100 коробок

Логические задачи

Модераторы: Азарапетыч, Администрация

100 коробок

Сообщение Gibby » 24 ноя 2015, 10:36

100 заключенным выдаются номера от 1 до 100.
Их по очереди заводят в комнату, где стоит 100 пронумерованных коробок.
Внутри каждой коробки находится случайный номер от 1 до 100 (все номера разные).
Каждый человек может открыть любые 50 коробок и посмотреть номер внутри. После этого он обязан вернуть комнату в первоначальное состояние (закрыть все коробки и т.д.)
Если хотя бы один заключенный за 50 попыток не найдет своего номера внутри коробки - всех заключенных казнят.
Если все заключенные найдут свои номера - все выйдут на свободу.

Помогите заключенным выработать оптимальную стратегию, которая даст максимальные шансы выхода на свободу.
Последний раз редактировалось Gibby 24 ноя 2015, 13:57, всего редактировалось 1 раз.
Аватара пользователя
Gibby
Писатель на заборах
Писатель на заборах
 
Сообщения: 152
Зарегистрирован: 03 окт 2012, 13:41

Re: 100 коробок

Сообщение Шшок » 24 ноя 2015, 10:41

Вопрос: каждый заключенный действует в первую очередь в свою пользу, или только в пользу всей группы? То есть, интерес каждого заключенного - спастись самому, или спасти как можно больше людей (пусть даже ценой собственной смерти)?
И еще: имеет ли право заключенный давать какие-либо сигналы (располагать коробки в каком-либо порядке, чтобы показать другим, что вот эти конкретные коробки он уже открывал, или что-то в этом духе)?
И еще: знает ли каждый зэк, какие номера у каждого другого зэка? И уходит ли каждый зэк из комнаты, или остается в ней до конца? И заводят ли зэков в комнату строго в порядке возрастания их номеров, или в случайном порядке?...

В общем, уточни условия, чтобы не оставалось места для лишних вопросов...
В борьбе бобра с козлом побеждает бобро. Или козло.
Аватара пользователя
Шшок
Акула пера
Акула пера
 
Сообщения: 8575
Зарегистрирован: 28 ноя 2003, 14:05
Откуда: С большой дороги.

Re: 100 коробок

Сообщение Gibby » 24 ноя 2015, 11:05

ОК

Все зэки изначально находятся в одной комнате. У них есть время, чтобы выработать совместную стратегию.
Они видят номера друг друга и заходят в комнату с коробками в порядке возрастания номеров.
После открытия 50 коробок зэк выходит из комнаты.
Выходя из комнаты с коробками он должен оставить ее в точности в том состоянии, в котором она была до его захода.
Выходит из комнаты он через другую дверь и с еще не вошедшими не может общаться.

Стратегия коллективная, т.е. максимизируется общий шанс, а не личный.

Задача сложная, так что я готов давать небольшие подсказки при необходимости :)
Аватара пользователя
Gibby
Писатель на заборах
Писатель на заборах
 
Сообщения: 152
Зарегистрирован: 03 окт 2012, 13:41

Re: 100 коробок

Сообщение Шшок » 24 ноя 2015, 11:20

Давай без ограничения общности допустим, что коробки стоят в ряд.

"Оставил в точности в том же состоянии"... Означает ли это ЧИСТО ВИЗУАЛЬНО в том же состоянии (то есть тот же ряд коробок, но коробки поменяли свои места в ряду)? Или он обязан оставить КАЖДУЮ КОРОБКУ строго на том же физическом месте, на котором она находилась до того?
В борьбе бобра с козлом побеждает бобро. Или козло.
Аватара пользователя
Шшок
Акула пера
Акула пера
 
Сообщения: 8575
Зарегистрирован: 28 ноя 2003, 14:05
Откуда: С большой дороги.

Re: 100 коробок

Сообщение Gibby » 24 ноя 2015, 11:34

Шшок писал(а):Давай без ограничения общности допустим, что коробки стоят в ряд.


Допустимо.

Шшок писал(а):"Оставил в точности в том же состоянии"... Означает ли это ЧИСТО ВИЗУАЛЬНО в том же состоянии (то есть тот же ряд коробок, но коробки поменяли свои места в ряду)? Или он обязан оставить КАЖДУЮ КОРОБКУ строго на том же физическом месте, на котором она находилась до того?


Строгое условие: в комнате с коробками нельзя оставить никакой информации о своих действиях в ней.
Аватара пользователя
Gibby
Писатель на заборах
Писатель на заборах
 
Сообщения: 152
Зарегистрирован: 03 окт 2012, 13:41

