Задача 8.
Клетки таблицы 50 × 50 раскрашены в 𝑛 цветов так, что для любой клетки в объединении её строки и столбца встречаются клетки всех 𝑛 цветов. Найдите наибольшее возможное количество клеток синего цвета, если
- 𝑛 = 2;
- 𝑛 = 25.
Ответ на Задачу 8.
Ответ: а) 2450. б) 1300.
Решение:
Докажем, что клеток любого цвета 𝐴, встречающегося в раскраске, не меньше 50. Предположим, это не так, и клеток цвета 𝐴 не больше 49. Тогда найдётся строка без клеток цвета 𝐴, а также найдётся столбец без клеток цвета 𝐴. Но тогда для клетки в пересечении этих строки и столбца условие не выполняется, противоречие. Следовательно, клеток любого цвета 𝐴 не меньше 50.
а) Поскольку клеток не синего цвета не меньше 50, то клеток синего цвета не больше 50 ⋅ 50 − 50 = 2450. Ровно 2450 клеток синего цвета может быть, например, если в нижней строке все клетки — красные, а все остальные клетки таблицы — синие.
б) Поскольку клеток любого не синего цвета не меньше 50, то клеток синего цвета не больше 50 ⋅ 50 − 24 ⋅ 50 = 1300. Ровно 1300 клеток синего цвета может быть, например, если в первых 26 строках таблицы все клетки — синие, а каждая из остальных 24 строк состоит из клеток какого-то одного цвета, причём цвета этих 24 строк различны.
