[san_piter]

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

В тюрьме сидят 100 заключенных. У каждого заключенного есть свое уникальное имя. Имена всех 100 заключенных положили в 100 ящичков, по 1 в каждый ящик. Ящики расставили в линию в комнату, в которую по одному пускают заключенных. Каждый заключенный может посмотреть содержимое не более 50 ящиков. После этого он выходит из комнаты через другую дверь и никаким образом не может передать информацию еще не входившим в комнату заключенным. После того, как он выходит из комнаты, все содержимое комнаты приводится к ее изначальному состоянию.

Если все 100 заключенных найдут свои имена, их выпустят. Если хотя бы один из 100 не найдет своего имени в своих 50 ящиках - всех казнят.
Заключенные могут договорится между собой до похода первого из них в комнату о том, как они будут открывать ящики.

Так вот, когда мой приятель сказал мне, что сущетсвует стратегия, при которой в >30% случаев их освободят, я, ес-но, не поверил. Когда я увидел решение, я прифигел - насколько оно простое.

[Gnome]

классная задачка, правда ответ придумать не могу пока что

[zlojolenevod]

У меня два варианта, один простой, второй немного математический (хоть бы они все умели считать ):

1. Четный смотрит первые 50, нечетный соответственно вторые 50.
2. Смотрится по два ящика с шагом в два ящика, а начинают смотреть ящик с того номера, которым по счету зашел заключенный (если дошел до конца, идет в начало).

[san_piter]

Сообщение от ZlojOlenevod писал вс, 25 марта 2007 03:41

У меня два варианта, один простой, второй немного математический (хоть бы они все умели считать ):

1. Четный смотрит первые 50, нечетный соответственно вторые 50.
2. Смотрится по два ящика с шагом в два ящика, а начинают смотреть ящик с того номера, которым по счету зашел заключенный (если дошел до конца, идет в начало).

Решения не верны. Хотя бы потому, что это не решения, т.к. нет доказательства

Скажу честно, в формальном доказательстве присутствуют некоторые нетривиальные формулы, но в неформмальном виде, т.е. "на словах", оно (доказательство) очень простое.

[korovin]

Давайте сначала для 2-х заключеных решим. Математическая вероятность 0.5*0.5=0.25. Как получить 0.3? Или открыть свое имя и найти его - не одно и тоже? После процедуры заключеные общаются? Если нет, то какая польза им от того что они договорятся как открывать ящики? Мне кажется что суть решения - найти подвох в условии.

[san_piter]

отредактировано

Тут было объяснение, почему для двоих вероятность не 0.25.
Прочитав это объяснение понял, что оно является подсказкой и стер его.

Подвоха в условии нет. Заключенные не могут общаться (в любых смыслах этого слова) с момента захода первого из них в комнату.

[Это Я]

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

[san_piter]

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

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

Да, в буквальном.

[Cardinal]

Сообщение от Korovin писал вс, 25 марта 2007 04:53

Давайте сначала для 2-х заключеных решим. Математическая вероятность 0.5*0.5=0.25. Как получить 0.3?

Если 2 зека и 2 ящика, то все просто. Один смотрит 1-й ящик и
говорит об этом 2-му. С 50% он не угадает и их казнят.
Если он попал, то второй смотрит ящик №2. P=0.5

Для более сложных моделей уже голова не варит, ибо 5 утра.

[Это Я]

Прикольная задача. Не могу найти решение даже для 4 зеков на 4 ящика или хотя бы для 2 первых зеков из 100 с р>0.3

[korovin]

Сообщение от Цитата:

Тут было объяснение, почему для двоих вероятность не 0.25. Прочитав это объяснение понял, что оно является подсказкой и стер его.

Так может проблема именно в постановке задачи? Большинство ведь понимает условие так, что должно быть 0.25

[san_piter]

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

Так может проблема именно в постановке задачи? Большинство ведь понимает условие так, что должно быть 0.25

Перечитал условия - задача сформулирована корректно.
Никакого подвоха нет. Собственно, Cardinal выше уже написал, почему в случае с двумя зэками P>0.3.

[ежык]

заключенные заходят с часами и каждую минуту например смотрят по ящику. когда запускают следущего. то он знает в каком ящике нашел первый зек свое имя. в том ящике он смотреть не будет
1й зек найдет имя с вероятностью 50/100
2й уже 50/99 и т.д. думаю идея понятна
верно?

[san_piter]

Сообщение от ежык писал вс, 25 марта 2007 05:59

заключенные заходят с часами и каждую минуту например смотрят по ящику. когда запускают следущего. то он знает в каком ящике нашел первый зек свое имя. в том ящике он смотреть не будет
1й зек найдет имя с вероятностью 50/100
2й уже 50/99 и т.д. думаю идея понятна
верно?

Нет, не верно. Кроме того, 50/100 * 50/99 < 0.3.

[korovin]

Сообщение от Цитата:

Подвоха в условии нет. Заключенные не могут общаться (в любых смыслах этого слова) с момента захода первого из них в комнату

Сообщение от Цитата:

Если 2 зека и 2 ящика, то все просто. Один смотрит 1-й ящик и говорит об этом 2-му. С 50% он не угадает и их казнят. Если он попал, то второй смотрит ящик №2. P=0.5

Сообщение от Цитата:

Никакого подвоха нет. Собственно, Cardinal выше уже написал, почему в случае с двумя зэками P>0.3.

И всеже из условия явно не следует что при первом же промахе эксперимент СРАЗУ заканчивается. В этом случае факт "эксперимент НЕ окончен" можно считать маяком для последующих зеков.

[nik_kg]

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

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

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

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

[nik_kg]

Пример для n=4

1234=(1234) +++
1243=(43) +++
1324=(32) +++
1342=(342)
1423=(432)
1432=(42) +++

2134=(21) +++
2143=(21)(43) +++
2314=(231)
2341=(2341)
2413=(2431)
2431=(241)

3124=(321)
3142=(3421)
3214=(31) +++
3241=(341)
3412=(31)(42) +++
3421=(3241)

4123=(4321)
4132=(421)
4213=(431)
4231=(41) +++
4312=(4231)
4321=(41)(32) +++

10/24 ~ 0,42

Edit: остается вывести общую формулу для числа устраивающих нас подстановок. Число всех подстановок n! Как посчитать только устраивающие нас пока не соображу

[nik_kg]

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

Имена всех 100 заключенных положили в 100 ящичков, по 1 в каждый ящик.

ГЫ... а положили как? Случайно или нет? А то ведь могли нарочно так положить, чтобы нейтрализовать эту стратегию

[mikhaylo]

Обязан ли заключенный покинуть комнату после того, как найдет свое имя в ящике?
Вообще ничего не приходит в голову кроме алфавитной сортировки ящиков первыми двумя заключенными... :?

[nik_kg]

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

Обязан ли заключенный покинуть комнату после того, как найдет свое имя в ящике?

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

...он выходит из комнаты через другую дверь и никаким образом не может передать информацию еще не входившим в комнату заключенным

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

Вообще ничего не приходит в голову кроме алфавитной сортировки ящиков первыми двумя заключенными... :?

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

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