100 коробок
Модераторы: Азарапетыч, Администрация
-
- Писатель на заборах
- Сообщения: 152
- Зарегистрирован: 03 окт 2012, 13:41
100 коробок
100 заключенным выдаются номера от 1 до 100.
Их по очереди заводят в комнату, где стоит 100 пронумерованных коробок.
Внутри каждой коробки находится случайный номер от 1 до 100 (все номера разные).
Каждый человек может открыть любые 50 коробок и посмотреть номер внутри. После этого он обязан вернуть комнату в первоначальное состояние (закрыть все коробки и т.д.)
Если хотя бы один заключенный за 50 попыток не найдет своего номера внутри коробки - всех заключенных казнят.
Если все заключенные найдут свои номера - все выйдут на свободу.
Помогите заключенным выработать оптимальную стратегию, которая даст максимальные шансы выхода на свободу.
Их по очереди заводят в комнату, где стоит 100 пронумерованных коробок.
Внутри каждой коробки находится случайный номер от 1 до 100 (все номера разные).
Каждый человек может открыть любые 50 коробок и посмотреть номер внутри. После этого он обязан вернуть комнату в первоначальное состояние (закрыть все коробки и т.д.)
Если хотя бы один заключенный за 50 попыток не найдет своего номера внутри коробки - всех заключенных казнят.
Если все заключенные найдут свои номера - все выйдут на свободу.
Помогите заключенным выработать оптимальную стратегию, которая даст максимальные шансы выхода на свободу.
Последний раз редактировалось Gibby 24 ноя 2015, 13:57, всего редактировалось 1 раз.
-
- Акула пера
- Сообщения: 9096
- Зарегистрирован: 28 ноя 2003, 14:05
- Пол: Мужской
- Откуда: С большой дороги.
Re: 100 коробок
Вопрос: каждый заключенный действует в первую очередь в свою пользу, или только в пользу всей группы? То есть, интерес каждого заключенного - спастись самому, или спасти как можно больше людей (пусть даже ценой собственной смерти)?
И еще: имеет ли право заключенный давать какие-либо сигналы (располагать коробки в каком-либо порядке, чтобы показать другим, что вот эти конкретные коробки он уже открывал, или что-то в этом духе)?
И еще: знает ли каждый зэк, какие номера у каждого другого зэка? И уходит ли каждый зэк из комнаты, или остается в ней до конца? И заводят ли зэков в комнату строго в порядке возрастания их номеров, или в случайном порядке?...
В общем, уточни условия, чтобы не оставалось места для лишних вопросов...
И еще: имеет ли право заключенный давать какие-либо сигналы (располагать коробки в каком-либо порядке, чтобы показать другим, что вот эти конкретные коробки он уже открывал, или что-то в этом духе)?
И еще: знает ли каждый зэк, какие номера у каждого другого зэка? И уходит ли каждый зэк из комнаты, или остается в ней до конца? И заводят ли зэков в комнату строго в порядке возрастания их номеров, или в случайном порядке?...
В общем, уточни условия, чтобы не оставалось места для лишних вопросов...
В борьбе бобра с козлом побеждает бобро. Или козло.
-
- Писатель на заборах
- Сообщения: 152
- Зарегистрирован: 03 окт 2012, 13:41
Re: 100 коробок
ОК
Все зэки изначально находятся в одной комнате. У них есть время, чтобы выработать совместную стратегию.
Они видят номера друг друга и заходят в комнату с коробками в порядке возрастания номеров.
После открытия 50 коробок зэк выходит из комнаты.
Выходя из комнаты с коробками он должен оставить ее в точности в том состоянии, в котором она была до его захода.
Выходит из комнаты он через другую дверь и с еще не вошедшими не может общаться.
Стратегия коллективная, т.е. максимизируется общий шанс, а не личный.
Задача сложная, так что я готов давать небольшие подсказки при необходимости
Все зэки изначально находятся в одной комнате. У них есть время, чтобы выработать совместную стратегию.
Они видят номера друг друга и заходят в комнату с коробками в порядке возрастания номеров.
После открытия 50 коробок зэк выходит из комнаты.
Выходя из комнаты с коробками он должен оставить ее в точности в том состоянии, в котором она была до его захода.
Выходит из комнаты он через другую дверь и с еще не вошедшими не может общаться.
Стратегия коллективная, т.е. максимизируется общий шанс, а не личный.
Задача сложная, так что я готов давать небольшие подсказки при необходимости
-
- Акула пера
- Сообщения: 9096
- Зарегистрирован: 28 ноя 2003, 14:05
- Пол: Мужской
- Откуда: С большой дороги.
Re: 100 коробок
Давай без ограничения общности допустим, что коробки стоят в ряд.
"Оставил в точности в том же состоянии"... Означает ли это ЧИСТО ВИЗУАЛЬНО в том же состоянии (то есть тот же ряд коробок, но коробки поменяли свои места в ряду)? Или он обязан оставить КАЖДУЮ КОРОБКУ строго на том же физическом месте, на котором она находилась до того?
"Оставил в точности в том же состоянии"... Означает ли это ЧИСТО ВИЗУАЛЬНО в том же состоянии (то есть тот же ряд коробок, но коробки поменяли свои места в ряду)? Или он обязан оставить КАЖДУЮ КОРОБКУ строго на том же физическом месте, на котором она находилась до того?
В борьбе бобра с козлом побеждает бобро. Или козло.
-
- Писатель на заборах
- Сообщения: 152
- Зарегистрирован: 03 окт 2012, 13:41
Re: 100 коробок
Допустимо.Шшок писал(а):Давай без ограничения общности допустим, что коробки стоят в ряд.
Строгое условие: в комнате с коробками нельзя оставить никакой информации о своих действиях в ней.Шшок писал(а):"Оставил в точности в том же состоянии"... Означает ли это ЧИСТО ВИЗУАЛЬНО в том же состоянии (то есть тот же ряд коробок, но коробки поменяли свои места в ряду)? Или он обязан оставить КАЖДУЮ КОРОБКУ строго на том же физическом месте, на котором она находилась до того?
-
- Акула пера
- Сообщения: 9096
- Зарегистрирован: 28 ноя 2003, 14:05
- Пол: Мужской
- Откуда: С большой дороги.
Re: 100 коробок
Давай начнем рассуждения с того, что первому совершенно все равно, какие коробки открывать. Его шанс на выживание при любом раскладе и при любой стратегии равен 50%, и увеличить его он не может.
По условиям задачи каждый, кто уже открывал коробки, не в состоянии передать остальным НИКАКУЮ информацию. Это означает, что каждый зэк находится в равных условиях, и шанс КАЖДОГО ОТДЕЛЬНО ВЗЯТОГО зека равен 50%. И как при таких условиях можно увеличить КОЛЛЕКТИВНЫЕ шансы?
Или я все-таки чего-то недопонял в условии задачи?... Может, всем последующим все-таки сообщают, выжили ли предыдущие?
По условиям задачи каждый, кто уже открывал коробки, не в состоянии передать остальным НИКАКУЮ информацию. Это означает, что каждый зэк находится в равных условиях, и шанс КАЖДОГО ОТДЕЛЬНО ВЗЯТОГО зека равен 50%. И как при таких условиях можно увеличить КОЛЛЕКТИВНЫЕ шансы?
Или я все-таки чего-то недопонял в условии задачи?... Может, всем последующим все-таки сообщают, выжили ли предыдущие?
В борьбе бобра с козлом побеждает бобро. Или козло.
-
- Акула пера
- Сообщения: 9096
- Зарегистрирован: 28 ноя 2003, 14:05
- Пол: Мужской
- Откуда: С большой дороги.
Re: 100 коробок
Если ВСЕ откроют одни и те же коробки, то на свободу выйдет ровно 50 человек. То есть, коллективный шанс будет строго равен индивидуальному шансу каждого зэка.
Если первые 50 зэков откроют первые 50 коробок, а остальные 50 откроют оставшиеся коробки, то на свободе может оказаться от нуля до 100 человек. Надо считать математическое ожидание количества спасшихся людей. Но будет ли оно при таком раскладе отличаться от 50? Тут нужен Дендр. Он наверняка сможет вывести формулу подсчета матожидания при этих условиях. Для меня эта задача непосильна.
Получается, что надо подобрать такую "комбинацию" при открывании коробок, чтобы матожидание количества спасшихся людей было бы максимальным.
Но зависит ли это матожидание от того, какую комбинацию разработают зэки? Существует ли такая комбинация, при которой матожидание будет больше 50?
Если первые 50 зэков откроют первые 50 коробок, а остальные 50 откроют оставшиеся коробки, то на свободе может оказаться от нуля до 100 человек. Надо считать математическое ожидание количества спасшихся людей. Но будет ли оно при таком раскладе отличаться от 50? Тут нужен Дендр. Он наверняка сможет вывести формулу подсчета матожидания при этих условиях. Для меня эта задача непосильна.
Получается, что надо подобрать такую "комбинацию" при открывании коробок, чтобы матожидание количества спасшихся людей было бы максимальным.
Но зависит ли это матожидание от того, какую комбинацию разработают зэки? Существует ли такая комбинация, при которой матожидание будет больше 50?
В борьбе бобра с козлом побеждает бобро. Или козло.
-
- Акула пера
- Сообщения: 9096
- Зарегистрирован: 28 ноя 2003, 14:05
- Пол: Мужской
- Откуда: С большой дороги.
Re: 100 коробок
Но ведь он же может оставить информацию о своих БУДУЩИХ действиях еще до того, как зайдет в комнату! Например, он может (при обсуждении стратегии) сказать: я открываю первые 50 коробок, а потом пять коробок с наименьшими обнаруженными номерами переставляю в конец ряда.Gibby писал(а):
Строгое условие: в комнате с коробками нельзя оставить никакой информации о своих действиях в ней.
Потом он, переставив коробки в конец ряда, сдвигает ВЕСЬ РЯД в его первоначальное положение. Таким образом, В КОМНАТЕ не оставлено никакой информации, но все знают, что в конце ряда стоят 5 коробок с наименьшими обнаруженными первым зэком номерами.
ТАКОЕ ДОПУСТИМО, ИЛИ НЕТ? Ты можешь прямо, не виляя, ответить на этот вопрос?
В борьбе бобра с козлом побеждает бобро. Или козло.
-
- Популярный автор
- Сообщения: 3359
- Зарегистрирован: 15 янв 2009, 12:32
- Пол: Женский
Re: 100 коробок
Все уже было в этой ветке 8 лет назад.
Причем задача ставилась жестче: спасти всех!
viewtopic.php?f=14&t=7166
Причем задача ставилась жестче: спасти всех!
viewtopic.php?f=14&t=7166
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
-
- Писатель на заборах
- Сообщения: 152
- Зарегистрирован: 03 окт 2012, 13:41
Re: 100 коробок
Дико извиняюсь, перечитал задачу - там несколько другое условие. Спасаются все только если все находят свой номер. Иначе всех казнят.
Извиняюсь, что не перепроверил условие, когда писал задачу. Все остальное верно.
Извиняюсь, что не перепроверил условие, когда писал задачу. Все остальное верно.
Верно.Шшок писал(а):Давай начнем рассуждения с того, что первому совершенно все равно, какие коробки открывать. Его шанс на выживание при любом раскладе и при любой стратегии равен 50%, и увеличить его он не может.
С точки зрения зека - даШшок писал(а):По условиям задачи каждый, кто уже открывал коробки, не в состоянии передать остальным НИКАКУЮ информацию. Это означает, что каждый зэк находится в равных условиях, и шанс КАЖДОГО ОТДЕЛЬНО ВЗЯТОГО зека равен 50%.
Коллективные шансы можно увеличить, выработав правильную стратегию.Шшок писал(а):И как при таких условиях можно увеличить КОЛЛЕКТИВНЫЕ шансы?
Или я все-таки чего-то недопонял в условии задачи?... Может, всем последующим все-таки сообщают, выжили ли предыдущие?
Перед выходом он должен вернуть комнату в то состояние, в котором она была до его входа. В том числе порядок коробок.Шшок писал(а):Но ведь он же может оставить информацию о своих БУДУЩИХ действиях еще до того, как зайдет в комнату! Например, он может (при обсуждении стратегии) сказать: я открываю первые 50 коробок, а потом пять коробок с наименьшими обнаруженными номерами переставляю в конец ряда. Потом он, переставив коробки в конец ряда, сдвигает ВЕСЬ РЯД в его первоначальное положение. Таким образом, В КОМНАТЕ не оставлено никакой информации, но все знают, что в конце ряда стоят 5 коробок с наименьшими обнаруженными первым зэком номерами.
Прямо отвечаю - меняя порядок коробок человек оставляет в комнате информацию. Это запрещено.Шшок писал(а):ТАКОЕ ДОПУСТИМО, ИЛИ НЕТ? Ты можешь прямо, не виляя, ответить на этот вопрос?
Последний раз редактировалось Gibby 24 ноя 2015, 14:25, всего редактировалось 1 раз.
-
- Писатель на заборах
- Сообщения: 152
- Зарегистрирован: 03 окт 2012, 13:41
Re: 100 коробок
Эх, надо было посмотреть по поискуЮляша писал(а):Все уже было в этой ветке 8 лет назад.
Причем задача ставилась жестче: спасти всех!
viewtopic.php?f=14&t=7166
-
- Акула пера
- Сообщения: 9096
- Зарегистрирован: 28 ноя 2003, 14:05
- Пол: Мужской
- Откуда: С большой дороги.
Re: 100 коробок
Но еще предстоит как-то доказать, что алгоритм той задачи годится и для этой задачки. Здесь ведь требуется найти тактику, при которой максимизируется матожидание количества выживших гномов, а не вероятность того, что выживут ВСЕ. Разве это одно и то же?
В борьбе бобра с козлом побеждает бобро. Или козло.
-
- Писатель на заборах
- Сообщения: 152
- Зарегистрирован: 03 окт 2012, 13:41
Re: 100 коробок
Прочитай выше. Это я в условии напутал. Задача та же самая (даже проще, потому что тут зеки уже пронумерованы).Шшок писал(а):Но еще предстоит как-то доказать, что алгоритм той задачи годится и для этой задачки. Здесь ведь требуется найти тактику, при которой максимизируется матожидание количества выживших гномов, а не вероятность того, что выживут ВСЕ. Разве это одно и то же?
-
- Акула пера
- Сообщения: 9096
- Зарегистрирован: 28 ноя 2003, 14:05
- Пол: Мужской
- Откуда: С большой дороги.
Re: 100 коробок
Да, извини, прошляпил твой пост.
Тем не менее, задачка в твоей формулировке тоже очень интересна. Другой вопрос, что мы не знаем, имеет ли она решение. Тут нужны Дендр и Юляша.
Короче, надо выработать коллективную стратегию, направленную на максимизацию количества выживших. Кто нашел свой номер, тот выживает. И каждый действует не с целью спастись самому, а с целью спасти как можно больше людей.
Ясно, что 50 человек спасутся с вероятностью 100%. Есть ли стратегия, при которой матожидание количества спасшихся превысит 50?
Тем не менее, задачка в твоей формулировке тоже очень интересна. Другой вопрос, что мы не знаем, имеет ли она решение. Тут нужны Дендр и Юляша.
Короче, надо выработать коллективную стратегию, направленную на максимизацию количества выживших. Кто нашел свой номер, тот выживает. И каждый действует не с целью спастись самому, а с целью спасти как можно больше людей.
Ясно, что 50 человек спасутся с вероятностью 100%. Есть ли стратегия, при которой матожидание количества спасшихся превысит 50?
В борьбе бобра с козлом побеждает бобро. Или козло.
-
- Писатель на заборах
- Сообщения: 152
- Зарегистрирован: 03 окт 2012, 13:41
Re: 100 коробок
Это не так.Шшок писал(а):Ясно, что 50 человек спасутся с вероятностью 100%.
Дело в том, что по такой стратегии либо спасутся все, либо погибнет 51 и более (все, кому не повезло попасть в длинную цепочку).
Индивидуальный шанс в этой стратегии - ровно 50%. Это легко находится.
Вероятность, что существует цепочка ровно в 51 элемент - 1/51. При этом погибнет 51 человек (все, кто попал в эту цепочку). Шанс оказаться в их числе - 51/100.
Аналогично для 52 шансы 1/52 и 52/100
Итого шанс погибнуть по этой стратегии:
1/51 * 51/100 + 1/52 * 52/100 + ... + 1/100 * 100/100 = 50 * 1/100 = 1/2
Потому что какую бы хитрую стратегию вы не выбрали, вы по большому счету все равно вытаскиваете 50 случайных чисел из 100. И ваши шансы точно 1/2. Просто в случае стратегии шансы оказываются взаимосвязанными. В точном соответствии с:
Можно такой интересный вариант задачи:
Тюремщик предлагает, чтобы карточки были разложены не случайно, а самим тюремщиком. Стоит ли принять его предложение, зная, что тюремщик хочет, чтобы заключенные проиграли? Очевидный ответ: нет, потому что он точно сделает цепочку из 51+ элемента. Но не факт, что само это знание не дает лучшей стратегии.