Question

Помогите решить: Дан квадрат 4 на 4. Его клетки покрашены в n цветов (все цвета используются). Оказалось, что в любом квадрате 2 на 2 присутствуют по крайней мере 2 клетки одного цвета. Какие из данных значений может принимать n?

5 7 8 9 10 11 12 13 14 15 16?

Answer 1

Ответ:от 1 до 11

Пошаговое объяснение:

Пример:

для 11 (меньшие можно получить просто заменяя большие цвета на 1):

1 2 3 4

5 5 3 6

7 8 5 5

9 8 10 11

Оценка:

Каждая пара клеток одного цвета может обслуживать не более двух квадратов. Всего квадратов 9, значит таких пар должно быть не менее 5, т. е. разных цветов не более 11.

На самом деле, одна клетка может входить в более чем одну пару, но в этом случае у этих пар хотя бы один квадрат общий