[mikhaylo]

Сообщение от nik_kg писал вс, 25 марта 2007 12:20

Имелось в виду следующее : заключенный открывает все 50 допустимых ящиков или же покидает комнату сразу после того, как находит ящик со своим именем?

[nik_kg]

Сообщение от Mikhaylo писал вс, 25 марта 2007 12:26

Имелось в виду следующее : заключенный открывает все 50 допустимых ящиков или же покидает комнату сразу после того, как находит ящик со своим именем?

По условию задачи не обязан... но как это повлияет на решение?
Его цель - найти свое имя... а если он после этого и другие ящики посмотрит то толку в этом? Все равно другим об этом сказать не сможет.

[Allinat0r]

To San piter.
Могут ли заключенные договоритсья о том в како очередности они будут заходить в эту комнату? Если да то могу дать ответ при котором у них будет 50% на выполнение задачи 8-) .

[nik_kg]

Для n=2 вероятность 50%
Для n=4 я привел решение с 42%

Думаю что с увеличением n вероятность будет падать, но при n=100 все еще останется больше 30%

Помогите обобщить мой способ...

[Это Я]

Сообщение от nik_kg писал вс, 25 марта 2007 10:43

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

Договор такой: заключенный номер x идет смотреть ящик с номером x, затем ящик с порядковым номером, указанным в ящике x, и т.д.

Для доказательства нужно рассмотреть множество всех подстановок на n (n=100) элементном множестве и выбрать из них только те подстановки, которые являются циклами длиной не более n/2 (т.е. 50)

Edit: или разлагаются в произведение не более чем n/2 элементных независимых циклов

А если в ящике Y имя Y, куда смотреть.

До сомого дошло, не может так быть

[san_piter]

Сообщение от Allinat0r писал вс, 25 марта 2007 14:54

To San piter.
Могут ли заключенные договоритсья о том в како очередности они будут заходить в эту комнату? Если да то могу дать ответ при котором у них будет 50% на выполнение задачи 8-) .

По оригинальному условию - не могут. Но я не вижу, как это могло бы повлиять на решение.

[san_piter]

Сообщение от Mikhaylo писал вс, 25 марта 2007 12:26

Имелось в виду следующее : заключенный открывает все 50 допустимых ящиков или же покидает комнату сразу после того, как находит ящик со своим именем?

Не принципиально. В задаче сказано, что он может открыть до 50 ящиков.

[san_piter]

Сообщение от nik_kg писал вс, 25 марта 2007 10:43

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

Договор такой: заключенный номер x идет смотреть ящик с номером x, затем ящик с порядковым номером, указанным в ящике x, и т.д.

Для доказательства нужно рассмотреть множество всех подстановок на n (n=100) элементном множестве и выбрать из них только те подстановки, которые являются циклами длиной не более n/2 (т.е. 50)

Если это решение не было подсмотрено в инете, то глубочайший респект.
Формальное докзательство могу привести, если кому интересно. Суть в том, что для 100 ящиков вероятность того, что их перестановка не будет иметь циклов длиннее 50, равна 31.18. В общем же случае (2*N заключенных открывают по N ящиков) она не меньше, чем 1-ln(2) = 0.307.

[Женя]

Не читал толком ответы выше. Но думаю решение такое. Заключённые должны поочереди открывать сначала первые 50 ящиков, затем вторые. Почему?
Делаем предположение, что первый зек открывал 1-50 ящики и угадал. Следовательно второму зеку чтобы повысить свои шансы нужно выбирать 51-100 ящики. И так далее...
Думаю это верно хотя бы потому что если зеки будут открывать только первые 50 ящиков, то вероятность победы будет равна нолю. Поэтому нам нужно максимально разнообразить их выбор, чтобы каждый ящик открывался максимальное количество раз.

Я прав?

[Это Я]

Аналитически не потянул. Промоделировал на С++. Ответ совпал.

[mikhaylo]

Не до конца понял решение задачи, поэтому задам встречный вопрос.
Ведь вероятность того, что первый преступник откроет нужный ящик равна 1/2. За счет чего повышается вероятность открытия нужного ящика следующим преступником?

[nik_kg]

Сообщение от Mikhaylo писал вс, 25 марта 2007 18:14

Не до конца понял решение задачи, поэтому задам встречный вопрос.
Ведь вероятность того, что первый преступник откроет нужный ящик равна 1/2. За счет чего повышается вероятность открытия нужного ящика следующим преступником?

Посмотри на это с другой точки зрения. Поясню на примере для n=4.

Всего возможных раскладов имен по ящикам 24 (4!) Т.е. организаторы эксперимента могли разложить 4 имя по 4-м ящикам 24-мя различными способами... не более.

