Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 55
Можно ли доказать, что не существует лучшей стратегии?
Эта задача в несколько другом виде уже публиковалась на Хабре в сентябре 2014 «Две красивые задачи по алгоритмам», там было обсуждение алгоритма, правда строгого доказательства вроде не было.
Да, стратегия в пределе оптимальна, но результат не столь тривиален, как сама стратегия. Доказательство можно найти в Eugene Curtin and Max Warshauer, The locker puzzle, The Mathematical Intelligencer, 28.1.
Данная стратегия как нибудь используется в каких-либо алгоритмах? Базах данных?
Я не согласен с вот этой частью:
Вполне может быть такое, что цепочка длиннее 50 коробок, но заключенный начинает не с её конца, а с какого-то положения Х, от которого до его номера может быть менее 50 коробок. Т.е. у «красных» столбиков справа на вашем графике на самом деле должна быть некоторая зелёная часть и некоторая красная.
Если цепочка длиннее, чем 50 коробок, заключенные, имеющие номера из этих цепочек провалят испытание — и все заключенные будут мертвы.
Вполне может быть такое, что цепочка длиннее 50 коробок, но заключенный начинает не с её конца, а с какого-то положения Х, от которого до его номера может быть менее 50 коробок. Т.е. у «красных» столбиков справа на вашем графике на самом деле должна быть некоторая зелёная часть и некоторая красная.
Заключённый всегда начинает с конца, иначе как он попадёт на нужную цепочку?
Но ведь это начала цепочки только с точки наблюдателя-заключенного, когда как его номер может быть далеко не первым в цепочке.
Да, я уже даже успел тест написать пока это понял :)
Даёт 31.1759% на миллионе экспериментов.
Даёт 31.1759% на миллионе экспериментов.
Ваш пример с «тёмным» помощником: gist.github.com/h4tr3d/d79e2e7def7a907f473f
Забавно, что если исправить только одну длинную цепочку, то вероятность повышается до 33%
Забавно, что если исправить только одну длинную цепочку, то вероятность повышается до 33%
ВСЕ заключенные должны пройти испытание успешно
madskillz
Но как заметили ниже, заключенный начинает же с конца по логике вещей.
Там же написно что вы начинаете с коробки, соответствующей вашему номеру. То есть вы придете к коробке со своим номером в последнюю очередь перед замыканием цепочки. Поэтому и шанса спастись также не будет
При правильном нахождении своего номера — коробка убирается или остается?
После открытия коробки заключенным и проверки им таблички она помещается обратно в коробку и крышка снова закрывается
В абсолютных величинах это ничего бы не изменило, т.к. первый заключенный имел бы шансы 31.18% и никак больше. Т.е. наименьший шанс успеха среди отдельно взятого заключенного определяет шанс успеха для всех. + это могло бы разрушить цепочку, что только снижает шансы на успех в перспективе, но так как я гуманитарий, то точно сказать не могу.
это могло бы разрушить цепочку, что только снижает шансы на успех в перспективеЭто не только гарантированно разрушит цепочку, разумеется, но и не даст многим даже начать этот алгоритм, т.к. коробки с их номером уже нету, убрали с чьим-то другим номером.
В абсолютных величинах это ничего бы не изменило, т.к. первый заключенный имел бы шансы 31.18% и никак больше.
У первого заключённого должно быть больше шансов, поскольку второе утверждение более слабое
1. нет ни одной последовательности, длиной больше 50
2. длина первой последовательности больше 50
Как, вы ещё не смотрите MinutePhysics? Тогда я просто оставлю это здесь:
>> Если максимальная длина самой длинной цепочки меньше, чем 50 коробок, тогда все заключенные пройдут испытание!
А если в первой цепочке на 45 коробок не оказалось искомого номера?
А если в первой цепочке на 45 коробок не оказалось искомого номера?
Я долго думал, что в этой задаче мне не нравится и понял. Это даже не то, что вероятность успеха всего 31 процент, черт с ней. Это то, что эту вероятность определяют не заключенные и не случайность, а тюремщик. Если он изначально разложит коробки в цепочку длиной 100 — все умрут, нет никаких алгоритмов спасения. Т.е. это уже не такие себе «логические шахматы на выживание» получаются, а игра маньяка с жертвами.
все умрут, нет никаких алгоритмов спасенияНа каждого хитрого маньяка найдется «дополнительный вопрос» из условия.
Ну можно попробовать решить задачу поиска решения оптимала в этом случае.
Если точно известно что тюремщик сволочь знает эту стратегию и наверняка сделает цепочку длиной больше 50.
Не удивлюсь еслив этом случае вероятность спасения можно повысить.
Если точно известно что тюремщик сволочь знает эту стратегию и наверняка сделает цепочку длиной больше 50.
Не удивлюсь еслив этом случае вероятность спасения можно повысить.
Можно выбрать заранее некоторую перестановку — и применять ее каждый раз перед выбором очередной коробки. Иными словами, получаем измененный алгоритм вида «открывать коробку с номером f(x), где x — табличка из прошлой коробки либо номер самого заключенного для первой итерации». Это эквивалентно тому, как если бы перед экспериментом все коробки случайно перемешали.
Если тюремщик будет всегда складывать в самую длинную цепочку типа 1->2->3->....->n->1, то никакая перестановка не поможет.
Почему? Перестановка /k->k+1/ даст 2 цикла по n/2 коробок, а перестановка /k->k-1/ даст после композиции тривиальную.
В общем случае, композиция случайной перестановки и фиксированной — полностью случайна — тюремщик не может сделать ничего (если только не подглядит перестановку, о которой договорились заключенные)
В общем случае, композиция случайной перестановки и фиксированной — полностью случайна — тюремщик не может сделать ничего (если только не подглядит перестановку, о которой договорились заключенные)
Да, согласен. Сначала немного не правильно вас понял.
Получается что если заключенные выберут рандомно число m и затем будут применять перестановку (k -> (k+m)%n), то получится неплохой рандомизированный алгоритм. Теперь надо пересчитать вероятность :)
Т.е. получается вопрос такой: какая вероятность что будет цепочка длиной 50 и более если число m выбрано случайно из промежутка [1..n)?
Получается что если заключенные выберут рандомно число m и затем будут применять перестановку (k -> (k+m)%n), то получится неплохой рандомизированный алгоритм. Теперь надо пересчитать вероятность :)
Т.е. получается вопрос такой: какая вероятность что будет цепочка длиной 50 и более если число m выбрано случайно из промежутка [1..n)?
Если изначальное распределение было равномерным, то и новое распределение будет равномерным и вероятность победы не изменится. Иначе надо считать в зависимости от распределения:)
Можно просто менять цифры местами: 39 карточка ведет к 93 коробке, 1 к 10, 10 к 1. А 100 оставляем без изменений. Не придется учить заключенных считать остатки от деления :)
О, ура, гармония вернулась в мир. Всё снова определяется логикой и математикой, а не злым умыслом. Думаю, Ваш комментарий надо бы добавить в статью, поскольку он реально повышает вероятность выживания в случае тюремщика со злым умыслом.
Блин, у меня мозг взорвался, может кто то сможет подсказать, какова вероятность, что 1ый заключенный поменяв 2 коробках таблички местами гарантирует 100% вероятность свободы и с какой вероятностью он может этой заменой создать цепочку длиннее 50?
Или я затупил и менять местами нужно после обнаружения цепочки длиннее 50?
Или я затупил и менять местами нужно после обнаружения цепочки длиннее 50?
Местами таблички менять нельзя;
Йода магистр согласен с вами :)
Йода магистр согласен с вами :)
Спасибо за статью. Интересная задача, интересное решение.
Для тех, кто подзабыл теорию вероятностей, как я, начинается небольшой ступор с места «Еще немного математики». Напомните, что означает (100 l) на картинке? Как получили, что 100! способов раскладок табличек вероятность существования цепочки длиной l (в нашем случае l > 50) = 1/l? То есть, допустим, если мне нужна цепочка только длинной l = 51, то вероятность её появления 1/51? Спасибо.
Для тех, кто подзабыл теорию вероятностей, как я, начинается небольшой ступор с места «Еще немного математики». Напомните, что означает (100 l) на картинке? Как получили, что 100! способов раскладок табличек вероятность существования цепочки длиной l (в нашем случае l > 50) = 1/l? То есть, допустим, если мне нужна цепочка только длинной l = 51, то вероятность её появления 1/51? Спасибо.
(100 l) — число сочетаний из 100 по l, т.е. количество способов выбора l элементов из 100 без учета порядка, также обозначается как C_100^l. (тут в статье, видимо, опечатка — вероятность события никак не может быть числом больше единицы, а C_100^l при 50 < l < 100 больше единицы)
Всего есть 100! перестановок длины 100 (единицу отправляем на одно из 100 мест, двойку на одно из оставшихся 99 свободных, тройку на одно из 98 и т.д.)
Чтобы получить цепочку длины l > 50 нужно: выбрать элементы, из которых будет строиться цепочка — это можно сделать C_100^l способами; выбрать, как расположить элементы в цепочке — (l — 1)! способов (выбираем, в какой из l — 1 элементов переходит наименьший элемент цепочки, в какой из l-2 переходит этот и т.д. — последний элемент цепочки обязан переходить в первый); выбрать, как расположить элементы вне цепочки — (100 — l)! способов. Каждую перестановку мы посчитали ровно один раз, т.к. элементы, образующие цепочку, определяются однозначно.
Итого перестановок с цепочкой длины l: C_100^l * (l — 1)! * (100 — l)!
Т.е. C_n^k = n! / k! / (n-k)!, то C_100^l * (l — 1)! * (100 — l)! = 100! / l. Всего перестановок из 100 элементов 100!, так что вероятность наличия цепочки длины l равно 1 / l (для l > 50).
Всего есть 100! перестановок длины 100 (единицу отправляем на одно из 100 мест, двойку на одно из оставшихся 99 свободных, тройку на одно из 98 и т.д.)
Чтобы получить цепочку длины l > 50 нужно: выбрать элементы, из которых будет строиться цепочка — это можно сделать C_100^l способами; выбрать, как расположить элементы в цепочке — (l — 1)! способов (выбираем, в какой из l — 1 элементов переходит наименьший элемент цепочки, в какой из l-2 переходит этот и т.д. — последний элемент цепочки обязан переходить в первый); выбрать, как расположить элементы вне цепочки — (100 — l)! способов. Каждую перестановку мы посчитали ровно один раз, т.к. элементы, образующие цепочку, определяются однозначно.
Итого перестановок с цепочкой длины l: C_100^l * (l — 1)! * (100 — l)!
Т.е. C_n^k = n! / k! / (n-k)!, то C_100^l * (l — 1)! * (100 — l)! = 100! / l. Всего перестановок из 100 элементов 100!, так что вероятность наличия цепочки длины l равно 1 / l (для l > 50).
Немного не понял, как вероятность на спасение может быть больше 0 при наличии цепочки в 51 коробку? Ведь тогда 51 заключенный не дойдет до конца цепочки.
Ничего не написано про то, что нельзя двигать коробки. Можно было бы сделать, что бы заключённые по мере прохождения цепочки, выставляли коробки цепочки в отдельный ряд. И новый заключённый, который вошёл, увидел бы свой номер в отдельном ряду, взял бы предыдущую коробку с его номером, а если его коробка первая, то взял бы последнюю. Если в ней оказывался не его номер, то он бы продолжал выкладывать цепочку из коробок, которую не завершил предыдущий заключённый (особенно, на случай, если длина цепочки больше 50). В этом случае вероятность того, что заключённые спасутся будет сильно больше 50% — это вероятность, что первый заключённый, чей номер находится в цепочке длиной более 50 найдёт свой номер за 50 ходов.
По условию задачи, все заключенные должны найти свои номера. Согласно алгоритму они начинают с конца этой цепочки, выстраивание в ряд не поможет — выстраивающий её до своего номера не дойдет, т.к. цепочка длиннее 50 шагов.
Ваш способ поможет изменить время, но не вероятность прохождения для группы.
Ваш способ поможет изменить время, но не вероятность прохождения для группы.
Это только первый заключённый, чей номер находится в цепочке больше 50. Если он за 50 попыток не найдёт свой номер, то все. Если найдёт, то ему лучше достроить цепочку до 50, что бы следующий заключённый из длинной цепочки достроил её менее, чем за 50 ходов, т.к. всего коробок 100, и длина самой длинной цепочки не может быть больше 100.
Хотя если длина самой большой цепочки будет равна 100, то второй заключённый тоже может не найти свой номер (в случае если его нет в уже собранной последовательности), т.к. он сможет добавить в последовательность только 49 коробок из-за того, что ему придётся открыть одну коробку из уже собранной последовательности.
Хотя если длина самой большой цепочки будет равна 100, то второй заключённый тоже может не найти свой номер (в случае если его нет в уже собранной последовательности), т.к. он сможет добавить в последовательность только 49 коробок из-за того, что ему придётся открыть одну коробку из уже собранной последовательности.
А я правильно понимаю, что есть дополнительное условие, при котором описанная стратегия работает, и согласно нему коробка не может указывать сама на себя?
Огромное спасибо за задачку. Прочитал начало статьи в момент ее публикации, и заставил себя не смотреть решение. Решал задачу неделю. Заставил жену и еще пару друзей прочитать решение, чтобы удостовериться, что нет никаких подвохов.
Если бы не жена, которая угрожала, что перестанет уважать, я бы сдался)
Если бы не жена, которая угрожала, что перестанет уважать, я бы сдался)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Математическая задача о 100 коробках и спасении заключенных