Dmitry

Две тюремные задачки

Двух зэков приговорили к смертной казни. Но дали им один шанс: надели на каждого по колпаку с цифрой. Каждая цифра может быть либо единицей, либо двойкой…

Задача 1

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

1.1. известно, в каком положении рубильник будет изначально

1.2. это не известно.

Задача 2

2.1. Двух зэков приговорили к смертной казни. Но дали им один шанс: надели на каждого по колпаку с цифрой. Каждая цифра может быть либо единицей, либо двойкой. Зэки могут смотреть друг на друга, но не обмениваться никакой информацией. По команде они должны одновременно выкрикнуть по числу. Если хоть кто-то угадает свое собственное число, то обоих отпускают. Как им необходимо договориться, чтобы гарантированно выжить?

2.2. Предыдущий пункт может решить и восьмиклассник, если немного подумает. Если Вы тоже с ним справитесь, то попробуйте предложить решение для трех человек, каждый из которых видит всех остальных, но написанные цифры уже могут быть от одного до трех.

2.3. Если вы справились и со вторым пунктом, то придумайте решение для произвольного числа зэков.

Посмотреть ответ

Ответы

1.1. Допустим, изначально рубильник поднят. Тогда каждый из первых 99-ти зэков должен ровно один раз опустить рубильник, во всех остальных случаях они не должны вообще ничего делать. Сотый зэк каждый раз только поднимает рубильник, если он опущен. Тогда когда он поднимет его в 99-ый раз он может гарантировать, что все зэки побывали в коридоре.

1.2. Всё происходит аналогично, но каждый из первых зэков должен опустить рубильник ровно два раза. Тогда, когда сотый зэк поднимет рубильник в 198-ой раз, либо все остальные зэки уже опустили его по два раза, либо один раз он опустил рубильник из исходного положения, и один из первых зэков опустил рубильник только один раз. В любом случае можно гарантировать, что все зэки побывали в коридоре.

2.1. Первый зэк называет ту цифру, которую видит, а второй - ту, которой не видит.

2.2. см. решение 2.3.

2.3. Пусть зэков n штук. Тогда первый называет такую цифру, чтобы сумма всех чисел на колпаках плюс названная делилась на n. Второй такую, чтобы давало остаток один при делении на n. Третий - чтобы два. И т.д. Каждый может так поступить, так как видит все остальные числа, и все они не больше n.

Задачки прислал Димитрий