еще одна задачка

[avva]

migmit:

Я не помню, где видел эту задачу, если здесь - звиняйте.
В тюрьме содержатся 100 узников. Однажды их собирают во дворе и объявляют, что проведут с ними испытание. Состоит оно в следующем. В одной из камер расставлены (можно считать, что в ряд) 100 ящиков. В каждый из них положена бумажка с именем одного из узников, причём в разные ящики - разные имена. Узников по одному будут заводить в эту камеру. В камере узник может открыть любые - какие захочет - 50 ящиков из 100. После этого его уведут и сразу отправят в его камеру, так что никакого обмена информацией со следующими не будет. Уходя, он должен оставить камеру точно в том же состоянии, в котором её нашёл - в частности, запрещено перекладывать бумажки, оставлять ящики открытыми и т.п. Узников выпустят, если КАЖДЫЙ из них найдёт бумажку со своим именем, в противном случае всех казнят. У них есть полчаса перед началом испытания, чтобы договориться. Как им следует действовать, чтобы вероятность выжить составила хотя бы 30%?

Не могу решить :(

Comments

[slonarch.livejournal.com]

И бумажку со своим именем он тоже оставляет в камере?

[avva.livejournal.com]

"Уходя, он должен оставить камеру точно в том же состоянии, в котором её нашёл", т.е. да.

[normal-homyak.livejournal.com]

Да никак, вероятность выжить у каждого при указаных условиях 50%, обмена никакого, т.е. в указаных условиях выживет 50%, даже вероятностная погрешность не опустит ниже 30%...

[http://users.livejournal.com/_scorp_/]

выпустят если каждый найдет. т.е. если хотя бы один ошибется - все пропало
совсем не 50%

[signamax.livejournal.com]

условие противоречивое
там нет вероятности выжить 30% поскольку по условию КАЖДЫЙ должен найти своё имя

как им решить чтобы каждый нашел - я не знаю
может пока
так что вероятность выше 0 не поднимается

[signamax.livejournal.com]

условие может быть сведено к менее громоздкому
в комнате всего 2 ящика
один всегда пустой
а в другой кладут бумажку входящего
найдет ли он ее?

[akor168.livejournal.com]

так что вероятность выше 0 не поднимается

Не совсем так. Грубо говоря, начальное распределение, это перестановка чисел от одного до 100, и хоть она неизвестна участникам, тем не менее она не меняется в процессе. Понятно, что первый может открыть любые 50 ящиков, и с вероятностью одна вторая, всех казнят сразу. Однако, предположим, что он попал. Поскольку второй знает, что первый угадал свой ящик, а также знает, какие ящики он открывал, в результате, он должен сделать коррекцию. И опять-таки, если он попадает на свой, у третьего информации еще больше. То есть, если кто-то не угадывает, то казнят всех, однако последовательные угадывания дают все больше и больше информации следующим гадателям.

[pivchanskiy.livejournal.com]

Каждый узник заходит в камеру и с некоторой долей вероятности находит своё имя. Перемножение этих вероятностей - общая вероятность того, что все узники найдут своё имя. Нужно, чтобы она была больше 30%.

Очевидно, что если все узники будут выбирать первые 50 ящиков, или будут выбирать ящики от балды - вероятности будут разные

[mura-vey.livejournal.com]

Ну почему 0, всего навсего (1/2)^100.

[monomyth.livejournal.com]

Узников выпустят, если КАЖДЫЙ из них найдёт бумажку со своим именем, в противном случае всех казнят.

о каких 30% речь? Умрут все.

[migmit.livejournal.com]

Нет.

[anhinga-anhinga.livejournal.com]

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

Пусть тянут бумажки только два узника (100 имен, каждый смотрит на 50 ящиков). Если они не договариваются между собой, вероятность успеха 1/4. Оптимальный договор для них -- непересекающиеся множества ящиков, и веороятность успеха (1/2)*(50/99), то есть лишь чуть выше 1/4 и уже меньше 30%.

Если это предположение неверно, то кажется, что задача не вполне определена..

[yurilax.livejournal.com]

ага, мне кажется, у задачи что-то с формулировкой не то.

Задача верна. Решение есть!

[yurilax.livejournal.com]

Ой. Беру свои слова обратно - формулировка верна и решение есть.
Я сдался и обратился к Великому Гуглу, который мне всё и рассказал.

Решение (для меня) показалось достаточно нетривиальным. Боюсь, что сам бы никогда не дошел.

Re: Задача верна. Решение есть!

[akor168.livejournal.com]

Не искушайте.

[bakhtin.livejournal.com]

Скорей всего, задача эта была придумана задним числом для иллюстрации по меньшей мере двух красивых идей. Я не решил, а прочитал решение на http://www.sciencenews.org/articles/20060819/mathtrek.asp

Там, собственно, и пишут, что эта задача --- модификация проблемы, решение которой появилось в "серьёзной" печати несколько лет назад.

Прикольно, что задача приписывается Peter'у Winkler'у, а я его сегодня видел, а в четверг пойду слушать его доклад на конференции по дискретной математике и фазовым переходам http://www-static.cc.gatech.edu/~vigoda/workshop/program.html.

[bakhtin.livejournal.com]

...а когда-то читал его книгу по Monte-Carlo Markov Chains & Simulated Annealing. Отличная книга, кстати.

[bespechnoepero.livejournal.com]

Ребята, математики не попадают в тюрьму. Так что все они умрут. Единственный шанс у них, поднять восстание, захватить охранников в заложники.

[vvyy.livejournal.com]

Что, на месте расстерливают?

[muchacho.livejournal.com]

Я после нагугленной подсказки решение угадал, но понятия не имею, как доказать, что оно верное. Точнее, не вижу лёгкого способа доказательства.
Подсказка (постараюсь сделать невидимой):

то шляпы, то ящики...

[santagloria.livejournal.com]

вы же их вконец умучаете!

[moldavsky.livejournal.com]

Во-вторых, количество открываний ящиков до успеха - это всегда "заколдованные" ряды цифр.

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

[shure.livejournal.com]

Чего-то я не понимаю одну вещь. Предположим что в пермутации нет циклов длины больше чем 50. Что же мешает узнику попасть в более короткий цикл не содержащий его имени ? Например я это A. В ящике А нахожу бумажку Б, в ящике Б - бумажку В, в ящике В бумажку Б. Что мне делать ?

[migmit.livejournal.com]

То есть, бумажка Б лежит в двух ящиках одновременно? Запрещено условием.

[timur0.livejournal.com]

Интересно, решил ли кто-нибудь эту задачку за 30 минут? А ведь за это время надо еще распределить номера по узникам и заучить наизусть эту нумерацию, причем это должны сделать все 100 узников... Как далека математика от организационных вопросов!

[latakot.livejournal.com]

У Вас же в условии не сказано, что на ящичках написаны имена, а это очень существенно.
Конечно, можно им всем пронумероваться, держать в памяти все номера и имена и отсчитывать номер ящичка в ряду, но это уж слишком... бесчеловечно. :)

[ex-tws5249.livejournal.com]

The better strategy goes as follows. Each prisoner will first open the drawer which corresponds
to his number. If his number is not there, he’ll use the number he just found to access another
drawer, then find a number there that points him to a third drawer, and so on, hoping to return
to his original drawer in at most 50 trials. (The last opened drawer will then contain his num-
ber.) This strategy succeeds provided the initial permutation σ defined by σi being the number
contained in drawer i has all its cycles of length at most 50. The probability of the event is
p = ..... = 0.31182 78206.

http://algo.inria.fr/flajolet/Publications/book070211.pdf
p.165

[tr.livejournal.com]

Здорово!

boring!

[socket-2007.livejournal.com]

Yes it is