Pull to refresh

Comments 55

Можно ли доказать, что не существует лучшей стратегии?
Да, стратегия в пределе оптимальна, но результат не столь тривиален, как сама стратегия. Доказательство можно найти в Eugene Curtin and Max Warshauer, The locker puzzle, The Mathematical Intelligencer, 28.1.
Данная стратегия как нибудь используется в каких-либо алгоритмах? Базах данных?
Я не согласен с вот этой частью:
Если цепочка длиннее, чем 50 коробок, заключенные, имеющие номера из этих цепочек провалят испытание — и все заключенные будут мертвы.


Вполне может быть такое, что цепочка длиннее 50 коробок, но заключенный начинает не с её конца, а с какого-то положения Х, от которого до его номера может быть менее 50 коробок. Т.е. у «красных» столбиков справа на вашем графике на самом деле должна быть некоторая зелёная часть и некоторая красная.
Заключённый всегда начинает с конца, иначе как он попадёт на нужную цепочку?
Но ведь это начала цепочки только с точки наблюдателя-заключенного, когда как его номер может быть далеко не первым в цепочке.
Определение цепочки и способ выбора первого элемента говорит, что в цепочке с количеством узлов L заключенный найдет свой номер точно на попытке номер L.
Да, я уже даже успел тест написать пока это понял :)
Даёт 31.1759% на миллионе экспериментов.
Ваш пример с «тёмным» помощником: gist.github.com/h4tr3d/d79e2e7def7a907f473f

Забавно, что если исправить только одну длинную цепочку, то вероятность повышается до 33%
Стало интересно, та же история на Python:
Функционально: gist
Объектно: gist
Может дальше ещё на каких языках предложат?
ВСЕ заключенные должны пройти испытание успешно
madskillz
image


Но как заметили ниже, заключенный начинает же с конца по логике вещей.
UFO just landed and posted this here
Там же написно что вы начинаете с коробки, соответствующей вашему номеру. То есть вы придете к коробке со своим номером в последнюю очередь перед замыканием цепочки. Поэтому и шанса спастись также не будет
При правильном нахождении своего номера — коробка убирается или остается?
После открытия коробки заключенным и проверки им таблички она помещается обратно в коробку и крышка снова закрывается
В абсолютных величинах это ничего бы не изменило, т.к. первый заключенный имел бы шансы 31.18% и никак больше. Т.е. наименьший шанс успеха среди отдельно взятого заключенного определяет шанс успеха для всех. + это могло бы разрушить цепочку, что только снижает шансы на успех в перспективе, но так как я гуманитарий, то точно сказать не могу.
это могло бы разрушить цепочку, что только снижает шансы на успех в перспективе
Это не только гарантированно разрушит цепочку, разумеется, но и не даст многим даже начать этот алгоритм, т.к. коробки с их номером уже нету, убрали с чьим-то другим номером.
В абсолютных величинах это ничего бы не изменило, т.к. первый заключенный имел бы шансы 31.18% и никак больше.

У первого заключённого должно быть больше шансов, поскольку второе утверждение более слабое
1. нет ни одной последовательности, длиной больше 50
2. длина первой последовательности больше 50
Как, вы ещё не смотрите MinutePhysics? Тогда я просто оставлю это здесь:
Чуть более гуманная задача ))
>> Если максимальная длина самой длинной цепочки меньше, чем 50 коробок, тогда все заключенные пройдут испытание!
А если в первой цепочке на 45 коробок не оказалось искомого номера?
Значит это не цепочка, раз нет таблички с номером первой коробки.
Значит мы никак не можем попасть в эту цепочку, следуя описанному в статье алгоритму.
Я долго думал, что в этой задаче мне не нравится и понял. Это даже не то, что вероятность успеха всего 31 процент, черт с ней. Это то, что эту вероятность определяют не заключенные и не случайность, а тюремщик. Если он изначально разложит коробки в цепочку длиной 100 — все умрут, нет никаких алгоритмов спасения. Т.е. это уже не такие себе «логические шахматы на выживание» получаются, а игра маньяка с жертвами.
все умрут, нет никаких алгоритмов спасения
На каждого хитрого маньяка найдется «дополнительный вопрос» из условия.
Ну можно попробовать решить задачу поиска решения оптимала в этом случае.
Если точно известно что тюремщик сволочь знает эту стратегию и наверняка сделает цепочку длиной больше 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)?
Если изначальное распределение было равномерным, то и новое распределение будет равномерным и вероятность победы не изменится. Иначе надо считать в зависимости от распределения:)
Можно просто менять цифры местами: 39 карточка ведет к 93 коробке, 1 к 10, 10 к 1. А 100 оставляем без изменений. Не придется учить заключенных считать остатки от деления :)
А где вы видели остаток от деления? Если вы про (k+m)%n — то это примитивнейший случай, сводится к одному вычитанию.
О, ура, гармония вернулась в мир. Всё снова определяется логикой и математикой, а не злым умыслом. Думаю, Ваш комментарий надо бы добавить в статью, поскольку он реально повышает вероятность выживания в случае тюремщика со злым умыслом.
Блин, у меня мозг взорвался, может кто то сможет подсказать, какова вероятность, что 1ый заключенный поменяв 2 коробках таблички местами гарантирует 100% вероятность свободы и с какой вероятностью он может этой заменой создать цепочку длиннее 50?

