Олимпиада имени Леонарда Эйлера 2019-2020 учебный год, II тур дистанционного этапа

Каждую клетку доски $7\times 7$ закрасили в один из девяти цветов. Известно, что у каждой клетки, не примыкающей к краю доски, есть соседи (по горизонтали, вертикали или диагонали) всех восьми цветов, не совпадающих с цветом этой клетки. Докажите, что клеток каждого из девяти цветов не меньше четырех. ( Р. Женодаров )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Рассмотрим четыре квадрата $3\times 3$, лежащие в углах доски. Центр каждого из них покрашен в какой-то цвет и граничит с клетками, покрашенными во все остальные цвета. Поэтому в каждом из четырех квадратов есть клетки всех девяти цветов. Поскольку эти квадраты не пересекаются, клеток каждого цвета не менее 4.