?

Log in

No account? Create an account
Головоломка - Олег Етеревский [entries|archive|friends|userinfo]
Oleg Eterevsky

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Головоломка [5 July 2007|14:48]
Oleg Eterevsky
[Tags|, ]

Прочитал только что совершенно безумную головоломку. Давно математические задачи не поражали меня такой неправдоподобностью ответа.

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

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

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

LinkReply

Comments:
[User Picture]From: _43_
2007-07-05 11:17 am (UTC)
неправдоподобный ответ в студию!!!(( а то я голову сломаю
(Reply) (Thread)
[User Picture]From: eterevsky
2007-07-05 12:22 pm (UTC)
Ну, народ небось ещё подумать хочет. :)
(Reply) (Parent) (Thread)
[User Picture]From: halif
2007-07-05 11:37 am (UTC)

Задачка супер

У нас на работе проскочила. 2 дня думал.
Ответ (алгоритм) угадать (уменно угадать!) довольно легко. Но с ходу поверить в то, что такой способ дает более 50% шанс для всех быть помилованными - очень непросто :) Посчитать, кстати, тоже не очень легко.
(Reply) (Thread)
[User Picture]From: halif
2007-07-05 11:49 am (UTC)

Re: Задачка супер

Соврал. Больше 30%.
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]From: amarao_san
2007-07-05 11:43 am (UTC)
Во-первых, о вероятности для одного заключённого найти своё имя. Она составляет сумму верояностней найти 1 имя среди 100, среди 99, среди 98 и т.д. вплоть до 1 из 51. Это составляет примерно 0.688. Дальше каждый из них должен найти имя. Т.е. нам надо получить 100 раз успех при 0.688, итого, вероятность случайного процесса 0.688^100=8.55e-017 (а не 2e-100).

Это на первый взгляд.

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

Рассмотрим задачу с другой стороны: Пусть мы будем не выбирать ящики, куда заглядывать, а, наоборот, выбирать ящики, в которые НЕ заглядывать.

Очевидное условие: в каждый ящик должно заглянуть максимальное количество людей. В идеале - равное. Общее количество "выборок" - 10000, "заглядываний" - 5000. Значит, следует обеспечить такую последовательность, при которой в каждый ящик в сумме посмотрит 50 человек.


У нас есть 5000 попыток с вероятностью 0.01 для каждой попытки, требуется не менее 100 шаров. Итого: вероятность 0.01*5000/100 = 0.5

Можно предположить алгоритм Round Robin, (т.е. сдвиг "окна просмотра" на один ящик от каждого заключённого).


Хотя предпоследний абзац явно бредом отдаёт...
(Reply) (Thread)
(Deleted comment)
(Deleted comment)
[User Picture]From: maxim_34_region
2007-07-05 12:21 pm (UTC)
На память приходит "чёрный" анекдот про игру в "А ну ка отними!" в газовой камере с одним противогазом.
(Reply) (Thread)
[User Picture]From: hronopik
2007-07-05 01:15 pm (UTC)
А переставлять ящики можно?
(Reply) (Thread)
[User Picture]From: eterevsky
2007-07-05 01:25 pm (UTC)
Нет. Никак передавать информацию нельзя.
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: clanchmo
2007-07-05 09:02 pm (UTC)
Запости ответ, а то я двинусь!!! Я ж бедный историк, а не великий математик! Катя
(Reply) (Thread)
[User Picture]From: talinka_derevze
2007-07-05 10:40 pm (UTC)
Капитулирую!..
(Reply) (Thread)
[User Picture]From: igorantarov
2007-07-06 12:13 am (UTC)
Думать что-то совсем лениво. :)
Почему-то тоже хочется просматривать подряд и сдвигать каждый раз начальный ящих на +1. Но не уверен что это что-то даст (см. первую фразу). ;)

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

Речь там как-раз шла про неочевидность ответа.

(Reply) (Thread)
[User Picture]From: ontumuct
2007-07-07 12:49 pm (UTC)
мне эта задачка пришла из сана.думал 2 дня.плкал.рвал волосы, но не решил. =(
(Reply) (Thread)
[User Picture]From: eterevsky
2007-07-07 12:56 pm (UTC)
Собственно, я не знаю никого, кто бы её сам решил.
(Reply) (Parent) (Thread)
[User Picture]From: menato
2007-07-07 07:01 pm (UTC)
Есть ещё похожая головоломка с 8 гномами, которым на головы наденут колпаки, и они должны будут угадать свой цвет по сигналу.
(Reply) (Thread)
[User Picture]From: eterevsky
2007-07-07 10:40 pm (UTC)
А, ну это как раз несложно.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2007-07-10 12:24 pm (UTC)
Да, я думаю, я там буду. Особенно с учётом того, что впервые был на Волынщике ещё году в 2000-м... :)
(Reply) (Parent) (Thread)