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

Проект МЦНМО
при участии
школы 57
Задача 98544
Темы:    [ Числовые таблицы и их свойства ]
[ Ориентированные графы ]
[ Степень вершины ]
Сложность: 4-
Классы: 8,9
В корзину
Прислать комментарий

Условие

В каждой клетке таблицы  (n–2)×n  (n > 2)  записано целое число от 1 до n, причём в каждой строке все числа различны и в каждом столбце все числа различны. Докажите, что эту таблицу можно дополнить до квадрата n×n, записав в каждую новую клетку какое-нибудь целое число от 1 до n так, чтобы по-прежнему в каждой строке и в каждом столбце числа были различны.


Решение

  В исходной таблице каждое число встречается по  n – 2  раза (по разу в каждой строке). Если дописать в каждый столбец по два недостающих числа, каждое число будет встречаться по n раз (в каждом столбце будет представлен “полный” набор). Значит, каждое число будет дописано ровно по два раза.
  Выпишем числа от 1 до n и соединим отрезками те номера, которые должны быть дописаны в один столбец. Получим граф с n вершинами, из каждой вершины которого выходит по два ребра. Значит, он является объединением нескольких циклов. Ориентируем граф, нарисовав стрелки в каждом цикле в одном направлении. Тогда из каждого числа будет выходить одна стрелка и в каждое число будет входить одна стрелка. Для каждой стрелки поместим число, "из которого" она выходит, в (n–1)-ю строку соответствующего столбца, а число, "в которое" эта стрелка входит, – в n-ю. Тогда каждое число по разу окажется в верхней и нижней строке.

Замечания

5 баллов

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

олимпиада
Название Турнир городов
Турнир
Дата 2001/2002
Номер 23
вариант
Вариант осенний тур, основной вариант, 8-9 класс
Задача
Номер 3

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

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