Задачки

Солохин · июня 5, 2016, 19:02

Спасибо Вам большое!

То есть, при достаточно большом числе попыток зависимость вероятности выжить от числа попыток ДЛЯ ВСЕХ действительно оказывается равной вероятности выжить ДЛЯ ОДНОГО. Грубо говоря, с 3/4.

Всё-таки удивительно красивая, многогранная задача. Может быть, самая красивая задача из тех, что мне встречались в жизни.

лад · июня 5, 2016, 19:04

Цитата: Солохин от июня 5, 2016, 17:53
Не могли бы Вы прикинуть с помощью Вашей программы вероятность спасения, если каждому мудрецу разрешается открывать не 50, а 60, 70 или 80 шкатулок. Мне хочется узнать, начиная с какого предела эта вероятность становится близкой к единице!

Зачем нужна какая-то программа которая выдает какие-то случайные результаты когда можно в прямую посчитать вероятность? Формула-то простая, вероятность равна

P(k,n) = 1 - Σ_i=k+1ⁿ n!/((n-i)!i), где k - количество разрешенных открытий, n - всего шкатулок

Bhudh · июня 5, 2016, 19:07

Цитата: Солохин от июня 5, 2016, 19:02зависимость вероятности выжить от числа попыток ДЛЯ ВСЕХ действительно оказывается равной вероятности выжить ДЛЯ ОДНОГО.

Точнее сказать, вероятность выжить у КАЖДОГО становится примерно равной.

Солохин · июня 5, 2016, 19:49

Цитата: Bhudh от июня 5, 2016, 19:07
Цитата: Солохин от зависимость вероятности выжить от числа попыток ДЛЯ ВСЕХ действительно оказывается равной вероятности выжить ДЛЯ ОДНОГО.
Точнее сказать, вероятность выжить у КАЖДОГО становится примерно равной.

Нет, нам обоим никак не удается выразить эту мысль словами.
По условиям задачи, вероятность выжить для каждого изначально равна вероятности выжить для всех. Ведь их либо казнят, либо милуют всех одновременно.

Лучше сказать так: вероятность того, что выживут все, приближается к вероятности того, что первому же мудрецу повезет. Если везет первому - везет всем.

И мне понятно, почему так получается. Чем длиннее оказался самый длинный цикл, тем больше вероятность того, что первый же мудрец сразу попадет именно на него. А наших мудрецов губит ни что иное как слишком длинные циклы. Потому если каждому из них дается достаточно много попыток, то вероятность неудачи первого же из них практически равна вероятности того, что там вообще имеется этот (слишком длинный) цикл.

Цитата: лад от июня 5, 2016, 19:04
Формула-то простая, вероятность равна

P(k,n) = 1 - Σ_i=k+1 n!/((n-i)!i), где k - количество разрешенных открытий, n - всего шкатулок

Ой...

На мой вкус, эта формула совсем-совсем не проста. Например, Вы можете показать, что при достаточно больших k

P(k,n) = 1 - Σ_i=k+1 ((n-i)!i)/n! ~ k/n ?

Я вот не могу

_Swetlana · июня 5, 2016, 20:32

Напишите формулу по-человечески в техе

http://www.codecogs.com/eqneditor
За решением задачи не слежу, но предложение найти асимптотику как-то заинтересовало

yurifromspb · июня 5, 2016, 20:37

Так вроде же вероятность существования цикла длиной больше k это сумма 1/i от k+1 до n, если k больше n/2 (см. вложение)
А вобще - вот:
(wiki/en) 100_prisoners_problem

лад · июня 5, 2016, 21:01

Цитата: Солохин от июня 5, 2016, 19:49
На мой вкус, эта формула совсем-совсем не проста. Например, Вы можете показать, что при достаточно больших k

Да проста, после сокращения факториалов получается
P(k,n) = 1 - Σ_i=k+1ⁿ 1/i, где k - количество разрешенных открытий, n - всего шкатулок
При k = n P = 1
при k = 99 n = 100, P = 0,99
при k = 50 n = 100, P = 0,3119
при k = 61 P = 0,51, то есть выживают в большей части случаев

Солохин · июня 5, 2016, 21:17

Цитата: лад от июня 5, 2016, 21:01
проста, после сокращения факториалов получается
P(k,n) = 1 - Σ_i=k+1ⁿ 1/i, где k - количество разрешенных открытий, n - всего шкатулок

