Задача М3‍‍

Полных решений этой задачи мы пока не получили.

Ученик 6-го класса Сергей Елисеев (Москва) прислал нам раскраску шестиугольной сетки тринадцатью цветами, которую мы воспроизводим, насколько это позволяют полиграфические возможности, на рисунке 8; он утверждает (без объяснений), что ответ в общем случае такой:

В задаче a) требуемая раскраска возможна, если количество цветов равно сумме двух квадратов целых чисел: $$ \begin{alignat*}{3} 1&=0^2+1^2;&\quad 2&=1^2+1^2;&\quad 4&=0^2+2^2;\\ 5&=1^2+2^2;&\quad 8&=2^2+2^2;&\quad 9&=0^2+3^2;\\ 10&=1^2+3^2;&\quad13&=2^2+3^2;&\quad16&=0^2+4^2 \end{alignat*} $$ и т. д.

В задаче б) решение возможно при количестве цветов, равном сумме двух чисел из последовательности 0, 1, 3, 6, 10, 15, $\ldots$‍,‍ $\dfrac{n(n+1)}{2}$‍,‍ $\ldots$‍:‍ $$ \begin{alignat*}{3} 1&=0+1;&\quad3&=0+3;&\quad4&=1+3;\\ 6&=0+6;&\quad7&=1+6;&\quad9&=3+6 \end{alignat*} $$ и т. д.

Попробуйте выяснить, правильны ли эти ответы? К этому вопросу мы вернёмся позже, а пока обратим внимание на одну тонкость в формулировке задачи (первым её заметил читатель В. Гутенмахер из Москвы).

Начнём с задачи a). В ней требуется найти раскраски, при которых «центры квадратов одного и того же цвета расположены в вершинах квадратной сетки». Но в условии не сказано, что для разных цветов эта «большая» квадратная сетка должна быть одинаковой. Посмотрите на рисунок 9. Здесь тоже квадраты каждого из трёх цветов образуют сетку, но для красного цвета «шаг» (сторона квадрата) сетки равен $\sqrt{2}$‍,‍ а для белого и зелёного — 2, да ещё сетки повёрнуты друг относительно друга.

Но если понимать условие задачи буквально — а на письменном экзамене или на олимпиаде именно так и следует поступать, — то раскраска рисунка 9 удовлетворяет условию задачи. При подобном понимании ответ в задаче а) будет такой: при любом числе цветов. Действительно, из любой раскраски с $n$‍‍ цветами, один из которых белый, легко изготовить раскраску с $n+1$‍‍ цветами: нужно белые квадраты в «шахматном порядке» раскрасить белой и новой $(n+1)$‍‍-й краской (именно так из шахматной красно-белой раскраски получилась раскраска рисунка 9).

При таком понимании и задача б) становится совсем простой.

Ответ. При любом числе цветов, большем 2. Действительно, раскраска двумя цветами невозможна, поскольку, если из трёх шестиугольников, каждые два из которых имеют общую сторону, два покрашены в один цвет, то и все шестиугольники должны быть раскрашены этим цветом. Раскраски с 3 и 4 цветами находятся легко, а дальше нетрудно, раскрашивая белые шестиугольники в три цвета, увеличить число цветов на 2, затем ещё на 2 и т. д.

Разумеется, таким способом можно получить много разнообразных раскрасок. Имея любую раскраску А ($k$‍‍ цветов), выделив в ней какой-то один цвет $x$‍‍ и взяв еще одну раскраску Б ($l$‍‍ цветов), можно построить «расширение раскраски А с помощью Б» следующим образом. В раскраске А сохраняются все цвета, кроме $x$‍,‍ а квадратики или шестиугольники — наше замечание относится к обоим случаям — цвета $x$‍‍ раскрашиваются новыми $l$‍‍ цветами: сетка, которую они образуют, раскрашивается по способу Б. Получается новая раскраска $k+l-1$‍‍ цветами. (На рис. 9 изображено, в этой терминологии, «расширение шахматной раскраски с помощью шахматной раскраски».)

Итак, в такой «буквальной» формулировке задача оказывается совсем простой. Однако, автор задачи, а также большинство читателей журнала, приславших нам решения, понимали условие иначе; а именно, они хотели найти такие раскраски, при которых решётки, соответствующие разным цветам, одинаковы и получаются друг из друга параллельным сдвигом (как на рисунках, сопровождающих условие задачи, и на рис. 8). Решение задачи М3 с таким уточнением мы приведём в следующем номере.

Теперь будем считать правильным только такое заполнение плоскости квадратами (или шестиугольниками), при котором сетка, соответствующая какому-то одному цвету, имеет такие же размеры и направления сторон квадратов (или треугольников), как и сетка, соответствующая любому другому цвету. Иначе говоря, все сетки должны получаться друг из друга параллельным сдвигом. Разумеется, разные сетки не могут быть закрашены одним цветом. Решение задачи для обоих случаев (квадраты и шестиугольники) аналогично, и мы рассмотрим оба случая сразу.

