Олимпиадная задача по комбинаторной геометрии для 8-10 классов: клетка с соседями одного цвета

Предположим, что клетки квадрата n×n удалось раскрасить таким образом, что для любой клетки с какой-то стороны от нее нет клетки одного с ней цвета. Рассмотрим тогда все клетки одного цвета и в каждой из них нарисуем стрелочку в том из четырех направлений, в котором клетки того же цвета нет. Тогда на каждую клетку каемки нашего квадрата, кроме угловых, будет указывать не более одной стрелки, а на угловую – не более двух. Так как клеток каемки всего4n-4, то клеток каждого цвета не более4n . С другой стороны, каждая из n² клеток нашего квадрата раскрашена в один из четырех цветов, т.е.

n² 4·4n.

Для решения задачи теперь достаточно заметить, что последнее неравенство неверно при n=50. Несложно убедиться, что оно неверно при всех n 17, и, следовательно, утверждение задачи верно уже в квадрате17×17– а заодно и в любом большем квадрате.

Уточнив немного рассуждение, можно показать, что клеток каждого цвета не более, чем4n-4, поэтому утверждение неверно уже в квадрате15×15.

Ответ задачи отсутствует