Ох ты!

Просто сумма по 1/i ?!
Это само по себе кажется странным. Почему так просто?

лад · июня 5, 2016, 21:26

Цитата: Солохин от июня 5, 2016, 21:17
Цитата: лад от июня 5, 2016, 21:01
проста, после сокращения факториалов получается
P(k,n) = 1 - Σ_i=k+1ⁿ 1/i, где k - количество разрешенных открытий, n - всего шкатулок
Ох ты!

Просто сумма по 1/i ?!
Это само по себе кажется странным. Почему так просто?

Тут чистая комбинаторика. Полное число циклов длинной i есть биномиальный коэффициент (ⁿ_i) помноженный на (i-1)! и на количество вариантов в оставшейся части (n-i)!. Далее для вычисления вероятности делим на полное число перестановок n!, не забыть сократить члены. Как получается сумма я уже писал ранее.

Солохин · июня 5, 2016, 21:42

Всё равно непонятно, почему.
Если все так лихо сокращается и упрощается, этому должны быть причины!

лад · июня 5, 2016, 22:08

Цитата: Солохин от июня 5, 2016, 21:42
Всё равно непонятно, почему.
Если все так лихо сокращается и упрощается, этому должны быть причины!

Так все просто. Все дело в том что количество путей цикла длинны i = (i-1)! = i!/i, поэтому все факториалы сокращаются, остается только этот пресловутый 1/i. Грубо говоря, из-за того что количество перестановок некоего типа это есть количество вариантов в делителе / в вероятности. Других причин наверное нету, просто так получается после вычислений.

_Swetlana · июня 5, 2016, 22:50

Цикл можно обходить по часовой и против часовой стрелки. Ещё на 2 надо поделить.
$[tex]<br />\frac{i!}{2i}<br />[/tex]$

лад · июня 5, 2016, 22:55

Цитата: _Swetlana от июня 5, 2016, 22:50
Цикл можно обходить по часовой и против часовой стрелки. Ещё на 2 надо поделить.
$[tex]<br />\frac{i!}{2i}<br />[/tex]$

Нет. Это перестановки, никакого направления обхода не существует. Не понимаете не пишите.

_Swetlana · июня 5, 2016, 23:07

Научитесь вначале техом пользоваться, чтобы я сюда заходила.

Солохин · июня 6, 2016, 06:20

Цитата: _Swetlana от июня 5, 2016, 22:50
$[tex] \frac{i!}{2i} [/tex]$

Цитата: _Swetlana от июня 5, 2016, 23:07
Научитесь вначале техом пользоваться, чтобы я сюда заходила.

Да, Вас здесь не хватает

Солохин · июня 6, 2016, 06:52

Давайте и правда воспользуемся техом.

Верно ли я понимаю? Утверждается, что вероятность спасения для $[tex]n[/tex]$ мудрецов, перед которыми стоят $[tex]n[/tex]$ шкатулок, из которых каждому разрешается заглянуть лишь в $[tex]k[/tex]$ штук
$[tex]P(k,n)=1-\sum\limits_{i=k+1}^{n}\frac1{i}[/tex]$

_Swetlana · июня 6, 2016, 10:31

Вот, красота ведь. Ув. коллеги, просто захо́дите на этот ресурс
http://www.codecogs.com/eqneditor
а потом обрамляете готовую формулу тегами tex в квадратных скобках.

В задачу не вникала, каюсь. Пишу только о том, что понимаю

При фиксированных $[tex]k[/tex]$ вершинах контуров (или ориентированных циклов) длины $[tex]k[/tex]$ в полном орграфе будет $[tex](k-1)![/tex]$ , а циклов в полном неориентированном графе будет $[tex]\frac{(k-1)!}{2}[/tex]$ , в чём нетрудно убедиться, построив полный неориентированный граф на трёх вершинах. Выбрать $[tex]k[/tex]$ вершин можно $[tex]C_{n}^{k}[/tex]$ различными способами, где $[tex]n[/tex]$ - количество вершин графа, $[tex]k\leq n[/tex]$ .

лад · июня 6, 2016, 13:00

Цитата: _Swetlana от июня 6, 2016, 10:31
В задачу не вникала, каюсь. Пишу только о том, что понимаю
а циклов в полном неориентированном графе будет