Или я затупил и менять местами нужно после обнаружения цепочки длиннее 50?
Вы неправильно поняли условия второй задачи. Таблички меняет не заключенный, их меняет третье лицо. Он может свободно открывать любые коробки и смотреть на их содержимое — потому что его никто не видит.
UFO just landed and posted this here
Местами таблички менять нельзя;
Йода магистр согласен с вами :)
UFO just landed and posted this here
Спасибо за статью. Интересная задача, интересное решение.

Для тех, кто подзабыл теорию вероятностей, как я, начинается небольшой ступор с места «Еще немного математики». Напомните, что означает (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).
Спасибо за разъяснения. Теперь понятно. Для наглядности не хватает визуализации :) В ролике выше этого не показано — именно вычисление 31 процента.
Немного не понял, как вероятность на спасение может быть больше 0 при наличии цепочки в 51 коробку? Ведь тогда 51 заключенный не дойдет до конца цепочки.
Никак. Вычисленная в статье вероятность — это вероятность отсутствия такой цепочки.
Ничего не написано про то, что нельзя двигать коробки. Можно было бы сделать, что бы заключённые по мере прохождения цепочки, выставляли коробки цепочки в отдельный ряд. И новый заключённый, который вошёл, увидел бы свой номер в отдельном ряду, взял бы предыдущую коробку с его номером, а если его коробка первая, то взял бы последнюю. Если в ней оказывался не его номер, то он бы продолжал выкладывать цепочку из коробок, которую не завершил предыдущий заключённый (особенно, на случай, если длина цепочки больше 50). В этом случае вероятность того, что заключённые спасутся будет сильно больше 50% — это вероятность, что первый заключённый, чей номер находится в цепочке длиной более 50 найдёт свой номер за 50 ходов.
По условию задачи, все заключенные должны найти свои номера. Согласно алгоритму они начинают с конца этой цепочки, выстраивание в ряд не поможет — выстраивающий её до своего номера не дойдет, т.к. цепочка длиннее 50 шагов.
Ваш способ поможет изменить время, но не вероятность прохождения для группы.
Это только первый заключённый, чей номер находится в цепочке больше 50. Если он за 50 попыток не найдёт свой номер, то все. Если найдёт, то ему лучше достроить цепочку до 50, что бы следующий заключённый из длинной цепочки достроил её менее, чем за 50 ходов, т.к. всего коробок 100, и длина самой длинной цепочки не может быть больше 100.
Хотя если длина самой большой цепочки будет равна 100, то второй заключённый тоже может не найти свой номер (в случае если его нет в уже собранной последовательности), т.к. он сможет добавить в последовательность только 49 коробок из-за того, что ему придётся открыть одну коробку из уже собранной последовательности.
А я правильно понимаю, что есть дополнительное условие, при котором описанная стратегия работает, и согласно нему коробка не может указывать сама на себя?
Насколько я понял, это не обязательно. Если коробка указывает сама на себя, то мы имеем очень короткую цепочку из одной коробки. Заключённый заходит, берёт свою табличку, уходит. В дальнейшем эта коробка не участвует в работе.
Точно. Всё сложилось, спасибо.
Огромное спасибо за задачку. Прочитал начало статьи в момент ее публикации, и заставил себя не смотреть решение. Решал задачу неделю. Заставил жену и еще пару друзей прочитать решение, чтобы удостовериться, что нет никаких подвохов.
Если бы не жена, которая угрожала, что перестанет уважать, я бы сдался)

Only those users with full accounts are able to leave comments. Log in, please.

Articles