ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 79255
Темы:    [ Геометрия на клетчатой бумаге ]
[ Раскраски ]
Сложность: 4
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

Автор: Логачев Д.

Лист клетчатой бумаги размером 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 числа закрашенных клеток (в качестве примера можно взять "промежуточный" между этими рисунками).

Ответ

Ответ а) можно; б) и в) вообще говоря, нельзя.

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1973
выпуск
Номер 10
Задача
Номер М228
олимпиада
Название Московская математическая олимпиада
год
Номер 36
Год 1973
вариант
Класс 8
Тур 2
задача
Номер 2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .