Задача 98495

Темы:    [ Числовые таблицы и их свойства ] [ Принцип крайнего (прочее) ]

Сложность: 3+ Классы: 8,9

Условие

Автор: Клепцын В.А.

Дана таблица n×n, в каждой её клетке записано число, причём все числа различны. В каждой строке отметили наименьшее число, и все отмеченные числа оказались в разных столбцах. Затем в каждом столбце отметили наименьшее число, и все отмеченные числа оказались в разных строках. Докажите, что оба раза отметили одни и те же числа.

Решение

Наименьшее число во всей таблице, очевидно, было отмечено оба раза. По условию ни одно из чисел, стоящих с ним в одной строке (одном столбце), не было отмечено ни разу. Поэтому оба раза было также отмечено наименьшее число в таблице, полученной из данной вычеркиванием этих строки и столбца. И так далее.

Замечания

3 балла

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

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