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

[avva]

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

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

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

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

Comments

[cxielamiko.livejournal.com]

Рассмотрим граф позиций с рёбрами-переходами. Степени всех вершин — 64. Если его вершины можно раскрасить в 64 цвета без наличия одноцветных рёбер, то задача решена. Возможна ли такая раскраска?

[omnibee.livejournal.com]

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