Pull to refresh

Сложная задачка про узников

Entertaining tasks Mathematics *
Рассказали мне недавно супер-задачу, потребовалось несколько дней чтобы решить.

Есть бесконечно много узников (счётное число), пронумерованных натуральными числами. Каждый узник знает все номера, в том числе свой. Узники умеют бесконечно быстро думать, и у них бесконечно много памяти. Сначала у них есть время на обсуждение алгоритма.
Их выстраивают по порядку, так что первый смотрит в спину второго, второй в спину третьего и т.д. На них одновременно надевают колпаки двух цветов. Каждый узник видит, какие колпаки надеты на узниках с большими номерами (первый видит все колпаки, кроме своего, второй — все, кроме своего и первого и т.д.). Никакой информацией они уже не обмениваются. Дальше каждый из них должен одновременно со всеми сказать, какой на нём колпак. Кто не угадает — того расстреливают. Как сделать так, чтобы лишь конечное число узников расстреляли?

PS Не хватает кармы, чтобы переместить в блог «Занимательные задачки». Спасибо за карму, перенёс в блог «Занимательные задачки».

UPD Решение в комментах.
Total votes 18: ↑11 and ↓7 +4
Views 3.2K
Comments 69

Узники и коробки

Entertaining tasks Mathematics *
Ещё одна задача про узников. На этот раз не такая теоретическая.

Есть 30 узников, пронумерованных от 1 до 30. Каждый знает все номера, в том числе свой. У них есть время на обсуждение алгоритма. Дальше их по одному заводят в комнату, где есть 30 пронумерованных коробок. В каждой коробке по одному ключу с номером какого-то узника (номер коробки и номер ключа в ней могут быть различными). Ключи по коробкам распределены совершенно случайно (т.е. все перестановки ключей в коробках равновероятны). Каждый узник по очереди открывает 15 коробок и смотрит, какие в них ключи, причём, открывая очередную коробку, он может сначала посмотреть, какой в ней ключ, а потом решить, какую открывать следующей. Если в одной из этих 15 коробок оказался ключ с его номером, то его отпускают, если нет — расстреливают. Комната и все коробки в ней после этого приводятся в изначальное состояние, т.е. следующие узники не получают никакой информации о том, что было с предыдущим узником.
Придумайте алгоритм, чтобы с вероятностью не меньше 30% выжили все узники.

PS Можно использовать калькулятор.

UPD Решение в комментах.
Total votes 13: ↑8 and ↓5 +3
Views 939
Comments 57

Реши задачку, используя один бит памяти!

Entertaining tasks
image
Задача, подобная этой на использование совместных ресурсов:
1-го сентября 100 бессмертных эльфийских воркутинских зэков постоили на торжественную линейку и предложили им ускорить процесс своего освобождения. Итак, в тюрьме есть камера с висящей лампочкой. Лампочку можно включить или выключить. Каждый день, начиная с 1-го сентября тюремщик будет запускать одного заключённого в эту камеру. В этот момент зэк сможет увидеть, горит ли лампочка.
У каждого заключенного тюремщик будет спрашивать: «А все ли твои товарищи тут были хотя бы раз?» Если зэк отвечает «нет», игра продолжается.
Если зэк отвечает «да» и это правда — всех выпускают на волю в тундру. Если же это неправда — высшая мера наказания для всех.
Тюремщики могут выбирать заключенных вразброс и с повторениями. Заключенные сидят в одиночных камерах и могут договориться только один раз — 1-го сентября на обеде после торжественной линейки. После этого они сидят в «одиночках» без окон, совсем не видят друг друга и лампочки.
Найти оптимальную стратегию поведения каждого заключенного с тем, чтобы их выпустили пораньше.
Читать дальше →
Total votes 77: ↑65 and ↓12 +53
Views 4.2K
Comments 252