На каждом поле шахматной доске либо лежит, либо не лежит зёрнышко. Тюремщик случайно выбирает поле на доске и показывает на него первому игроку. Тот должен по выбрать поле на доске по своему усмотрению и, если оно пустое, поставить на него дополнительное зерно, либо если оно уже есть, убрать его с доски. После чего первого уводят, приводят второго, который должен определить (с первой попытки), какую клетку выбрал тюремщик.
Как и во всех задачах подобного рода, обмен информацией между игроками после начала игры невозможен. Гарантируется, что на доске после 1-го игрока и до 2-го ничего не меняется и доска не поворачивается.
У меня малость бредовая идея. Пусть зерно - 1, а пустая клетка - 0.
Надо клетку, которую загадал тюремщик. координаты ее перевести в двоичный код. Таким образом у нас максимальная координата получится 1000, 1000. Далее, найти строку или столбец, изменить в нем 0 на 1 или 1 на 0, чтобы получилась загаданная координата. 2-й игрок, сразу отметает столбцы и строки, координаты которых больше 8.
Но здесь как повезет. Может быть, что нельзя никак закодировать координаты клетки.
Есть одна идея... но пока что не придумал как обосновать одну вещь...
каждая клетка кодируется своим номером в ряду и столбце, т.е. любая клетка предствима как (1..8,1..8). Берём все клетки на которых стоят 1 и складываем соответственные координаты. Получаем (a,b), задача первого сделать так, чтобы в последних разрядах чесел a и b стояли цифры, указывающие на клетку, выбранную тюремщиком. Теперь проблема: как доказать что такой выбор клетки всегда существует.
Покажем, что это можно сделать в случае, когда N=2^k. Вершины куба (их 2^N) будут соответствовать коэффициентам булева многочлена от k переменных. Каждому такому многочлену сопоставим набор его значений на векторах, в которых ровно один нуль (таких наборов 2^k=N). Утверждение следует из того, что все мономы имеют разные наборы значений, иначе говоря, любой бином хотя бы в каком-то из выбранных векторов обращается в единицу. (Это легко видеть, выделив общий множитель в биноме.)
Клевая задача, заставила подумать :о) При том, что идея ясна сразу, конкретная реализация достаточно не тривиальна оказалась.
Надо понять сначала нашу цель. Наша цель - передать два числа от 0 до 7 - строку и стробец. В подобных задачах часто надо пытаться зацепиться за четность количества зернышек в строках и столбцах - это то, что понятно сразу. Каждая строка и каждый столбец кодируют один бит информации (четно или нечетно), таким образом все строки и все столбцы вместе кодируют два байта информации. Сейчас в этих двух байтах содержится какая-то фигня, наша задача поменять один бит в каждом из байтов (очевидно, размещение зернышка в строке А стоблец Б меняет четность в обоих) так, чтобы второй игрок из полученных значений мог получить информацию о том, что же выбрал тюремщик. Решая задачу отдельно для строки и отдельно для столбца мы получаем следующее: имея байт, содержащий случайную величину, надо поменять в нем один бит так, чтобы второй узник смог по полученной в байте величине декодировать три бита информации. Вот тут начинается самое сложное :о) Тем, кто задачу еще не решил, советую пока не читать комментарий дальше и подумать отталкиваясь от этого момента: найти функцию f(a)->b где область определения (0..255), область значений (0..7), и для любого a0 и любого b0 должно существовать k (0 <= k <= 7) такое, что f(a ^ (1 << k)) = b
Вот функция, к которой в конце концов пришел я:
Пусть значения каждого из битов в байте соответственно равны а0, а1, ... а7, и кодировать ими нам число p, которое содержит три бита информации р0, р1 и р2. Будем кодировать следующим образом
р0 = а0 xor a3 xor a4 xor a6
p1 = a1 xor a3 xor a5 xor a6
p2 = a2 xor a4 xor a5 xor a6
Посчитаем, чему сейчас равно значение закодированного числа. Мы обязаны поменять значение одного из битов a0..a7 так, чтобы закодированное число приняло нужную нам величину. Если оно уже равно нужной нам величине, поменяем значение в a7 (a7 не влияет на число p). Если оно отличается в одном бите, поменяем соответственно a0, a1 или a2, в зависимости от того, какой бит не совпадает .Если не совпадает два бита, поменяем в a3, a4 или a5, в зависимости от того, какие два бита не совпадают. Если не совпадают все три бита, поменяем в a6. Таким образом, имея байт со случайной величиной в нем, мы можем поменять один бит в нем, чтобы закодировать любое число от нуля до 7, что нам собственно и требуется.
Тоже самое, что и выше можно по другому определить. Для начала представим нашу доску в одномерном виде. Выделим 8 групп клеток (чем-то напоминает бинарное дерево в общем случае):
1) клетки через одну 0, 2, 4,..., 62
2) клетки через две 0, 1, 4, 5,...,60, 61
i) клетки через 2^i
В каждой из этих групп посчитаем четность фишек в соотвествующих клетках (тоже, что и xor). Данные классы клеток соответствуют разрядам числа, обозначающего координату загаданной ведущим клетки. Можно легко доказать, что любую исходную ситуацию можно одним изменением привести к любому числу из диапазона 0..63, что дает нам шанс для второго игрока отгадать исходную клетку.