|
|
 |
Условие
Имеется сетка, состоящая из квадратов размером 1×1. Каждый её узел
покрашен в один из четырёх данных цветов так, что вершины любого квадрата
1×1 покрашены в разные цвета. Доказать, что найдётся прямая,
принадлежащая сетке, такая, что узлы, лежащие на ней, покрашены в два цвета.
Решение
Предположим противное. Поскольку соседние узлы раскрашены в разные цвета, то на горизонтальной прямой найдутся три подряд идущих узла различных цветов. Обозначим эти цвета через 1, 2 и 3, тогда над и под этими узлами должны находиться узлы 3, 4, 1 (действительно, над и под узлом 2 может быть только узел 4). Таким образом получили, что вверх и вниз чередуются узлы 1, 2, 3 с узлами 3, 4, 1, а значит, эти вертикальные прямые покрашены ровно в два цвета. Получили противоречие.
