?

Log in

Головоломка - Олег Етеревский [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: eterevsky
2007-07-05 12:47 pm (UTC)
Собственно ответ нмже уже озвучили -- можно гарантировать вероятность 30%.
(Reply) (Parent) (Thread)
[User Picture]From: _43_
2007-07-05 12:59 pm (UTC)
так мне ж не ответ нужен, а алгоритм..
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2007-07-05 01:05 pm (UTC)
Если совсем не терпится, поищи в интернете "Seven Puzzles You Think You Must Not Have Heard Correctly".
(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)
[User Picture]From: eterevsky
2007-07-05 12:23 pm (UTC)
Если алгоритм известен, то оценить вероятность -- дело техники. Первокурсник матмеха должен справиться. А вот придумать...
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]From: eterevsky
2007-07-05 01:04 pm (UTC)
Передам, когда познакомлюсь. :)
(Reply) (Parent) (Thread)
[User Picture]From: halif
2007-07-05 01:04 pm (UTC)
По идее да, но там целая серия нестандартных умозаключений, впрочем несложных :)
Но я не знаю, как можно додуматься. Надо быть гением. А вот угадать - можно :)
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2007-07-05 01:29 pm (UTC)
Не вижу принципиальной разницы между додуматься и угадать. В любом случае, не знаю, как это сделать. :)
(Reply) (Parent) (Thread)
[User Picture]From: halif
2007-07-05 01:38 pm (UTC)
Такая же как и между конструктивным доказательство существования и доказательством от противного :) Не все признают закон исключенного третьего.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2007-07-05 01:43 pm (UTC)
Ну нет. Между конструктивным и неконструктивным доказательствами есть вполне конкретная формальная разница. Для способов эвристического поиска решения ничего подобного нет.
(Reply) (Parent) (Thread)
[User Picture]From: halif
2007-07-05 01:54 pm (UTC)
А я и не думаю, что есть формальная разница.
Лично для меня эти способы поиска решения разные.
"Додоуматься" - значит найти решение структурированным поиском, небольшими шагами в пространстве утверждений, начиная от исходных данных. (Прошу понимать это как метафору).
Угадать - это примерно прицелиться и выстрелить сразу в сторону решения - большим "шагом". Нужно большое искусство целиться, умение угадать направление.

Для сложных задач я сочетаю эти способы.
(Reply) (Parent) (Thread)
[User Picture]From: vse_budet
2007-07-05 06:34 pm (UTC)

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

У меня пока воображения не хватает для того, чтобы представить как она может быть больше 50%. Вроде, вероятность того, что игра не кочается проигрошем после первого хода такая.

Я правильно понимаю, что задача эквивалентна выбору 100 наборов по 50 ящиков?
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2007-07-05 06:40 pm (UTC)

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

Больше 50% её, естественно, сделать нельзя. Можно -- около 30%.

Не понимаю, что за выбор наборов из 50 ящиков.
(Reply) (Parent) (Thread)
[User Picture]From: halif
2007-07-06 07:23 am (UTC)

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

Да, 30% с небольшим.

Если я правильно вас понял - нет не эквивалентна.
Человек может не знать заранее какие конкретные ящики он откроет (это подсказка)!
(Reply) (Parent) (Thread)
[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)
[User Picture]From: eterevsky
2007-07-05 12:30 pm (UTC)
В том-то и дело, что в таком виде рассуждения не улучшают вероятность вообще.
(Reply) (Parent) (Thread)
[User Picture]From: amarao_san
2007-07-05 01:07 pm (UTC)
Ну, так как в каждом ящике лежит имя (нужное нам), то туда должен заглянуть хотя бы один человек. При этом чем больше людей заглянет, тем больше шанс совпадения.
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]From: eterevsky
2007-07-05 01:32 pm (UTC)
Не сбивай человека с толку, как ты узнаешь, какая именно бумажка была для предыдущего человека нужной?
(Reply) (Parent) (Thread)
[User Picture]From: amarao_san
2007-07-05 02:08 pm (UTC)
Как остальные узнают, какая бумажка "нужная"? И что в неё смотреть не нужно? По правилам каждый заключённый с начала выполнения алгоритма не может общаться с другими. По всей видимости и знаков оставлять тоже не может.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2007-07-05 02:13 pm (UTC)
Давай я лучше правильную подсказку дам. :) Действия каждого следующего участника не должны зависеть от результатов действий предыдущих.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2007-07-05 12:30 pm (UTC)
В условии написано, что найденные бумажки остаются в ящиках.

Дальше. Твой подсчёт кругом ошибочен. У тебя все попытки незавимы и с вероятностью близкой к 1, кто-то найдёт свою бумажку 2 раза, а кто-то -- ни одного.

Дальше, от того, что не человек будет заглядывать в 50 ящиков, а в ящик будет заглядывать 50 человек, очевидно ничего не меняется. Если, в соответсвии с твоим планом, первые 50 человек будут заглядывать в первые 50 ящиков, а вторые -- во вторые, то вероятность останется равной 2-100.
(Reply) (Parent) (Thread)
[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)
[User Picture]From: hronopik
2007-07-05 01:27 pm (UTC)
Интересно-интересно! Только ответ не пости! =)
(Reply) (Parent) (Thread)
[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)