ERUDITOR.RU

60. 100 узников №3.а) (ящики с именами)

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

Вопрос: Как им следует действовать, чтобы вероятность выжить составила хотя бы 30%?
Примечания
Аналогичная задача — «100 узников №3.б) (новогодняя версия)».
2008-08-28

Обсуждение


Задачи :: Новая задачка. Тоже про 100 узников.
↓↓ 0 ↑↑   eruditor (143 / 443)   2008-08-29 16:59   »»


А если передвигать ящики?
Или тоже запрещено?
↓↓ 0 ↑↑   Zero (38 / 335)   2007-05-16 21:29   «« #2 »»   Ответить


Разве не очевидно?
"Уходя, он должен оставить камеру точно в том же состоянии, в котором её нашёл."
Что тут может быть непонятно?
↓↓ 0 ↑↑   eruditor (143 / 443)   2007-05-16 23:04   «« #3 »»   Ответить


Если честно, то не очень.
Еще 2 глупых вопроса:
1. Во время испытания узник находится в камере один?
2. Бумажку с именем узник забирает с собой?
↓↓ 0 ↑↑   Zero (38 / 335)   2007-05-17 14:59   «« #4 »»   Ответить


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

ТОЧНО В ТОМ ЖЕ СОСТОЯНИИ.

Что же в этой формулировке непонятно? Каждая пылинка в комнате должна остаться на своём месте.
↓↓ 0 ↑↑   eruditor (143 / 443)   2007-05-17 20:29   «« #5 »»   Ответить


Ну с каждой пылинкой вы переборщили...:)
↓↓ 0 ↑↑   Zero (38 / 335)   2007-05-18 17:25   «« #6 »»   Ответить


Eсли формулировка такая жесткая, то о вольной трактовке, как и о хитро-мухлёжном решении можно забыть :)
Остается искать сложно-пессимистическое...
↓↓ 0 ↑↑   Zero (38 / 335)   2007-05-19 17:24   «« #7 »»   Ответить


За полчаса до испытания ...
узникам надо договориться о том, кто, какие ящики и в какой последовательности будет открывать.
Возьмем для примера 4 ящика, для которых возможны 24 варианта распределения имен. Перед началом испытания каждому узнику в произвольном порядке присваивается номер от 1 до 4. Они могут открывать ящики несколькими способами (например, 1 и 2 узник открывают 1 и 2 ящики, а 3 и 4 - 3 и 4 ящики; 1 и 3 открывают нечетные, остальные - четные и т.п.). Однако при любом способе только в 4 случаях из 24 (около 17%) все найдут свои имена.
Однако можно поступить по-другому. Узник, заходя в комнату, открывает ящик с номером, который ему присвоили. Если там его имени нет, то он открывает ящик с номером, который он нашел. Вероятность остаться в живых при этом возрастает до 10 случаев из 24 (почти 42%).
Логично предположить, что если эта стратегия сработала на 4 ящиках, то и на 50 она будет работать.
↓↓ 0 ↑↑   Zero (38 / 335)   2007-05-21 17:15   «« #8 »»   Ответить


???
Как-то непонятно... А точно есть решение?
↓↓ 0 ↑↑   -V@Ndal- (7 / 31)   2008-12-27 06:49   «« #9 »»   Ответить


!!!
Очень интересная задача.
Ещё показательнее она была бы с 1000-ю узниками и числом ящиков разрешённых открывать=995.
1)При случайном выборе ящиков для открытия,не смотря на большую вероятность найти своё имя каждым узником,общая вероятность остаться в живых<0,67%(т.е. они фактически смертники).
2)В случае же выбора по алгоритму,предложенному Zero, вероятность всех остаться в живых близка к 100%(им почти ничего не грозит).
Вот такая большая разница!
↓↓ 0 ↑↑   total (-4 / 9)   2009-02-19 19:51   «« #10 »»   Ответить


