Решение задачи 314

Условие:

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

Решение:

Покрасим клетки листа в четыре цвета следующим образом: выберем строку, ее клетки покрасим в красный и синий цвета поочередно, так же покрасим строки, идущие через одну клетку от выбранной. Оставшиеся строки покрасим аналогично в зеленый и желтый цвета.

Очевидно, что клетки одного цвета не соприкасаются. По принципу Дирихле найдутся хотя бы 500 отмеченных клеток, покрашенные в один цвет.