Так вот. Блигоприятными для нас, при данной стратегии, являются 10 из них. Т.е. если организаторы разложили имена по ящикам одними из этих 10 способов, то руководствуясь выбранной стратегией, каждый заключенный откроет свое имя со 100% вероятностью!!! Т.е. просто прийдет и гарантированно найдет свое имя!

Т.е. из 24 возможных раскладов нас устраивают 10. Имеем 10/24

См. табличку подстановок... я там приводил выше...

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

[nik_kg]

Сообщение от san_piter писал вс, 25 марта 2007 16:05

Если это решение не было подсмотрено в инете, то глубочайший респект.

Открыл свои старые лекции по комбинаторике и случайно наткнулся на тему подстановок...

Сообщение от san_piter писал вс, 25 марта 2007 16:05

Формальное докзательство могу привести, если кому интересно. Суть в том, что для 100 ящиков вероятность того, что их перестановка не будет иметь циклов длиннее 50, равна 31.18. В общем же случае (2*N заключенных открывают по N ящиков) она не меньше, чем 1-ln(2) = 0.307.

А вот откуда взялись этиц ифры так и не понял :? Можно по подробнее?

[mikhaylo]

Сообщение от nik_kg писал вс, 25 марта 2007 22:20

Посмотри на это с другой точки зрения. Поясню на примере для n=4.

Всего возможных раскладов имен по ящикам 24 (4!) Т.е. организаторы эксперимента могли разложить 4 имя по 4-м ящикам 24-мя различными способами... не более.

Так вот. Блигоприятными для нас, при данной стратегии, являются 10 из них. Т.е. если организаторы разложили имена по ящикам одними из этих 10 способов, то руководствуясь выбранной стратегией, каждый заключенный откроет свое имя со 100% вероятностью!!! Т.е. просто прийдет и гарантированно найдет свое имя!

Т.е. из 24 возможных раскладов нас устраивают 10. Имеем 10/24

См. табличку подстановок... я там приводил выше...

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

Теперь все понятно. Огромное спасибо за разъяснения.

[san_piter]

Сообщение от nik_kg писал вс, 25 марта 2007 22:32

А вот откуда взялись этиц ифры так и не понял :? Можно по подробнее?

См. тут [Зарегистрироваться?] html
И немного тут [Зарегистрироваться?]

[Allinat0r]

Каждому имени присвоить номер от 1 до 100. Один заключенный должен зайти и посмотреть какое имя в 1-вом ящике, затем просматривать остальные 49 в течение такого количества например часов, которому будет соответствовать номер имени лежащее в этом ящике. Например: в ящике номер 1 имя соответствующее числу 23, значит находится в комнате он должен 23 часа из чего остальные заключенные узнают имя лежащее в первом ящике. Потом заключенный 23 смотрит ящик соответствующий договоренности, а другие 49 втечении времени соответствующему имени в том ящике. и.т.д.
В случае если первый вошедший в комнату заключенный найдет свое имя, а это будет в 50% случаев, то все остальные тоже найдут.
50% лучше чем 30%, тем более что вопрос жизни и смерти

[Alexismoon]

Allinat0r, а разве вероятность, что второй найдёт своё имя в 99 ящиках, просмотрев всего 50 равна 100%?

Вопрос такого порядка - как решение этой задачки применимо к покеру?

Может, есть какой ориентир на доске, который подскажет, какие типы рук в следующей раздаче мы будем играть, а какие нет? Глупо звучит, конечно, но весьма интересная задачка и интересно, может ли она иметь практическое применение? Или, может быть, этот вариант подойдёт товарищам, юзающим рулетку? Если добиться простым способом там нормального +EV, так почему бы её не юзать тогда? Хотя, против рулетки вряд ли что поможет, конечно.

[Allinat0r]

Сообщение от Alexismoon писал вт, 27 марта 2007 00:40

Allinat0r, а разве вероятность, что второй найдёт своё имя в 99 ящиках, просмотрев всего 50 равна 100%?

Второй найдет с вероятностью 100% и с первой попытке.
Ты наверное не понял мое объяснение. Приведу более простой пример:
В комнате стоит 10 ящиков, в 9-ти ничего нет, а в одном предмет который надо найти. Я захожу в комнату, быстро смотрю все ящики и нахожу предмет в ящике N5. Затем стою там 5 часов и выхожу.
После этого в комнату заходит мой напарник и знает что предмет в ящике N5(т.к. мы заранее договорились о таком маяке).
И никакая математика нафиг не нужна

[Alexismoon]

Тогда ещё такой момент - схема работает, если заключённым можно менять свой порядок захода в комнату произвольно, если нет - не работает. А так - мысль оригинальная, 50% лучше 30% по-любому

[nik_kg]