Похоже, что Zero прав
Моделирование его решения («Узник, заходя в комнату, открывает ящик с номером, который ему присвоили. Если там его имени нет, то он открывает ящик с номером, который он нашел») для 100 ящиков даёт P&#8776;0,33
↓↓ 0 ↑↑   d1ma (0 / 7)   2009-05-14 02:20   «« #11 »»   Ответить


Или нет
А теперь получается 0,299
↓↓ 0 ↑↑   d1ma (0 / 7)   2009-05-14 03:38   «« #12 »»   Ответить


Я не понял...
ZERO объясни пожалуйсто почему шанс угадать увелич???
↓↓ 0 ↑↑   Givchik3316 (0 / 31)   2009-08-13 16:12   «« #13 »»   Ответить


И класно будет узникам, если охрана специально положит в яшики бумажни с номером= номер ящика+1
%)))
↓↓ 0 ↑↑   Givchik3316 (0 / 31)   2009-08-13 16:21   «« #14 »»   Ответить


50%
Все узники выбирают первые 50 ящиков
↓↓ 0 ↑↑   amur27 (0 / 1)   2010-09-23 12:26   «« #15 »»   Ответить


как мудро
вы хоть условие читали? какие еще номера ящика+1?? там имена узников лежат! какой спрашивается охранник знает кто там кому присвоил какой то номер?
↓↓ 0 ↑↑   lavsvip (-124 / 40)   2010-10-18 16:50   «« #16 »»   Ответить


При любом N, вероятность не опустится меньше 30,68%
Если конечно открывать с умом, как правильно предлагалось выше (распределить по ящику на каждого и открывать только ящики найденных имён).
При дезорганиованном открытии, вероятность спастить = 1/(2^N) - практически невозможно для 100... С практической точки зрения, узники должны быть в таком унынии, что вряд ли будут мелочиться на тему "не хотелось бы потратить попытку и открыть ящик, в котором кто-то уже нашёл своё имя".

Очень интересная задача, дающая повод для интересных размышлений. Поэтому универсальную формулу, приводить не буду.
↓↓ 0 ↑↑   SergeyASh (4 / 36)   2010-12-01 19:50   «« #17 »»   Ответить


А для N=100 будет ~31,18%
↓↓ 0 ↑↑   SergeyASh (4 / 36)   2010-12-01 20:15   «« #18 »»   Ответить


метод Zero не работает
там же имена, а не номера, блин

мой метод даёт просто до безобразия, но дает только ~13% (всё же больше 1/(2^100) )
↓↓ −5 ↑↑   Sergio471 (-5 / 2)   2011-02-02 18:21   «« #19 »»   Ответить


для того им и даётся полчаса — чтоб присвоить имени номер.
↓↓ +5 ↑↑   Никола (10 / 2)   2014-07-11 03:01   «« #22 »»   Ответить


даёт решение*

если интересно, могу написать )
↓↓ 0 ↑↑   Sergio471 (-5 / 2)   2011-02-02 18:22   «« #20 »»   Ответить


Напиши пожалуйста, очень хочется узнать. Сам пробовал решить — не получается.
↓↓ 0 ↑↑   Илья (0 / 1)   2014-01-13 05:13   «« #21 »»   Ответить


Если каждый из узников будет открывать первые пятьдесят, то будет 50% от 100
↓↓ 0 ↑↑   Стасяндр (0 / 3)   2016-04-27 21:33   «« #23 »»   Ответить


А ещё лучше поочерёдно. Т.е. первые пятьдесят — последние пятьдесят.
↓↓ 0 ↑↑   Тёма (0 / 1)   2016-12-10 21:18   «« #24 »»   Ответить


узники должны присвоить себе порядковые номера. Заходя комнату, каждый начинает открывать ящики начиная со своего порядкового номера, узники с номерами после пятидесяти, пройдя до сотого ящика, возвращаются к первому и так далее. Вероятность найти свой номер будет возрастать от 50% у первого до 100% у сотого узника
↓↓ 0 ↑↑   галим (0 / 2)   2018-08-14 11:50   «« #25   Ответить



© 2006-2024   Авторы