Причем тут неориентированные графы? В этой задаче их сроду не было. Это по условиям задачи граф обхода, то есть по определению ориентированный граф выражаемый перестановкой которые всегда ориентированные. Можно рассуждать в терминах перестановок в симметрической группе, тогда таких абстракций как не из чего не следующие неориентированные графы не возникнут.
Прежде чем писать нужно познакомиться с условиями задачи, конечно.)))

_Swetlana · июня 6, 2016, 13:17

Лад, вы всё время указываете, чего и как мне писать в этой теме.
Начните с себя. Пользуйтесь, пожалуйста, редактором формул.

Солохин · июня 6, 2016, 18:54

Кстати, а вот эту задачу решали на международном форуме эсперантисты семь лет назад http://eo.lernu.net/komunikado/forumo/temo.php?t=5424

_Swetlana · июня 6, 2016, 22:47

Посмотрела решение задачи о заключённых. (Тот редкий случай, когда графы не нужны. Тем не менее, их и сюда приплели.)
Решение простое, конечно. Но не осмыслила

вид полученной функции вероятности.

Буду пользоваться обозначением $[tex](n)_{r}=n\times (n-1)\times \cdots (n-r+1).[/tex]$
Генеральная совокупность состоит из n элементов; производим выборку r элементов без возвращения.
Если заключённый один. Вероятность появления фиксированного номера в выборке равна
$[tex]1-\frac{(n-1)_r}{n_r}=1-\frac{n-r}{n}=\frac{r}{n}.[/tex]$
Для одного заключённого вероятность спасения растёт как линейная функция при увеличении объёма выборки.

Как растёт для $[tex]k, k=2\cdots n [/tex]$ заключённых при описанной в решении оптимальной стратегии? Какой там вид функции?

_Swetlana · июня 7, 2016, 04:43

Осмыслила

Для оптимальной стратегии вероятность не зависит от количества участников. Будем сравнивать вероятности проигрыша (для удобства) при случайном выборе и при оптимальной стратегии для одного участника.
$[tex]r=100; 0; 0.[/tex]$
$[tex]r=99; \frac{1}{100}; \frac{1}{100}.[/tex]$
$[tex]r=98; \frac{1}{100}+\frac{1}{100}; \frac{1}{99}+\frac{1}{100}[/tex]$ и так далее.
Для одиночки случайный выбор лучшая стратегия.

Волод · июня 7, 2016, 07:39

Возвращаясь к презренному металлу.
Интересная картина получается, на первый взгляд процент проблематичных номеров заветных клеток вроде должен расти пропорционально числу нестандартных клеток после раскладки монеток надзирателем.
Однако,когда количество нестандартных клеток достигает 32, можно без проблем (не считая необходимости складывать в уме 32 числа) задать номер любой заветной клетки.
Наверно это потому, что 32 из 64 нестандартным быть не может.

Волод · июня 7, 2016, 08:05

Возможно нужно просто уделить больше внимания тем вариантам где предложенное решение (wiki/en) 100_prisoners_problem не работает7

Номер шкатулки: 1 2 3 4 5 6... 98 99 100

Номер карточки: 1 2 3 4 5 6... 98 99 100 работает

Номер карточки: 2 3 4 5 6.... 99 100 1 100 шагов -секир башка
Номер карточки: 3 4 5 6.... 100 1 2 50 шагов - Ура
Номер карточки: 4 5 6.... 1 2 3 100 шагов - секир башка
...

Не знаю как в других вариантах, но в этом создаётся впечатление, что если чётность лежащей в ячейке карточки совпадает с чётностью номер ячейки то жить можно.

_Swetlana · июня 12, 2016, 20:00

Очень простая задачка, которую нужно решить очень просто, то есть в уме.
ABCD - параллелограмм, точки X и Y - произвольные внутренние точки соответствующих сторон.
Доказать, что сумма площадей жёлтых треугольников равна сумме площадей зелёных.

Лингвофорум

Задачки

Солохин

лад

Bhudh

Солохин

_Swetlana

yurifromspb

лад

Солохин

лад

Солохин

лад

_Swetlana

лад

_Swetlana

Солохин

Солохин

_Swetlana

лад

_Swetlana

Солохин

_Swetlana

_Swetlana

Волод

Волод

_Swetlana

Быстрый ответ