?

Log in

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

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

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

По многочисленным просьбам -- вот решение вчерашней головоломки:

Перед началом процесса приговорённые случайным образом присваивают себе номера от одного до ста и договариваются о нумерации коробочек в комнате (например, слева направо). Каждый, заходя в комнату, первым делом смотрит в ящик со своим номером. Если он находит свою бумажку -- всё ok, если нет -- он смотрит в ящик с номером человека, имя которого он нашёл в своём ящике. И так далее. Если он находит своё имя, он выиграл, если нет -- следующий ящик под номером человека, имя которого он увидел в предыдущем.

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

Попытаюсь для не-математиков объяснить на пальцах, почему это работает. Идея в том, что если начать с какой-то коробочки и действовать с помощью этого алгоритма, то рано или поздно вернёшься к ней. Все коробочки, таким образом, разбиваются на циклы. Вероятность того, что все эти циклы содержат в себе не больше 50-и коробочек как раз и составляет около 30% (это на пальцах я объяснить не берусь).

LinkReply

Comments:
[User Picture]From: fealin_lena
2007-07-06 11:14 am (UTC)
О офигенно великий маг, ты, порой, заставляешь мозги раскручиваться:)
(Reply) (Thread)
[User Picture]From: eterevsky
2007-07-06 11:25 am (UTC)
Да, я всегда знал, что математика сродни магии. :)
(Reply) (Parent) (Thread)
[User Picture]From: igorantarov
2007-07-06 11:17 am (UTC)
О, точно!
Именно её я и видел! 8)))

спасиб )
(Reply) (Thread)
[User Picture]From: kirpich_spb
2007-07-06 11:23 am (UTC)
Здорово!! Красивое решение. Я вот не удержался и прочитал решение, так и не успев тольком подумать. Есть еще прикольная задачка про заключенных и карцер с лампочкой. Знаешь?
(Reply) (Thread)
[User Picture]From: eterevsky
2007-07-06 11:26 am (UTC)
Я про лампочки много задач знаю. Например, про три выключателя и три лампочки. Ты не эту имеешь в виду?
(Reply) (Parent) (Thread)
[User Picture]From: kirpich_spb
2007-07-06 11:29 am (UTC)
Не, не эту. Там условие похожее (хотя точно я его что-то не помню): есть заключенные, есть карцер, есть ламопчка в карцере, которую можно зажечь или потушить, и, типа, всех повесят, если они какой-то умный алгоритм не придумают. =)
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2007-07-06 11:36 am (UTC)
По-моему, это хорошее средство для студентов-информатиков: запереть куда-нибудь и всех повесить, если хитрый алгоритм не придумают. :)))
(Reply) (Parent) (Thread)
[User Picture]From: kirpich_spb
2007-07-06 11:38 am (UTC)
Хаха! =) Причем если в этой комнате будет интернет, то они, конечно, не придумают. А если нет -- то обязательно придумают.
(Reply) (Parent) (Thread)
[User Picture]From: dmitrits
2007-07-06 01:34 pm (UTC)
Их по-одному заводят в карцер, а там только лампочка и выключатель. Их всех отпустят, если в какой-то момент кто-нибудь скажет, что здесь уже все побывали как минимум по разу, а если это будет не так, то всех растреляют.
(Reply) (Parent) (Thread)
[User Picture]From: kirpich_spb
2007-07-06 01:37 pm (UTC)
Ага, все так. Нужно еще дать беднягам знать, что изначально лампочка потушена, видимо (ну, в известном состоянии).
(Reply) (Parent) (Thread)
[User Picture]From: dmitrits
2007-07-06 01:39 pm (UTC)
не нужно
(Reply) (Parent) (Thread)
[User Picture]From: lee_onore
2007-07-06 01:44 pm (UTC)

Эта?

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

1. Каждый из них будет сидеть в отдельной камере, не имея возможности общаться с остальными заключенными.
2. Ежедневно утром, начиная с первого дня заключения, одного из них будут отводить в карцер, а вечером того же дня возвращать назад в камеру.
3. В карцере есть лампочка, которую находящийся в карцере заключенный сможет включать и выключать. Надзиратели должны тщательно следить за тем, чтобы сидящие в карцере не оставляли друг другу никаких посланий. При этом надзиратели сами не будут ни включать, ни выключать лампочку.
4. Заключение закончится в тот день, когда кто-то из осужденных сообщит надзирателю о том, что каждый из десяти преступников побывал в карцере хотя бы один раз. Если это окажется правдой, то все десять преступников будут отпущены на свободу, в противном случае — их казнят.
5. До начала заключения преступникам разрешено собраться вместе и разработать план действий, позволяющий им покинуть место лишения свободы в соответствии с правилами задачи.
6. Заключенным не известен порядок, в котором будут они сидеть в карцере, но им сообщили, что согласно плану надзирателей:
* каждый заключенный побывает в карцере;
* после выхода из него заключенный вновь попадает туда через конечное число дней.
7. Предполагается, что ни один из преступников не может ни освободиться, ни умереть иначе как в результате того, что кто-то из заключенных сообщит надзирателю о факте пребывания в карцере каждого преступника.

Необходимо предложить такой алгоритм поведения преступников, который позволит им выбраться из тюрьмы за конечное время без риска быть казненными.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2007-07-06 01:48 pm (UTC)
Да, я её когда-то решал.
(Reply) (Parent) (Thread)
[User Picture]From: kirpich_spb
2007-07-06 01:49 pm (UTC)

Re: Эта?

