100 заключённых

По условию задачи в тюрьме находится 100 заключенных, каждый из которых имеет личный номер от 1 до 100. Тюремщик решает дать заключенным шанс на освобождение и предлагает пройти придуманное им испытание. Если все заключенные справятся, то они свободны, если хотя бы один провалится — всем увеличат срок в двое

Тюремщик идет в секретную комнату и подготавливает 100 коробок с крышками.
Коробки пронумерованы от 1 до 100

В каждую коробку он кладет табличку с нумерацией от 1 до 100. в произвольном порядке и закрывает крышкой

Заключенные не видят, как тюремщик выполняет все эти действия.

Соревнование начинается: тюремщик отводит каждого заключенного по одному в комнату с коробками и говорит, что он должен найти коробку, в которой будет находиться табличка с номером заключенного. Каждому разрешается открыть до 50-ти коробок из 100;
Если заключённый находит свой номер его отводят в другое помещение и с оставшимися он общается не может. Коробки опять закрывают и ведут следующего

если каждый из заключенных найдет свой номер, то заключенных отпустят, если хотя бы один из них не найдет свой номер за 50 попыток, то всем продлят срок

Вопрос как им победить?
------------------------------------------------------------------------------------------------------------

И второй вариант: с условием что разрешается пометить коробку в которой лежит номер заключённого который прошёл испытание.

Заключённые могут обсудить стратегию и выбрать, кто пойдет в комнату, и в какой последовательности.

0

оттуда цитата

Никто не перемешивает таблички между посещениями комнаты отдельными заключенными, так что мы можем использовать эту информацию.

Что за хренотеь? Это нарушение исходных условий.

0

Сообщение от titan4ik Это нарушение исходных условий.

Нет. Где там написано, что таблички перемешиваются?

0

ОК, быстро просмотрел, но идея понятна. Но и в этом случае считаю условия не вполне корректными. Если мы полагаем, что 100 заключенных смогут договориться о единой стратегии, то почему тюремщик не может подложить подлянку - разместить таблички так, чтобы заключенные при такой стратегии были бы обречены на поражение?

Сообщение от dimank666 В каждую коробку он кладет табличку с нумерацией от 1 до 100. в произвольном порядке и закрывает крышкой

В условиях некорректность - не в произвольном порядке, а в случайном порядке надо написать.
Ладно. Интересная задачка! Выходит, что я тупой) В заключенные не гожусь. Зато в тюремщики - в самый раз)))

Добавлено через 1 минуту
Мда... интересно!

Добавлено через 4 минуты
dimank666, I can, спасибо за тему и разъяснения! Последний раз так радовался, когда парадокс Монте-Хилла осознал)))

Добавлено через 2 минуты
Кстати, не все люди (с первого раза, по крайней мере) понимают суть парадокса Монте-Хилла. Я однажды пытался одному маститому ученому объяснить - не понял, как я ни старался. И даже обиделся на меня.

1

Сообщение от titan4ik почему тюремщик не может подложить подлянку

Не может по условию задачи

Сообщение от dimank666 в произвольном порядке

А так да. Свинья без особых хитростей подкладывается так: в первую коробку кладём табличку 2, во вторую -3, в третью 4 .... в сотую - 1.

0

Надо бы такие темы как-то помечать особо. Типа - Рекомендуется ВСЕМ! Золотой фонд!

0

Сообщение от titan4ik Надо бы такие темы как-то помечать особо. Типа - Рекомендуется ВСЕМ! Золотой фонд!

пробегись по картинкам загадкам тут
мне особенно нравится 102

0

А как практически можно использовать этот "метод выхода из тюрьмы посредством коробочек". Я имею ввиду, где бы это можно было применить и как?

0

Сообщение от titan4ik Я имею ввиду, где бы это можно было применить и как?

В пивнушке можно мужикам загадать.

Добавлено через 59 секунд
Только там хрен кто поверит

0

Сообщение от dimank666 пробегись по картинкам загадкам тут мне особенно нравится 102

Я этого вообще не понимаю. Не интересно. Может в мое время в это не играли) Короче, я не в теме.

0

Сообщение от titan4ik А как практически можно использовать этот "метод выхода из тюрьмы посредством коробочек". Я имею ввиду, где бы это можно было применить и как?

обычно такие головоломки имеют в себе комплекс решений, для достижения целей.
а конкретно в практики ты можешь использовать какую-то часть решения. Например полетела база, а на складе 100 коробок и нужно найти нужный товар.

Добавлено через 1 минуту

Сообщение от titan4ik Я этого вообще не понимаю. Не интересно. Может в мое время в это не играли) Короче, я не в теме.

что в детективов не играли причина и следствие.

0

Сообщение от dimank666 Например полетела база, а на складе 100 коробок и нужно найти нужный товар.

В каждой коробке один товар или набор? Ну и...что делать? Как найти нужный товар?

