Всесиб 2022, отборочный этап, 11 класс, задача 3
( баллов) В какое максимальное число цветов нужно окрасить все клетки квадрата так, чтобы для каждой пары различных цветов нашлись две клетки этих цветов, находящиеся либо в одной строке, либо в одном столбце квадрата?
Ответ
Ответ. В цветов.
Решение. Если бы клетки были раскрашены в и более цветов, то нашёлся бы цвет, в который окрашена всего одна клетка. Клеток, расположенных с ней в одной строке или столбце всего , поэтому других цветов, образующих с ней пару, требуемую в условии, не больше — противоречие. Следовательно, клетки могут быть окрашены не более, чем в цветов.
Приведём два существенно различных примера требуемой в условии окраски в цветов, при этом в каждый цвет окрашены ровно по две клетки квадрата.