задачка, математическое

[avva]

Тюремщик играет с двумя заключенными в следующую игру. Во дворе тюрьмы на земля нарисована доска размером 8x8 клеток, и в центре каждой клетки либо лежит, либо не лежит камешек. Сначала во двор выходит первый заключенный, и тюремщик указывает ему на какую-то клетку доски. Заключенный в ответ должен выбрать какую-то клетку, на свой выбор, и изменить ее состояние: либо убрать камень из центра, если он там был, либо положить в центр, если его там не было.

Потом первого заключенного уводят, и выводят второго. Он должен посмотреть на доску и угадать, на какую клетку указал тюремщик первому заключенному.

Заключенные могут заранее договориться о стратегии, но до того, как выводят первого, они не знают, как выглядит доска, и после этого любое общение между ними запрещено. Могут ли заключенные так договориться действовать, чтобы второй всегда мог правильно отгадать выбранную клетку?

Update: я раскрываю правильные решения - их штук шесть набралось за прошедшие пять часов, первыми были buddha239 и plakhov. Не заглядывайте в комменты, если хотите сами подумать.

Comments

[breqwas.livejournal.com]

Хм. Уж нет ли в этом посте пропаганды пыток и издевательств над заключёнными в тюрьмах?

[breqwas.livejournal.com]

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

[avva.livejournal.com]

А я как раз Солженицына читаю, так очень уместно звучит.

[alsterellie.livejournal.com]

Первая мысль — не могут. Для того, чтобы зашифровать состояния доски из 8х8 клеток, нужно шесть битов: ln2(8) + ln2(8). Заключённые же своими перекладываниями могут рассчитывать разве что на 1-2 бита. Но посмотрю на ответы остальных, любопытно.

[flaass.livejournal.com]

Белоснежка и 7*9 гномов :)

[phoonzang.livejournal.com]

Первый заключенный может менять или не менять ту клетку, на которую указал тюремщик? Если нет, то какой смысл в том, что тюремщик ему сперва указывает на какую-то клетку?

[phoonzang.livejournal.com]

а, сорри, понял

[chessplayer.livejournal.com]

он обязан менять или может все так оставить?

[buddha239.livejournal.com]

Мне кажется, что пару лет назад очень похожая задачка уже была (возможно, действительно про Белоснежку).:) И то же решение все так же работает.:)

[avva.livejournal.com]

Обязан.

[http://users.livejournal.com/_1313/]

нужно зашифровать координаты клетки, номера рядов указать. это два бита как раз

[http://users.livejournal.com/_1313/]

а изначальное положение "нет ни одного камня" валидное?

[avva.livejournal.com]

да.

[stevebest.livejournal.com]

Кажется, я знаю алгоритм для этого случая! :)

[avva.livejournal.com]

http://community.livejournal.com/ru_math/28836.html
по-моему, это другая задача.

http://avva.livejournal.com/1743110.html
это тоже другая задача :)

[liveuser.livejournal.com]

(Вспоминается задачка про 100 заключенных, которых нужно пересчитать одним битом)

[alsterellie.livejournal.com]

Как — два бита? Как вы зашифруете двумя битами клетку 2х5? Или 0х7?

[buddha239.livejournal.com]

Ну, может, не было такой задачи.:) Все равно - каждая клетка кодируется своим восьмимерным вектором над Z/2Z, и первый может добиться любой суммы - в том числе той, которая покажет на нужную клетку.

[avva.livejournal.com]

это верно, да :) я заскриню пока.

[dimmik.livejournal.com]

Ну, самое тупое "в лоб" решение - товарищи заранее договариваются о всех возможных соответствиях ("исходное состояние доски", "указанная клетка") <-> ("конечное состояние доски")
И по "конечному состоянию" определяют указанную клетку.

[fistashkin.livejournal.com]

Я по-чайницки)

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

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

[phoonzang.livejournal.com]

отображение 2^64 x 2^8 -> 2^64 не так уж и легко инвертируется

[avva.livejournal.com]

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

[alsterellie.livejournal.com]

Не, биекции не получится.

ряды

[jerom.livejournal.com]

Это лишь идея:
Использовать ряды. Скажем, считать первые 32 клетки "нулём", а оставшиеся 32 клетки - ключом, информацией от этого нуля.