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