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