Данная работа посвящена исследованию хроматических номеров и нахождению минимальных раскрасок. Похожая тема была представлена на Колмогоровских чтениях в 2005 году. Тогда в совместной работе Веры и Елены Бушмановых были найдены хроматические номера всех тетра- и пентамино. Задача, являющаяся частным случаем этой работы, была представлена на Санкт-Петербургской городской олимпиаде в 2010 году.
Тема хроматических номеров и минимальных раскрасок породила много открытых вопросов, большинство из которых не решены до сих пор. В частности, оказалось, что даже нахождение хроматических номеров прямоугольников представляет собой весьма сложную и содержательную задачу. В данной работе найдены хроматические номера «широких» прямоугольников, т. е. тех, у которых отношение большей стороны к меньшей не превосходит двух.
Постановка и решение задачи
Определение: Рассмотрим бесконечную клетчатую плоскость, раскрашенную в k цветов, и клетчатую фигурку (полимино) X. Раскраску будем считать правильной, если она обладает следующим свойством: как бы мы ни расположили данную фигуру X на плоскости (по клеточкам), цвета клеток, которые ограничены фигурой X, будут различными. Наименьшее такое k будем называть хроматическим номером фигуры X (обозначаем cr(X)), а соответствующую раскраску назовём минимальной.
Лемма 1: Если фигура X содержится в фигуре Y, то cr(X)
cr(Y)
Доказательство: (Бушмановы) Возьмем минимальную, подходящую для Y раскраску. Допустим, что эта раскраска не подходит для фигурки X. Значит, есть какая-то фигурка, X не покрашенная в разные цвета, но этой фигурке соответствует фигурка Y, которую можно наложить на фигурку X, тогда получается, что эта фигурка Y покрашена не в разные цвета. Это противоречит тому, что мы взяли подходящую для Y раскраску.
Замечание: Хроматический номер прямоугольника 
не меньше количества клеток в прямоугольнике, т. е. .
Следующая теорема отвечает на вопрос, в каких случаях вышеупомянутое неравенство обращается в равенство.
Теорема 1: Хроматический номер прямоугольника (где m и n — стороны прямоугольника) имеют те и только те прямоугольники, у которых одна из сторон кратна другой.
Доказательство: (Карашевич) Пусть дан прямоугольник вида 
. Покажем, что для него существует раскраска. Заметим, что все цвета равноправны. Пусть каждой краске соответствует число, тогда произвольно заполним прямоугольник числами от
. Теперь разобьём наш прямоугольник на 
квадратов 
, пронумеруем квадраты числами от 
, затем ответим на вопрос задачи для полоски 
(см. рис. 1), теперь в пронумерованные квадраты вставим числа соответствующие номеру квадрата (см. пример на рис. 2 и рис. 3, где 
). Получилась нужная раскраска.
Рис. 1
Рис. 2 Рис. 3
Если же прямоугольник имеет другой вид 
то для него раскраски не существует. Пусть большая сторона лежит по вертикали, тогда, нумеруя краски числами по строкам, получим, что все числа в 
-ом столбце кратны . Сдвинув наш прямоугольник вправо на одну клетку, легко понять, что все числа из первого столбца совпадают со всеми числами из нового (последнего) столбца. Построим новый прямоугольник, совпадающий левым верхним углом с первым прямоугольником, большая сторона которого лежит по горизонтали. Заметим, что в этом прямоугольнике в каждом -ом столбце содержаться числа кратные r, но так как по горизонтали таких чисел 
, а в первом прямоугольнике 
значит, раскраска некорректна (см. рис. 4).
Рис. 4
Теорема 2: Если в прямоугольнике отношение большей стороны к меньшей меньше 
, но больше 
, то хроматический номер данной фигуры равен 
2, где — длина меньшей стороны, т.e. если 
, то 
Доказательство: Разобьем наш прямоугольник на блоки, как показано на рис. 5 (жирными линиями выделен исходный прямоугольник):
Рис.5
В данном случае мы просто переворачиваем наш прямоугольник четыре раза и полученные части выделяем в блоки. Блоки А, В, Е, D, F, G — образуют изначальный прямоугольник. Рассмотрим прямоугольник С, все цвета в этом блоке не совпадают с цветами исходного прямоугольника. Теперь рассмотрим прямоугольник А+. Он не может иметь общих цветов с прямоугольниками D, B, E, F, G, C. Из этого следует, что в прямоугольнике А+ могут быть только цвета из блока А либо новые цвета. Также рассмотрим прямоугольник В+. Он не может иметь общих цветов с прямоугольниками A, D, E, F, G, C. Аналогично в В+ должны быть цвета из В либо новые. Теперь посмотрим на самый правый блок — это блок Е, с возможно какими-то новыми цветами. Под ним будет располагаться блок D (с возможно какими-то новыми цветами). И наконец, рассмотрим блок, находящийся под блоком С и по размерам равный блоку F. В нем (с учетом уже прибавленных) в сумме новых цветов будет столько же, сколько и в блоке F. Теперь мы можем считать, что у нас появился новый блок (назовем его Н), по размерам равный блоку F.
Теперь посчитаем, сколько всего цветов у нас затрачено:
+ 
+ 
Получили, что у нашего прямоугольника хроматический номер не менее чем у прямоугольника 
. Исходный же прямоугольник помещается в прямоугольник 
. По лемме хроматический номер меньшего прямоугольника не больше хроматического номера большего прямоугольника. Из этого следует, что cr(n, m) строго равен хроматическому номеру прямоугольника . По теореме 1 хроматический номер в точности равен . На данной картинке мы использовали, что блок Е+ «длиннее», чем блок D, т. е. 
В противоположном случае утверждение про блок Н неверно. Таким образом, теорема верна при условии
. Доказано.
Все раскраски, возникающие в работе, построены по следующему принципу. Дана координатная плоскость (точки с целочисленными координатами соответствуют центрам клеток). Покрасим клетку (0,0) в первый цвет. Возьмем два вектора а = (x1,y1) и b = (x2, y2). Покрасим клетки 
в этот же цвет, где k, l — целые числа. Остальные цвета покрасим сдвигом на вектор относительно первого цвета. Количество цветов в этой раскраске равно площади параллелограмма, образованного векторами 
.
Лемма 2: площадь параллелограмма, образованного двумя векторами (x1,y1) и (x2,y2) равна |x2y1 — x1y2|.
Доказательство: Рассмотрим параллелограмм (см. рис. 6), образованный двумя векторами (x1,y1) и (x2,y2): Sпараллелограмма = (x1+x2)(y1+y2) — x1y2 — x1y2 — x2y2 — x1y1 = = x1y1 + x2y1 + x1y2 + x2y2 — x1y2 — -x1y2 — x2y2 — x1y1 = x2y1 — x1y2 Что и требовалось доказать.
Рис. 6
Теорема 3: Если в прямоугольнике отношение большей стороны к меньшей меньше 3/2, но больше 1, то хроматический номер данной фигуры равен
, где 
— длина большей стороны, а — длина меньшей, то есть если 
, то 
.
Доказательство:Найдем такие целые 
, что 
. Буквами A, B, C, D, E, F обозначим наборы различных цветов, которые должны быть в искомой раскраске (см. рис.7).
Рис.7
Повернём исходный прямоугольник на 90 градусов относительно левого верхнего угла. В квадрате C+ могут быть только цвета С или новые (их мы обозначаем как +) Аналогично выясняем для прямоугольника A+. Вследствие этих двух поворотов в прямоугольнике G новый цвет, который мы обозначимc как G. В прямоугольнике D+ может быть либо цвет D, либо новый. В прямоугольнике E+ может быть либо цвет E, либо новый. Теперь рассмотрим самый нижний прямоугольник.
Рис.8
В нем может быть только новый цвет и цвета, которые есть в В, но нет в В+.
Получается, что кол-во цветов, нужных для раскраски плоскости не менее
= 
Из того что 
следует, что 
,
= 
Докажем, что их достаточно. Рассмотрим координатную плоскость. Покрасим целые точки цветами. Пусть в точках A(0,0), B(n,n), C(m+n,m), D(m,m-n) находится цвет G (см. рис. 8). Заметим, что на плоскости не существует прямоугольников , содержащих два цвета G. Тогда кол-во различных цветов равно площади параллелограмма ABCD. 
. Что и требовалось доказать.
Итог
В данной работе найдены хроматические номера «широких» прямоугольников, т. е. тех, у которых отношение большей стороны к меньшей не превосходит двух. Задача разбивается на два случая. Если в прямоугольнике отношение большей стороны к меньшей меньше 2, но больше 3/2, то хроматический номер данной фигуры равен , где — длина меньшей стороны. Для прямоугольников, у которых отношение большей стороны к меньшей меньше 3/2, но больше 1, хроматический номер равен , где — длина большей стороны, а — длина меньшей.