Добавлено через 9 минут
Если вместо тюремщика будет ГСЧ, то это какая-то стохастическая самоорганизация данных - в замкнутые цепочки.
Некая странная организация хранилища данных, когда по индексу или ID выходим на конечную цепочку с ним, а не на сам блок нужных данных. Наверное целый раздел математики можно на этом развить. Хотя, он, скорее всего, уже есть. а это некий частный случай.
Не исключаю, что этот инструментарий можно использовать для анализа каких-то социальных связей. В обществе такие цепочки (контакты людей) образуются автоматически, только они ещё и пересекаются. Мда, это будет "немного" другая топология. Не знаю, может и связи образов в мозге имеют похожую топологию - ассоциативные цепочки и т.п. Но это уже не случайные связи.
В некоторых лечебных учреждениях раньше были такие плакаты: "Избегайте случайных связей!"

0

Я прочитал доп комментарии тут и статью на Хабре.

Уделяется особое внимание что таблички не перемешиваются. Вроде, от этого результат не зависит.

Кто-то подсчитывал вероятность успеха первого узника? Она равна корню сотой степени от ~0.318?

0

Сообщение от titan4ik В каждой коробке один товар или набор? Ну и...что делать? Как найти нужный товар?

ну вот тебе гипотетическая ситуация пришло 100 контейнеров в контейнерах двигатели или автомобили имеющие свой серийный номер, документов нет как будешь искать нужный автомобиль, а если контейнеров 1000 что всю 1000 будешь вскрывать, не выгоднее идти по методу цепочек ведь цепочки могут быть всего по 2-10 контейнеров.

0

Сообщение от dimank666 ну вот тебе гипотетическая ситуация пришло 100 контейнеров в контейнерах двигатели или автомобили имеющие свой серийный номер, документов нет как будешь искать нужный автомобиль, а если контейнеров 1000 что всю 1000 будешь вскрывать, не выгоднее идти по методу цепочек ведь цепочки могут быть всего по 2-10 контейнеров.

Я всё-таки глубоко в тему не влез и даже статью на Хабре не прочитал - только глянул бегом и идею ухватил.
Такое ощущение, что если вам нужно найти один раз 1 автомобиль, то не важно как действовать. И если нужно все - тоже не важно все нужно вскрыть и промаркировать коробки. А если некое число авто найти нужно...не знаю.
Это ведь немного не та задача. Открытую коробку ты потом не закрываешь. Ладно. Есть желание покопаться по свободе. Забили вы гвоздь в мозг с этими заключенными и тюремщиком-инноватором. Интересно)

0

По изначальному условию никаких выигрышных стратегий нет. Первый арестант, независимо оттого, кто вызовется, найдёт свой номер с 50 попыток с вероятностью 0,5 (в предположении, что нет сговора с тюремщиком). Если он угадает, а далее следует рассматривать только этот вариант, то его уводят и он не может передать информации о содержимом коробок. Единственная доступная информация для остальных - номера проверенных коробок, которые он мог сообщить остальным заблаговременно и факт угадывания. Т.е. то, что в одной из 50 коробок с известными номерами точно есть номер угадавшего его первого арестанта. Но это никак не меняет шансов для следующего, ведь по сути он просто узнаёт о том, что в одной половине коробок один из номеров точно не его. Но то известно и так, без каких либо проверок. Более того, и во второй половине коробок один из номеров тоже точно не его. Поэтому, вероятность удачи второго арестанта остаётся такой же как у первого, т.е. 0.5. В итоге, вероятность выиграть всем составляет Р=8.8Е-16, т.е. лучше и не пытаться.

0

Сообщение от Alexis333 В итоге, вероятность выиграть всем составляет Р=8.8Е-16, т.е. лучше и не пытаться.

Еще один учёный-математик

А тему почитать не судьба?

0

Сообщение от titan4ik Им всего нужно порядка миллиона раз сыграть.

Это я тут оч сильно напутал с нулями (имелось ввиду 2¹⁰⁰ раз). Но это уже не важно. Поскольку заключенные стратегию единую выработали)

Добавлено через 1 минуту

Сообщение от I can Еще один учёный-математик

не, ну не очевидно из условий, что заключенные имеют возможность реализовывать совместную стратегию.
В конце концов они могли бы все вместе одного тюремщика и даже к миру принудить как-то асимметрично)

0

Сообщение от titan4ik ну не очевидно из условий, что заключенные имеют возможность реализовывать совместную стратегию.

Конечно не очевидно А это что?

Сообщение от dimank666 Заключённые могут обсудить стратегию и выбрать, кто пойдет в комнату, и в какой последовательности.

0

I can,
я это воспринял, как "второй вариант" и решил сначала проработать первый. Там же подчеркнуто и написано "И второй вариант".

0

Я смоделировал для миллиона случайных раскладок, получил 31.4345%.

Для одной тысячи псевдослучайных раскладок распределение максимальной длины цепи такое:

Миниатюры

 

1