I. Докажем сначала, что если плоскость заполнена указанным образом, то число цветов равно $k^2+l^2$‍‍ в случае квадратов и $k^2+kl+l^2$‍‍ в случае шестиугольников, где $k$‍,‍ $l$‍‍ — целые неотрицательные числа (но не равные нулю одновременно)‍.

Примем за единицу длины расстояние между центрами двух соседних квадратов или шестиугольников.

Начертим жирными чёрными линиями сетку, проходящую через центры квадратов или шестиугольников одного цвета, скажем, красного (рис. 2, 3). В случае шестиугольников мы проведём линии только двух направлений, так что сетка будет состоять не из правильных треугольников, а из ромбов.

Пусть $ABCD$‍‍ — один квадрат или один ромб сетки. Выведем формулу для его площади.

В случае квадрата проведём через точки $A$‍‍ и $B$‍‍ прямые, параллельные сторонам окрашенных квадратиков и точку их пересечения обозначим $M$‍.‍ Длины $AM=k$‍‍ и $BM=l$‍‍ — целые числа (одно из них может быть равно нулю). На рисунке 1 $k=3$‍,‍ $l=2$‍.‍ Тогда $AB=\sqrt{k^2+l^2}$‍,‍ а площадь $ABCD$‍‍ равна $k^2+l^2$‍.‍

В случае ромба проведём через точки $A$‍‍ и $B$‍‍ прямые, параллельные апофемам шестиугольников, и точку их пересечения обозначим $M$‍.‍ Угол $AMB$‍‍ может оказаться равным $120^\circ$‍‍ или $60^\circ$‍.‍ Проведём прямые так, чтобы он был равен $120^\circ$‍.‍ Длины $AM=k$‍‍ и $BM=l$‍‍ — целые числа (одно из них может быть равно нулю). На рисунке 2 $k=1$‍,‍ $l=2$‍.‍ Тогда $AB=\sqrt{k^2+kl+l^2}$‍,‍ а площадь ромба равна $\dfrac{\sqrt3}2(k^2+kl+l^2)$‍.‍

Мы докажем, что число цветов, участвующих в раскраске, равно отношению площади $ABCD$‍‍ к площади одного окрашенного квадратика (случай (a)) или шестиугольника (случай (б)) и, тем самым, равно:

в случае квадратов $k^2+l^2$‍,‍

в случае шестиугольников $k^2+kl+l^2$‍‍

(так как площадь одного шестиугольника равна $\dfrac{\sqrt3}2$‍)‍

Это сразу следует из следующей леммы.

Основная лемма. Часть $ABCD$‍,‍ закрашенная каждым цветом, участвующим в раскраске, либо представляет собой один квадратик (в случае (a)), соответственно шестиугольник (в случае (б)), либо состоит из кусочков (для красного цвета — четырёх, для других цветов — двух), из которых можно сложить такой же квадратик или соответственно шестиугольник.

Доказательство леммы несложно, и мы предлагаем читателю провести его самостоятельно. Заметим только, что раскраска всех квадратов (ромбов) жирной сетки одинакова, т. е. если вырезать квадрат (ромб) $ABCD$‍‍ из плоскости и наложить его, скажем, на соседний квадрат (ромб), то часть $ABCD$‍,‍ закрашенная любым цветом, точно совместится с частью соседнего квадрата (ромба), закрашенной тем же цветом.

Существует другой способ изложить это доказательство, более красивый, но требующий некоторой работы воображения. Ограничимся сначала случаем квадратной сетки. Вырежем из плоскости квадрат $ABCD$‍‍ и склеим из него трубку — цилиндр, раскрашенной стороной снаружи, совместив стороны $AB$‍‍ и $DC$‍.‍ Эта трубка ограничена двумя окружностями, получившимися из сторон $AB$‍‍ и $DC$‍.‍ Склеим эти окружности друг с другом (совместив точку $A=D$‍‍ с точкой $B=C$‍).‍ Бумажную трубку придётся для этого сплющить, но мы всё равно будем считать всю её окрашенную поверхность за единое целое, не разделённое на части сгибами. Площадь поверхности полученной фигуры равна $k^2+l^2$‍,‍ а часть её, закрашенная любым из цветов раскраски, — квадратик размером $1\times1$‍.‍ Мы вам советуем всё это практически проделать с квадратным листком бумаги, раскрасив его пятью или большим числом цветов.

В случае шестиугольников мы придём к аналогичному результату, если таким же образом склеим прямоугольник, имеющий одну сторону, общую с ромбом $ABCD$‍,‍ а другую, равную высоте ромба.

Можно заполнить плоскость и другими равными фигурами, в которых площади, закрашенные разными цветами, равны. Например, в решении задачи (a), присланном из Киева (пер. Белинского, 8, кв. 32, фамилия автора не указана), предлагается заполнить плоскость фигурами, составленными из двух квадратов со сторонами $k$‍‍ и $l$‍.‍ Скажем, для $k=2$‍‍ и $l=3$‍‍ (13 цветов) фигура будет такой, как на рисунке 4.

