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

[avva]

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

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

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

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

Comments

[kapahel.livejournal.com]

Пронумеруем клетки числами от 0 до 63. Первый заключенный может своим ходом добиться любого остатка суммы номеров клеток с камнями от деления на 64.

[avva.livejournal.com]

Точно может?

[kapahel.livejournal.com]

Нет, лажа. Не удается придумать решение для произвольной доски. Для 8x8 можно занумеровать клетки векторами из (F_2)^6 и сложить нумера отмеченных и указанной.

[avva.livejournal.com]

Это верно, да.

Можно показать несложными counting arguments, что решение может существовать только на доске размером 2^k.

[(Anonymous)]

А можно поподробнее? Сумел доказать что невозможно для любой доски с нечетным количеством элементов, дальше пока не удалось

спасибо

[burrru.livejournal.com]

Упростим задачу до 6 клеток. В клетках под номерами 0, 1, 2 нет камней, а клетках под номерами 3, 4, 5 есть камни. Тюремщик указывает на клетку под номером 5 или 4. Легко видеть, что добиться этого остатка нельзя.

Причина в том, что в этой и подобных ситуациях есть любое действие добавляет к имеющемуся остатку небольшое число. А надо добавить большое.

[kapahel.livejournal.com]

Ну да, я невнимательно условие прочел (нельзя на 4 или 5 еще один положить).