Помогите найти формулировку

[arqady]

Там говориться про комнату с доской $8\times8$. Каждая клетка либо чёрная, либо белая.
Клетки можно переворачивать. Тогда она меняет свой цвет.
Следующие слова могут быть полным бредом.
Ведущий переворачивает какую-то клетку. Двое других доску не видят, но о чём-то между собой договариваются.
Один из них заходит и переворачивает какую-то клетку. После него заходит второй и определяет, какую клетку перевернул ведущий.
Как они эти двое это делают?
Если кто знает, какова точная формулировка этой задачи, напишите, пожалуйста.
Спасибо!

[Rock`n`Rolla]

Похоже на http://datagenetics.com/blog/december12014/index.html .

[Cash]

По сути - все та же задача по поиску за один проход массива непарного целого числа. Но редакция такова, что это действительно похоже на магию.

Супер. Блеск. Высший класс!

arqady, Rock`n`Rolla спасибо огромное!

[warlock66613]

Даже прочитав решение я никак не могу сообразить как это работает. В моём преставлении задача сводится к разбиению множества $B$ всех бинарных строк длины $2^n$ на $2^n$ множеств $u_i$ так, чтобы для каждого элемента $x \in B$ в каждом $u_i$ нашёлся элемент $y$ такой, чтобы $\rho(x, y) = 1$, где $\rho$ — расстояние между двумя строками, определяемое как количество несовпадающих бит. Что с этим делать дальше я так и не придумал.

-- 31.07.2016, 15:15 --

(Оффтоп)

Ясно, что множества $u_i$ должны быть равномощными и что для каждого $x$ в каждом $u_i$ есть ровно один элемент $y$, удовлетворяющий условию. Для случая $n=2$ требуемое разбиение находится легко, но общую закономерность (кроме того, что строка и её инверсия должны быть в одном подмножестве) я в нём не заметил — уж слишком специальный случай получается.

[ewert]

Вот перевод: https://habrahabr.ru/post/250585/. Но тоже довольно занудный, поскольку достаточно дословный.

На самом деле всё просто. Код ("чётность") доски -- это двоичный код, полученный XORированием двоичных кодов номеров всех чёрных клеток. Переворачивание любой клетки (независимо от цвета) означает дополнительное XORирование кода доски с номером этой клетки.

Первый товарищ заходит, подсчитывает код доски и XORирует его с кодом загаданной клетки и переворачивает клетку с полученным после этой операции номером.

После чего код доски оказывается равным коду загаданной клетки, и второму остаётся только подсчитать этот код, взглянув на доску.

[Munin]

Уф-ф-ф, ewert, спасибо за краткое объяснение!