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

[avva]

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

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

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

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

Comments

[buddha239.livejournal.com]

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

[avva.livejournal.com]

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

[avzel.livejournal.com]

Прошу прощения за тупость. Почему клетка кодируется восьмимерным двоичным вектором, если клеток 64 = 2^6?

[avva.livejournal.com]

шестиричным, конечно, думаю, buddha39 просто описался; впрочем, он сам сможет подтвердить :)

[avzel.livejournal.com]

Спасибо. Да, конечно, шестимерным, до меня уже тоже дошло.

[buddha239.livejournal.com]

Описался, да - и, кстати, я из 239 школы.:)

[avva.livejournal.com]

sorry :)

[buddha239.livejournal.com]

Это я прошу прощения за маразм - шестиричным, конечно.:)

[avzel.livejournal.com]

Спасибо, я уже разобрался. Я даже сочинил вариант задачи, где не нужно требовать, чтобы число объектов угадывания было степенью двойки. У фокусника есть две одинаковых колоды карт (количество карт в колоде произвольно). Он предлагает зрителю загадать карту и сообщить её своему ассистенту. После этого ассистент предлагает другому зрителю выбрать несколько карт из одной колоды (ни одной или всю колоду тоже разрешается), добавляет к ним одну карту из другой колоды, возвращает это множество карт фокуснику, и тот отгадывает задуманную первым зрителем карту.

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