Задача М530‍‍

Заменим наш лист бумаги таблицей из нулей и единиц: если клетка чёрная, напишем на её месте единицу, а если белая — ноль (рис. 2). Определим для каждой клетки сумму её соседей «по модулю 2», т. е. по следующему правилу: $$ \begin{gather*} 0+0=1+1=0;\\ 1+0=0+1=1.\\ \end{gather*} $$

Сумму соседей данной клетки назовём её ореолом, а вместо слов «чёрная клетка» будем писать «1-клетка».

Из условия задачи следует, что состояние клетки (т. е. записанное в ней число) в некоторый момент времени равно её ореолу в предыдущий момент.

а) Если множество $B$‍‍ 1-клеток при перекрашивании не изменяется, то ореол любой «1-клетки» множества $B$‍‍ равен 1. Сложим ореолы всех «1-клеток». Каждая сторона, общая для двух «1-клеток», вносит в эту сумму всех ореолов две единицы: поэтому сумма всех ореолов равна сумме чётного числа единиц, т. е. равна нулю. Но так как ореол каждой «1-клетки» равен 1, получаем, что клеток в $B$‍‍ — чётное число.

б) Будем писать $A\to B$‍,‍ если при перекрашивании таблица $A$‍‍ переходит в таблицу $B$‍.‍ Назовём суммой таблиц $A$‍‍ и $B$‍‍ таблицу $A+B$‍,‍ получающуюся послементным сложением чисел таблиц $A$‍‍ и $B$‍‍ (по указанным выше правилам; см. рис. 3).

Лемма. Если $A\to A_1$‍,‍ $B\to B_1$‍,‍ то $A+B\to A_1+B_1$‍.‍

Это следует из того, что при сложении ореолы клеток тоже складываются.

Приступим к решению задачи б). Пусть $$ B_1\to B_2\to\ldots\to B_r\to B_1. $$ Используя лемму, получаем: $$ \begin{gather*} B_1+B_2\to B_2+B_3\to\ldots\to B_r+B_{1}\to B_1+B_2,\\ B_1+B_2+B_3\to B_2+B_3+B_4\to\ldots\to B_r+B_1+B_2\to B_1+B_2+B_3,\\ .~~.~~.~~.~~.~~.~~.~~.~~.~~.~~.~~.~~.~~.~~.~~.~~.~~.~~.~~.~~.~~.\\ B_1+B_2+B_3+\ldots+B_r\to B_1+B_2+B_3+\ldots+B_r. \end{gather*}$$

Из последней строчки и задачи а) следует, что в таблице $B_1+B_2+\ldots+B_r$‍‍ — чётное число «1-клеток». Заметим теперь, что число «1-клеток» в таблице $A+B$‍‍ равно сумме чисел «1-клеток» в таблицах $A$‍‍ и $B$‍‍ минус чётное число (получающееся из-за того, что $1+1=0$‍);‍ поэтому чётность числа «1-клеток» в таблице $A+B$‍‍ и суммарного числа «1-клеток» в таблицах $A$‍‍ и $B$‍‍ одинакова. Поскольку в таблице $B_1+B_2+\ldots+B_r$‍‍ — чётное число «1-клеток», получаем, что и общее число «1-клеток» в множествах $B_1$‍,‍ $B_2$‍,‍ $\ldots$‍,‍ $B_r$‍‍ чётно.

Задача М530 решена. Но в связи с ней возникает много интересных вопросов. Например, чему может равняться $r$‍,‍ т. е. каким может быть период превращений множества «1-клеток» данной таблицы? Как будет происходить «эволюция» для таблиц «непрямоугольного вида»? Прямоугольные таблицы поддаются исследованиям с трудом. Это объясняется «неравноправностью» их клеток: разные клетки имеют разное число (от двух до чётырех) соседей. Но если из прямоугольной таблицы склеить тор (бублик), то у каждой клетки будет уже по четыре соседа. Для тора уже удаётся кое-что доказать: например, установлено, что на торе, склеенном из квадрата $(2^n+1)\times(2^n+1)$‍,‍ длина периода $r$‍‍ обязательно равна делителю числа $2^n-1$‍.‍ Но возникают новые вопросы: возможны ли для данного тора все такие периоды $r$‍?‍ Например, на торе, склеенном из квадрата $65\times65$‍,‍ существуют периоды длины 1 и 63, но неизвестно, существуют ли периоды длины 3, 7, 9 и 21. Продвинуться в решении задачи на торе помогает аналогичная задача на окружности из $n$‍‍ клеток (похожая задача М19 была разобрана в «Кванте», 1970, № 4).