Ага, именно она. Только, блин, надо же было ее записать, используя столько букв! =)
(Reply) (Parent) (Thread)
[User Picture]From: thusthla
2007-07-06 11:25 am (UTC)
Это нереально же запомнить у кого какой номер.. =)
(Reply) (Thread)
[User Picture]From: eterevsky
2007-07-06 11:29 am (UTC)
Ну, это уже технические подробности, не относящиеся собственно к задаче. Если тебе так будет удобно, во всех подобных задачах можно считать, что фигурируют андроиды с неограниченной памятью и вычислительной способность.
(Reply) (Parent) (Thread)
[User Picture]From: thusthla
2007-07-06 11:31 am (UTC)
Фигасе, казнить столько андроидов с неограниченной памятью и вычислительной способность.. =)
(Reply) (Parent) (Thread)
[User Picture]From: halif
2007-07-06 02:13 pm (UTC)
А зачем помнить у кого какой номер? Каждому достаточно знать только свой номер...
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2007-07-06 02:18 pm (UTC)
Нет, не достаточно. Как же он иначе следующие ящики будет выбирать?
(Reply) (Parent) (Thread)
[User Picture]From: thusthla
2007-07-06 02:20 pm (UTC)
А как же тогда смотреть в ящик с номером человека, имя которого нашел в своём ящике?
(Reply) (Parent) (Thread)
[User Picture]From: halif
2007-07-06 02:25 pm (UTC)
Согласен, невнимателен. Думал, что в ящичках номера :)
(Reply) (Parent) (Thread)
From: (Anonymous)
2007-07-06 11:55 am (UTC)
Каким образом хотя бы даже последнему пленнику будет легче?
Шансы любого из пленников будут около 70%.

Подобный алгоритм лишь сведет на ноль шанс, что все пленники "посмотрят первые 50 ящиков". Т.е. в итоге в каждый ящик заглянет ровно 50 пленников.
Точно такой же эффект даст алгоритм, который озвучил Шуклин.

ЗЫ: в процессе обсуждения родилась идея 99 пленникам убить себя сразу, тогда один оставшийся выживет с 70% вероятностью.
(Reply) (Thread)
[User Picture]From: eterevsky
2007-07-06 12:01 pm (UTC)
Во-первых, в результате этого алгоритма, шансы _одного_ пленника никак не изменятся и останутся равными 50%. Во-вторых, фишка в том, что коль скоро в этой перестановке не будет циклов длины больше 50, ВСЕ пленники найдут свои имена.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2007-07-06 12:05 pm (UTC)
Да, фишка в том, что шансы каждого из пленников найти свою бумажку остаются равными 50%, но эти вероятности перестают быть независимыми, и поэтому вероятность успеха всех не равна произведению вероятностей успеха каждого. Так например, при таком алгоритме, если мы знаем, что первые 50 приговорённых нашли свои бумажки, мы можем гарантировать, что остальные 50 тоже найдут.
(Reply) (Parent) (Thread)
From: (Anonymous)
2007-07-06 12:19 pm (UTC)
Шансы одного пленника все таки порядка 70%.
(1/100+1/99+...+1/50)

Работу алгоритма таки осознал. Красиво. ^_^
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2007-07-06 12:26 pm (UTC)
Нет, Вы неправильно считаете вероятность успеха. Если действовать таким способом, то должно получаться:

1/100 + 99/100*(1/99 + 98/99*(1/98 + ...)),

что в точности равно 1/2. Дело в том, что если пленник находит в первом ящике своё имя, то он не продолжает процесс, так что всё остальное приходится умножить остальные слагаемые на 99/100 и т. д.

P.S. Кстати, с кем имею честь? :)
(Reply) (Parent) (Thread)
[User Picture]From: vse_budet
2007-07-06 02:18 pm (UTC)
Отличная головоломка, побольше бы таких, а то мозг костенеет в отсутствии олимпиадных задач.
//Только я опять понял условие когда прочитал решение, но конечно врядли бы сам решил.
Очень симпатично!=)
(Reply) (Thread)
[User Picture]From: amarao_san
2007-07-06 07:49 pm (UTC)
Офигеть. Я пас.
(Reply) (Thread)
[User Picture]From: clanchmo
2007-07-06 09:23 pm (UTC)
Ни шиша не понятно... Чувствую себя дурой...*ушла плакать в чулан*
(Reply) (Thread)
[User Picture]From: eterevsky
2007-07-07 11:32 am (UTC)
Ничего страшного. Просто задача сложная, и я написал только набросок решения.
(Reply) (Parent) (Thread)
From: ex_alinusch
2007-07-07 11:26 am (UTC)
Как обидно быть блондинкой...
Очень стильная сама задача.
(Reply) (Thread)
[User Picture]From: eterevsky
2007-07-07 11:31 am (UTC)
Тут дело не в цвете волос. Сама задача совсем не простая.
(Reply) (Parent) (Thread)
[User Picture]From: ontumuct
2007-07-07 12:51 pm (UTC)
мощно.
(Reply) (Thread)
From: (Anonymous)
2007-07-09 07:46 am (UTC)
Маленький комметарий.

Шансы каждого пленника. Чуть больше 50%, так как
если он не открыл ящик со своим номером у него еще есть шанс угадать (1 к 50).

Юрий Белов
(Reply) (Thread)
[User Picture]From: eterevsky
2007-07-09 10:37 am (UTC)
Угадать что?! Юра, у тебя 100 ящиков, ты открываешь 50 -- какова вероятность открыть правильный?
(Reply) (Parent) (Thread)