?

Log in

No account? Create an account
Головоломка - Олег Етеревский [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) (Expand)
[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) (Expand)
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)
(no subject) - (Anonymous) Expand
[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)