Всесиб 2023, 9 класс, задача 4

Ответ. В цветов.

Решение. Докажем, что максимальное число цветов в условиях задачи не больше . Рассмотрим в квадрате на пять квадратов размера на клетки: четыре угловых и центральный. Угловые квадраты на не пересекаются, а центральный имеет по одной общей клетке с каждым из угловых. По условию, каждый угловой квадрат на содержит клетки не более трёх различных цветов, всего не больше . Но если среди этих четырёх троек цветов в угловых квадратах нет повторяющихся, то центральный квадрат на должен содержать клетки четырёх различных цветов - по одной из каждой тройки, что противоречит условию. Следовательно, общее число различных цветов, в которые окрашены клетки квадрата на не превосходит . Если же хотя бы в одном из угловых квадратов на использовано не больше двух различных цветов, то всего различных цветов сразу не больше .

Пример раскраски квадрата на в цветов, удовлетворяющей условию задачи выглядит так: нижняя горизонталь квадрата красится в различные цвета и , вторая горизонталь - вся в цвет , третья горизонталь в различные цвета и , а четвёртая горизонталь - в цвета .