Re: 100 коробок

Сообщение Шшок » 24 ноя 2015, 12:04

Давай начнем рассуждения с того, что первому совершенно все равно, какие коробки открывать. Его шанс на выживание при любом раскладе и при любой стратегии равен 50%, и увеличить его он не может.
По условиям задачи каждый, кто уже открывал коробки, не в состоянии передать остальным НИКАКУЮ информацию. Это означает, что каждый зэк находится в равных условиях, и шанс КАЖДОГО ОТДЕЛЬНО ВЗЯТОГО зека равен 50%. И как при таких условиях можно увеличить КОЛЛЕКТИВНЫЕ шансы?
Или я все-таки чего-то недопонял в условии задачи?... Может, всем последующим все-таки сообщают, выжили ли предыдущие?
В борьбе бобра с козлом побеждает бобро. Или козло.
Аватара пользователя
Шшок
Акула пера
Акула пера
 
Сообщения: 8575
Зарегистрирован: 28 ноя 2003, 14:05
Откуда: С большой дороги.

Re: 100 коробок

Сообщение Шшок » 24 ноя 2015, 12:58

Если ВСЕ откроют одни и те же коробки, то на свободу выйдет ровно 50 человек. То есть, коллективный шанс будет строго равен индивидуальному шансу каждого зэка.
Если первые 50 зэков откроют первые 50 коробок, а остальные 50 откроют оставшиеся коробки, то на свободе может оказаться от нуля до 100 человек. Надо считать математическое ожидание количества спасшихся людей. Но будет ли оно при таком раскладе отличаться от 50? Тут нужен Дендр. Он наверняка сможет вывести формулу подсчета матожидания при этих условиях. Для меня эта задача непосильна.
Получается, что надо подобрать такую "комбинацию" при открывании коробок, чтобы матожидание количества спасшихся людей было бы максимальным.
Но зависит ли это матожидание от того, какую комбинацию разработают зэки? Существует ли такая комбинация, при которой матожидание будет больше 50?
В борьбе бобра с козлом побеждает бобро. Или козло.
Аватара пользователя
Шшок
Акула пера
Акула пера
 
Сообщения: 8575
Зарегистрирован: 28 ноя 2003, 14:05
Откуда: С большой дороги.

Re: 100 коробок

Сообщение Шшок » 24 ноя 2015, 13:28

Gibby писал(а):
Строгое условие: в комнате с коробками нельзя оставить никакой информации о своих действиях в ней.


Но ведь он же может оставить информацию о своих БУДУЩИХ действиях еще до того, как зайдет в комнату! Например, он может (при обсуждении стратегии) сказать: я открываю первые 50 коробок, а потом пять коробок с наименьшими обнаруженными номерами переставляю в конец ряда.
Потом он, переставив коробки в конец ряда, сдвигает ВЕСЬ РЯД в его первоначальное положение. Таким образом, В КОМНАТЕ не оставлено никакой информации, но все знают, что в конце ряда стоят 5 коробок с наименьшими обнаруженными первым зэком номерами.

ТАКОЕ ДОПУСТИМО, ИЛИ НЕТ? Ты можешь прямо, не виляя, ответить на этот вопрос?
В борьбе бобра с козлом побеждает бобро. Или козло.
Аватара пользователя
Шшок
Акула пера
Акула пера
 
Сообщения: 8575
Зарегистрирован: 28 ноя 2003, 14:05
Откуда: С большой дороги.

Re: 100 коробок

Сообщение Юляша » 24 ноя 2015, 14:01

Все уже было в этой ветке 8 лет назад.

Причем задача ставилась жестче: спасти всех!

http://forum.danetka.ru/viewtopic.php?f=14&t=7166
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3159
Зарегистрирован: 15 янв 2009, 12:32

Re: 100 коробок

Сообщение Gibby » 24 ноя 2015, 14:16

Дико извиняюсь, перечитал задачу - там несколько другое условие. Спасаются все только если все находят свой номер. Иначе всех казнят.

Извиняюсь, что не перепроверил условие, когда писал задачу. Все остальное верно.

Шшок писал(а):Давай начнем рассуждения с того, что первому совершенно все равно, какие коробки открывать. Его шанс на выживание при любом раскладе и при любой стратегии равен 50%, и увеличить его он не может.


Верно.

Шшок писал(а):По условиям задачи каждый, кто уже открывал коробки, не в состоянии передать остальным НИКАКУЮ информацию. Это означает, что каждый зэк находится в равных условиях, и шанс КАЖДОГО ОТДЕЛЬНО ВЗЯТОГО зека равен 50%.


