|
|
 |
Условие
Дано натуральное число n ≥ 2. Рассмотрим все такие покраски клеток доски n×n в k цветов, что каждая клетка покрашена ровно в один цвет и все k цветов встречаются. При каком наименьшем k в любой такой покраске найдутся четыре окрашенных в четыре разных цвета клетки, расположенные в пересечении двух строк и двух столбцов?
Решение
Сначала покажем, как покрасить клетки в 2n – 1 цвет так, чтобы не было ни одной четвёрки клеток разных цветов, лежащих на пересечении двух горизонталей и двух вертикалей.
Первый способ. Занумеруем горизонтальные ряды сверху вниз чётными числами 0, 2, 4, ..., 2n – 2, а вертикальные
ряды слева направо нечётными числами 1, 3, ..., 2n – 1. Покрасим последовательно 0-й ряд в цвет 0, 1-й ряд – в цвет 1, ..., (2n–1)-й ряд – в цвет 2n – 1. При этом при покраске очередного ряда мы перекрашиваем все клетки, которые были покрашены ранее. В конечной раскраске присутствует 2n – 1 цвет (цвета 0 не останется).
Рассмотрим четыре клетки на пересечении двух горизонталей и двух вертикалей. Один из этих четырёх рядов (вертикалей или горизонталей) был покрашен последним; тогда две его клетки останутся окрашенными
в этот цвет и, следовательно, будут одноцветными.
Второй способ. Покрасим все клетки первой горизонтали H и первой вертикали V в 2n – 1 различный цвет, причём клетку на их пересечении покрасим в цвет c; затем покрасим все оставшиеся клетки также в цвет c. Тогда из четырёх клеток на пересечении любых двух столбцов и двух строк максимум две будут иметь цвет, отличный от c.
Докажем, что при k ≥ 2n требуемая четвёрка обязательно найдётся.
Первый способ. Рассмотрим раскраску клеток в 2n или более цветов. Переформулируем задачу следующим образом. Рассмотрим двудольный граф, вершины которого соответствуют горизонталям и вертикалям доски (всего 2n вершин). Если клетка на пересечении некоторых горизонтали и вертикали покрашена в цвет c, то соединим вершины, соответствующие этим горизонтали и вертикали, ребром цвета c. Разноцветным циклом будем называть цикл, в котором нет двух рёбер одного цвета. Нам требуется доказать, что в построенном графе найдется разноцветный цикл из 4 рёбер.
Докажем, что найдётся разноцветный цикл (возможно, более чем из четырёх рёбер). Выберем по одному ребру каждого цвета – всего не менее 2n рёбер попарно разных цветов. Остальные рёбра временно сотрём.
В полученном графе количество рёбер не меньше количества вершин; как известно, в таком графе найдется цикл.
Теперь найдём в исходном графе кратчайший разноцветный цикл. Пусть это цикл a1b1a2b2...asbsa1 из 2s ребер, где ai – вершины, соответствующие горизонталям доски, а bj – вершины, соответствующие вертикалям. Пусть s > 2. Рассмотрим ребро b2a1. Если его цвет отличен от цвета каждого из ребер a1b1, b1a2 и a2b2, то a1b1a2b2a1 – разноцветный цикл из 4 рёбер; противоречие. Значит, цвет ребра b2a1 отличен от цвета каждого из ребер b2a3, a3b3, ..., akbk, bka1, тем самым цикл a1b2a3b3...akbka1 из 2k – 2 ребер является разноцветным; противоречие.
Второй способ. Индукцией по m + n докажем более общее утверждение: если клетки прямоугольника m×n окрашены в k ≥ m + n цветов, причём все цвета присутствуют, то найдутся 4 разноцветных клетки на пересечении двух строк и двух столбцов.
При m = 1 утверждение верно, ибо раскрасок n клеток в n + 1 цвет не существует; в частности, это доказывает базу индукции при
m + n = 2.
Шаг индукции. Пусть m, n ≥ 2. Назовём цвет c уникальным для столбца V, если цвет c встречается только в этом столбце; аналогично определим цвет, уникальный для строки. Пусть существует столбец, для которого есть не более одного уникального цвета. Тогда выбросим его; в оставшемся прямоугольнике будет встречаться не менее k – 1 ≥ m + n – 1 цвета, значит, по предположению индукции в нём найдётся нужная четвёрка клеток.
Осталось разобрать случай, когда в каждом столбце и в каждой строке хотя бы по два уникальных цвета. Рассмотрим любой столбец V1; пусть в нём два уникальных цвета p и q, и какие-то клетки этих цветов стоят в строках H1 и H2 соответственно. В H1 есть два уникальных цвета; один из них отличен от p. Пусть этот цвет – r, и в H1 клетка этого цвета стоит в столбце V2 ≠ V1. Тогда построенные два столбца и две строки – требуемые. Действительно, на их пересечении в V1 стоят два разных цвета, уникальных для V1; значит, они не встречаются в V2. Цвет r ≠ p уникален для H1, значит, он не встречается в H2. Итого, в нашем пересечении есть различные цвета p, q, r, а также клетка цвета, отличного от них.
Ответ
k = 2n.