II. Теперь пусть нам дано число $m=k^2+l^2$‍‍ или $n=k^2+kl+l^2$‍.‍ Покажем, что плоскость можно заполнить в соответствии с условием квадратами $m$‍‍ цветов или шестиугольниками $n$‍‍ цветов.

Заполним плоскость равными квадратами или правильными шестиугольниками и начнём их раскрашивать следующим образом.

Закрасим один из них красным. Отсчитаем от него $k$‍‍ квадратиков (шестиугольников) в одну сторону, потом повернём на $90^\circ$‍‍ для квадратов и на $60^\circ$‍‍ для шестиугольников и отсчитаем $l$‍‍ квадратиков (шестиугольников) в новом направлении, и тот квадратик (шестиугольник), в который мы придём, тоже закрасим красным. На отрезке, соединяющем центры двух красных квадратиков (шестиугольников), как на стороне, построим квадрат (a) или правильный треугольник (б). Пристраивая к нему равные квадраты (правильные треугольники), мы получим центры всех квадратов (шестиугольников), которые надо закрасить красным; сдвигая параллельно всю совокупность красных квадратов (шестиугольников), мы будем получать каждый раз новую совокупность незакрашенных квадратов (шестиугольников) и закрашивать её новым цветом, пока не закрасим всю плоскость. По доказанному выше число цветов будет равно $k^2+l^2$‍‍ в случае (а) и $k^2+kl+l^2$‍‍ в случае (б).

III. Какие же натуральные числа представимы в виде $k^2+l^2$‍‍ или $k^2+kl+l^2$‍?‍ Чтобы выписать первые несколько таких чисел, удобно составить две таблицы: таблицу 1 — для $k^2+l^2$‍,‍ таблицу 2 — для $k^2+kl+l^2$‍.‍

Числа ниже диагонали повторяют уже написанные, и их писать не нужно. Некоторые числа входят в таблицу дважды; соответствующие клетки выделены. Это значит, что при таком числе цветов имеются два существенно различных способа заполнения плоскости. Теперь уже легко начать выписывать эти числа в порядке возрастания.

Первая таблица: 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, $\ldots$‍‍
Вторая таблица: 1, 3, 4, 7, 9, 12, 13, 16, 19, 21, 25, 27, 28, $\ldots$‍‍

Пусть мы уже выписали эти числа до какого-то места и ищем следующее по величине число.

Красные линии, проведённые на первой таблице, помогают это сделать. Чтобы объяснить, как они проведены, заметим, что в первой таблице каждое число равно квадрату расстояния от центра той клетки, в которой оно стоит до точки 0 в левом верхнем углу (за единицу длины принимаем сторону клетки). Поэтому, если провести несколько окружностей с центром 0, то они разобьют наши числа (то есть центры клеток, в которых они стоят) на группы в порядке возрастания. Если попытаться провести от руки аналогичные линии во второй таблице, то может показаться, что они прямые. Но это, конечно, не так. На самом деле это графики соотношений вида $$ k^2+kl+l^2=c=\text{const} $$ в системе координат с началом 0 и осями, идущими: ось $k$‍‍ — вправо; ось $l$‍‍ — вниз. Перейдя к другой паре переменных: $x=k+l$‍,‍ $y=k-l$‍,‍ можно увидеть, что это эллипсы, вытянутые в направлении оси $y$‍‍‍‍.

В определённом смысле мы получили ответ, но, быть может, его можно упростить. Например, если в какой-то другой задаче мы получим ответ: все числа вида $k^2+l^2+m^2+n^2$‍,‍ где $k$‍,‍ $l$‍,‍ $m$‍,‍ $n$‍‍ целые, то его можно будет переписать так: любое целое неотрицательное число, поскольку все натуральные числа представимы в таком виде. Может быть, и в нашу последовательность входят все натуральные числа, начиная с некоторого места? Чтобы доказать, что это не так, можно воспользоваться системой пунктирных линий.

Проведём в первой таблице красную окружность с центром 0 радиуса $n$‍.‍ Центры всех клеток, в которых стоят числа, меньше или равные $n^2$‍,‍ лежат внутри или на границе сектора этой окружности с центральным углом $45^\circ$‍.‍ Поэтому все такие клетки лежат внутри фигуры, получающейся из этого сектора, если к нему добавить окаймляющую его полосу ширины 1. Площадь этой фигуры меньше $\dfrac{\pi n^2}8+3n+4$‍.‍

Отсюда среди первых $n^2$‍‍ натуральных чисел меньше $\dfrac{\pi n^2}{8}+3n+4$‍‍ представимых в виде $k^2+l^2$‍.‍ При больших $n$‍‍ второе число меньше первого и составляет от него примерно $\dfrac\pi8$‍.‍ В действительности, так как некоторые числа в таблице равны, чисел вида $k^2+l^2$‍‍ ещё меньше. Легко убедиться в том, что доля чисел, представимых в виде $k^2+kl+l^2$‍,‍ ещё меньше.