Олимпиадная задача: уголки в квадрате 2010×2010 — теория графов и комбинаторика

  Обозначим  n = 2010 : 3 = 670.  Назовём линией строку или столбец; пронумеруем строки сверху вниз, а столбцы – слева направо. Достаточно отметить клетки так, чтобы при любом k в левых k столбцах и в верхних k строках содержалось бы по kn отмеченных клеток.

  Скажем, что уголок смотрит из i-й вертикали влево, если две его клетки находятся в i-й вертикали, а третья – левее. Аналогично определим "взгляд" в других трёх направлениях; каждый уголок, таким образом, смотрит в двух направлениях.

  Отметим для начала в каждом уголке среднюю клетку. Теперь в каждом уголке можно либо оставить клетку на месте, либо сдвинуть её ровно в одном из двух направлений, в которые этот уголок смотрит. Выясним, сколько таких сдвигов надо сделать.

  Наложим дополнительное условие: между каждыми двумя соседними линиями все сдвиги должны идти в одну сторону. Рассмотрим, скажем, два соседних столбца: k-й и (k + 1)-й. Предположим, что в левых k столбцах сейчас содержится  d_k > nk  отмеченных клеток. Пусть в k-м столбце есть a_k уголков, смотрящих вправо, а в (k+1)-м – b_k уголков, смотрящих влево. Тогда в первых k столбцах находится  ⅓ (3kn – 2a_k – b_k)  целых уголков, и потому  d_k = ⅓ (3kn – 2a_k – b_k) + a_k = kn + ⅓ (a_k – b_k).  Значит, чтобы добиться нашей цели, надо сдвинуть  s_k = ⅓ (a_k – b_k) ≤ ⅓ a_k  отмеченных клеток из k-го столбца вправо. В этом случае выделим  s_k = ⅓ (a_k – b_k)  непересекающихся пар среди a_k уголков, смотрящих из k-го столбца вправо, и потребуем, чтобы ровно в одном уголке из каждой пары клетка был сдвинута вправо. Аналогично если  d_k < nk,  то мы выделим  s_k = ⅓ (b_k – a_k)  непересекающихся пар среди b_k уголков, смотрящих из (k+1)-го столбца влево.

  Проделав такую операцию с каждой парой соседних линий, мы получим некоторое количество выделенных пар уголков, в каждой из которых надо выбрать по уголку; при этом все выбранные уголки должны быть различными. Осталось показать, что это возможно.

  Соединим два уголка, находящиеся в одной паре, ребром. Заметим, что каждый уголок лежит не более, чем в двух парах: по одной на два направления, в которых он смотрит. Значит, мы получим граф, в котором из каждой вершины выходит не более двух рёбер. Такой граф распадается на циклы и пути. В каждом цикле  U₁ – U₂ – ... – U_n – U₁  в паре  (U_i, U_i+1)  выберем уголок U_i, а в паре  (U_n, U₁)  – уголок U_n. Аналогичную операцию проделаем с путём. Очевидно, что все условия выполнены.

Ответ задачи отсутствует