Всесиб 2022, отборочный этап, 9 класс, задача 5
( баллов) В какое наименьшее число цветов можно окрасить все клетки квадрата так, чтобы в каждой горизонтали, вертикали и диагонали квадрата все клетки имели разный цвет? Пояснение: под диагональю квадрата понимаются все ряды из не менее, чем двух клеток, идущие диагонально от одного края квадрата до другого под углом или к горизонтали.
Ответ
Ответ. В цветов.
Решение. Приведём пример раскраски в цветов, удовлетворяющей условию задачи. Рассмотрим квадрат , и окрасим его требуемым образом в цветов с помощью известного приёма: окраска каждой следующей горизонтали получается из раскраски предыдущей циклическим сдвигом на клетки. Затем выберем в нём левый нижний угловой квадрат , это и будет требуемый пример.
Докажем минимальность цветов. Каждая горизонталь квадрата содержит клеток, поэтому для корректной раскраски потребуется не менее цветов. Предположим, что нам удалось выкрасить квадрат в цветов требуемым в условии образом, тогда клеток каждого цвета будет ровно и располагаться они будут все в различных вертикалях и горизонталях квадрата. Назовём цвет, в который окрашена левая нижняя угловая клетка квадрата чёрным, и покажем, что оставшиеся чёрных клеток не могут располагаться в правом верхнем квадрате в разных вертикалях и горизонталях и при этом не лежать на его главной диагонали, уже контролируемой клеткой . В противном случае можно считать, что не меньше трёх из них располагались бы ниже главной диагонали в фигуре «лесенка» из клеток, состоящей из полосок по клеток соответственно. Однако непосредственно проверяется, что для любой клетки «лесенки» клетки, не находящиеся с окрашенной в одной горизонтали, вертикали или горизонтали могут корректно содержать ещё не более одной чёрной клетки. Возможные положения этой второй чёрной клетки рассмотрены на рисунке. Клетки, контролируемые ей, окрашены светло-серым цветом.
Следовательно, раскрасить квадрат требуемым образом в условии образом в цветов невозможно.