|
|
 |
Условие
Клетчатый квадрат 2010×2010 разрезан на трёхклеточные уголки. Докажите, что можно в каждом уголке отметить по клетке так, чтобы в каждой вертикали и в каждой горизонтали было поровну отмеченных клеток.
Решение
Обозначим n = 2010 : 3 = 670. Назовём линией строку или столбец; пронумеруем строки сверху вниз, а столбцы – слева направо. Достаточно отметить клетки так, чтобы при любом k в левых k столбцах и в верхних k строках содержалось бы по kn отмеченных клеток.
Скажем, что уголок смотрит из i-й вертикали влево, если две его клетки находятся в i-й вертикали, а третья – левее. Аналогично определим "взгляд" в других трёх направлениях; каждый уголок, таким образом, смотрит в двух направлениях.
Отметим для начала в каждом уголке среднюю клетку. Теперь в каждом уголке можно либо оставить клетку на месте, либо сдвинуть её ровно в одном из двух направлений, в которые этот уголок смотрит. Выясним, сколько
таких сдвигов надо сделать.
Наложим дополнительное условие: между каждыми двумя соседними линиями все сдвиги должны идти в одну сторону. Рассмотрим, скажем, два соседних столбца: k-й и (k + 1)-й. Предположим, что в левых k столбцах сейчас содержится dk > nk отмеченных клеток. Пусть в k-м столбце есть ak уголков, смотрящих вправо, а в (k+1)-м – bk уголков, смотрящих влево. Тогда в первых k столбцах находится ⅓ (3kn – 2ak – bk) целых уголков, и потому dk = ⅓ (3kn – 2ak – bk) + ak = kn + ⅓ (ak – bk). Значит, чтобы добиться нашей цели, надо сдвинуть sk = ⅓ (ak – bk) ≤ ⅓ ak отмеченных клеток из k-го столбца вправо. В этом случае выделим sk = ⅓ (ak – bk) непересекающихся пар среди ak уголков, смотрящих из k-го столбца вправо, и потребуем, чтобы ровно в одном уголке из каждой пары клетка был сдвинута вправо. Аналогично если dk < nk, то мы выделим sk = ⅓ (bk – ak) непересекающихся пар среди bk уголков, смотрящих из (k+1)-го столбца влево.
Проделав такую операцию с каждой парой соседних линий, мы получим некоторое количество выделенных пар уголков, в каждой из которых надо выбрать по уголку; при этом все выбранные уголки должны быть различными.
Осталось показать, что это возможно.
Соединим два уголка, находящиеся в одной паре, ребром. Заметим, что каждый уголок лежит не более, чем в двух парах: по одной на два направления, в которых он смотрит. Значит, мы получим граф, в котором из каждой вершины выходит не более двух рёбер. Такой граф распадается на циклы и пути. В каждом цикле U1 – U2 – ... – Un – U1 в паре (Ui, Ui+1) выберем уголок Ui, а в паре (Un, U1) – уголок Un. Аналогичную операцию проделаем с путём. Очевидно, что все условия выполнены.
