Проект основателей компании «Ваш репетитор»
ERUDITOR.RU

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

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

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

Обсуждение


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


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


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


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


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

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

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


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


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


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


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


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


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


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


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


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


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


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

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


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


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

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


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


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

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


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


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


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



Ваше имя
Email
Текст ответа
© 2006-2017   Авторы