С точки зрения зека - да

Шшок писал(а):И как при таких условиях можно увеличить КОЛЛЕКТИВНЫЕ шансы?
Или я все-таки чего-то недопонял в условии задачи?... Может, всем последующим все-таки сообщают, выжили ли предыдущие?


Коллективные шансы можно увеличить, выработав правильную стратегию.


Шшок писал(а):Но ведь он же может оставить информацию о своих БУДУЩИХ действиях еще до того, как зайдет в комнату! Например, он может (при обсуждении стратегии) сказать: я открываю первые 50 коробок, а потом пять коробок с наименьшими обнаруженными номерами переставляю в конец ряда. Потом он, переставив коробки в конец ряда, сдвигает ВЕСЬ РЯД в его первоначальное положение. Таким образом, В КОМНАТЕ не оставлено никакой информации, но все знают, что в конце ряда стоят 5 коробок с наименьшими обнаруженными первым зэком номерами.


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

Шшок писал(а):ТАКОЕ ДОПУСТИМО, ИЛИ НЕТ? Ты можешь прямо, не виляя, ответить на этот вопрос?


Прямо отвечаю - меняя порядок коробок человек оставляет в комнате информацию. Это запрещено.
Последний раз редактировалось Gibby 24 ноя 2015, 14:25, всего редактировалось 1 раз.
Аватара пользователя
Gibby
Писатель на заборах
Писатель на заборах
 
Сообщения: 152
Зарегистрирован: 03 окт 2012, 13:41

Re: 100 коробок

Сообщение Gibby » 24 ноя 2015, 14:18

Юляша писал(а):Все уже было в этой ветке 8 лет назад.

Причем задача ставилась жестче: спасти всех!

http://forum.danetka.ru/viewtopic.php?f=14&t=7166


Эх, надо было посмотреть по поиску ](*,)
Аватара пользователя
Gibby
Писатель на заборах
Писатель на заборах
 
Сообщения: 152
Зарегистрирован: 03 окт 2012, 13:41

Re: 100 коробок

Сообщение Шшок » 24 ноя 2015, 15:12

Но еще предстоит как-то доказать, что алгоритм той задачи годится и для этой задачки. Здесь ведь требуется найти тактику, при которой максимизируется матожидание количества выживших гномов, а не вероятность того, что выживут ВСЕ. Разве это одно и то же?
В борьбе бобра с козлом побеждает бобро. Или козло.
Аватара пользователя
Шшок
Акула пера
Акула пера
 
Сообщения: 8575
Зарегистрирован: 28 ноя 2003, 14:05
Откуда: С большой дороги.

Re: 100 коробок

Сообщение Gibby » 24 ноя 2015, 15:23

Шшок писал(а):Но еще предстоит как-то доказать, что алгоритм той задачи годится и для этой задачки. Здесь ведь требуется найти тактику, при которой максимизируется матожидание количества выживших гномов, а не вероятность того, что выживут ВСЕ. Разве это одно и то же?

Прочитай выше. Это я в условии напутал. Задача та же самая (даже проще, потому что тут зеки уже пронумерованы).
Аватара пользователя
Gibby
Писатель на заборах
Писатель на заборах
 
Сообщения: 152
Зарегистрирован: 03 окт 2012, 13:41

Re: 100 коробок

Сообщение Шшок » 24 ноя 2015, 15:36

Да, извини, прошляпил твой пост.
Тем не менее, задачка в твоей формулировке тоже очень интересна. Другой вопрос, что мы не знаем, имеет ли она решение. Тут нужны Дендр и Юляша.
Короче, надо выработать коллективную стратегию, направленную на максимизацию количества выживших. Кто нашел свой номер, тот выживает. И каждый действует не с целью спастись самому, а с целью спасти как можно больше людей.
Ясно, что 50 человек спасутся с вероятностью 100%. Есть ли стратегия, при которой матожидание количества спасшихся превысит 50?
В борьбе бобра с козлом побеждает бобро. Или козло.
Аватара пользователя
Шшок
Акула пера
Акула пера
 
Сообщения: 8575
Зарегистрирован: 28 ноя 2003, 14:05
Откуда: С большой дороги.

Re: 100 коробок

Сообщение Gibby » 24 ноя 2015, 16:53

Шшок писал(а):Ясно, что 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+ элемента. Но не факт, что само это знание не дает лучшей стратегии.
Аватара пользователя
Gibby
Писатель на заборах
Писатель на заборах
 
Сообщения: 152
Зарегистрирован: 03 окт 2012, 13:41

След.

Вернуться в Задачки

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2

cron