Условие
На клетчатой бумаге отмечены произвольным образом
2000 клеток. Докажите, что среди них
всегда можно выбрать не менее 500 клеток,
попарно не соприкасающихся друг с другом
(соприкасающимися считаются клетки,
имеющие хотя бы одну общую вершину).
Подсказка
Раскрасьте клетки в 4 цвета так, чтобы никакие две клетки
одного цвета не соприкасались.
Решение
Рассмотрим некоторую (бесконечную)
строку и все строки, идущие через одну клетку от нее.
Клетки каждой из этих строк окрасим через одну красным и желтым.
Рассмотрим оставшиеся строки.
Клетки каждой из этих строк окрасим через одну синим и зеленым.
Таким образом, каждая клетка получила свой цвет и никакие две
клетки одного цвета не соприкасаются.
Остается заметить, что так как отмечено 2000 клеток, то клеток
хотя бы одного из цветов не меньше 2000/4=500
(по принципу Дирихле).
Источники и прецеденты использования
