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