Question

В квадрате 4*4 клетки раскрашены в разные цвета так, чтобы в каждом прямоугольнике 1*3 было две клетки одинакового цвета. Какое максимальное количество цветов может быть использовано.

Answer 1

Покажем, что количество используемых цветов не может быть больше 9. По условию в каждом прямоугольнике размером 1 на 3 клетки имеются две клетки одинакового цвета. Заметим, что в каждой строке и каждом столбце квадрата 4 на 4 клетки есть два таких прямоугольника, а это означает, что количество различных цветов в каждой строке и каждом столбце квадрата ≤ 3. Предположим противное и допустим, что количество используемых цветов > 9 и равно, к примеру, 10. Пусть в каждой строке и каждом столбце квадрата 4 на 4 клетки имеются три различных цвета. Но, тогда найдется такая строка и такой столбец, в которых будет 4 различных цвета, а это значит что в них не найдется прямоугольника размером 1 на 3 клетки с двумя клетками одинакового цвета. Приходим к противоречию, значит количество используемых цветов не может быть больше 9 и максимальное количество цветов равно 9. Пример раскраски с девятью цветами изображен на рисунке.

Ответ: 9 цветов.

Answer 2

Максимальное количество цветов, которое может быть использовано в таком раскрашенном квадрате, равно 4.

Рассмотрим возможные варианты раскраски:

1. Если в первой строке первые две клетки одного цвета, то третья клетка обязательно будет иметь другой цвет. Четвертая клетка тоже будет иметь другой цвет, иначе в прямоугольнике 1*3 будут три клетки одного цвета. Таким образом, в первой строке у нас уже есть два разных цвета. Аналогично, во второй, третьей и четвертой строках будут использованы ещё два разных цвета. Всего получаем 2+2+2+2=8 цветов.

2. Если в первой строке первые две клетки разных цветов, то третья клетка обязательно будет иметь один из этих двух цветов. Четвертая клетка должна иметь другой цвет, иначе в прямоугольнике 1*3 будут три клетки одного цвета. Таким образом, в первой строке у нас уже есть два разных цвета. Аналогично, во второй, третьей и четвертой строках будут использованы ещё два разных цвета. Всего получаем 2+2+2+2=8 цветов.

Таким образом, максимальное количество цветов, которое может быть использовано, равно 8.