|
|
 |
Условие
Лист клетчатой бумаги размером N×N раскрасили в N цветов. (Каждую клеточку закрасили одним из этих N цветов или не закрасили вообще). "Правильной" раскраской называется такая, что в каждом столбце и в каждой строке нет двух клеточек одинакового цвета. Можно ли докрасить лист "правильным" способом, если сначала было "правильно" закрашено
а) N2 - 1 клетка?
б) N2 - 2 клетки?
в) N клеток?
Решение
а) Ответ: можно. Докажем даже более общее утверждение: если
правильно закрашены все клетки квадрата n×n, кроме некоторых
клеток одной строки (или одного столбца), то квадрат можно правильно докрасить.
Пусть, например, недокрашены некоторые клетки первой строки. Покрасим каждую
такую клетку в тот цвет, который ещё не встречается в её столбце. Нужно
доказать, что в первой строке при этом не может оказаться двух клеток
одинакового, скажем, красного, цвета. Для этого рассмотрим прямоугольник
(n − 1)×n, полученный из квадрата вычёркиванием первой строки. Поскольку раскраска была правильной, то в каждой из n − 1 строк прямоугольника красный цвет встречался один раз, — следовательно, всего красных клеток в нем n − 1, а в каждом из n столбцов прямоугольника красная
клетка встречалась не более одного раза, — следовательно, красная клетка не встречалась только в одном из столбцов прямоугольника. Следовательно, лишь в одной клетке первой строки квадрата может появиться этот цвет.
б) и в) Ответ: вообще говоря, нельзя.
Примеры приведены на рисунках (здесь n = 6; аналогичные примеры можно, конечно, привести и для любого n).
Тот же ответ: нельзя верен, конечно, и для промежуточного между n и n2 − 2 числа закрашенных клеток (в качестве примера можно взять "промежуточный" между этими рисунками).
Ответ
