ВсОШ 2023, 7 класс, задача 8
( баллов) Клетки таблицы раскрашены в цветов так, что для любой клетки в объединении её строки и столбца встречаются клетки всех цветов. Найдите наибольшее возможное количество клеток синего цвета, если
(а) ( балл) ;
(б) ( балла) .
Ответ
Ответ: (а) ; (б) .
Решение. Докажем, что клеток любого цвета , встречающегося в раскраске, не меньше . Предположим, это не так, и клеток цвета не больше . Тогда найдётся строка без клеток цвета , а также найдётся столбец без клеток цвета . Но тогда для клетки в пересечении этих строки и столбца условие не выполняется, противоречие. Следовательно, клеток любого цвета не меньше .
(а) Поскольку клеток не синего цвета не меньше , то клеток синего цвета не больше . Ровно клеток синего цвета может быть, например, если в нижней строке все клетки — красные, а все остальные клетки таблицы — синие.
(б) Поскольку клеток любого не синего цвета не меньше , то клеток синего цвета не больше . Ровно клеток синего цвета может быть, например, если в первых строках таблицы все клетки — синие, а каждая из остальных строк состоит из клеток какого-то одного цвета, причём цвета этих строк различны.
Верное решение пункта (а).
Верное решение пункта (б).