Question

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

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.

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

Answer 2

Задача состоит в определении допустимых значений для переменной n, которые удовлетворяют условию задачи. Поскольку мы имеем квадрат 4 на 4, то у нас есть варианты раскраски клеток, в которых каждый цвет представлен только один раз (т.е. каждый цвет используется только для одной клетки) или есть повторяющиеся цвета. Предположим, что в нашем квадрате каждый цвет используется только один раз. Тогда, чтобы в каждом квадрате 2 на 2 были как минимум 2 клетки одного цвета, нам потребуется использовать минимум 2 разных цвета для каждого квадрата 2 на 2. Общее количество клеток в каждом квадрате 2 на 2 равно 4, поэтому общее количество разных цветов, используемых в нашем квадрате 4 на 4, должно быть как минимум равно 8 (2 разных цвета для каждого из 4 квадратов 2 на 2). Значит, n >= 8. Теперь рассмотрим случай, когда у нас есть повторяющиеся цвета в квадрате 4 на 4. Самым неблагоприятным случаем будет ситуация, когда все цвета повторяются, и каждая пара квадратов 2 на 2 содержит только одинаковые цвета. В таком случае нам понадобится всего 4 разных цвета, чтобы каждый из 4 квадратов 2 на 2 был окрашен таким образом, что в каждом квадрате есть минимум 2 клетки одного цвета. Значит, n = 4. Таким образом, допустимые значения для переменной n в данной задаче - n >= 8 и n = 4.