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

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

Условие

Автор: Анджанс А.

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


Решение

Допустим противное: для каждого i найдутся две строки, отличающиеся только по i-му элементу. Зафиксируем эти пары строк и рассмотрим граф, вершины которого соответствуют строкам, а рёбра – отмеченным парам. В этом графе есть простой цикл (поскольку рёбер столько же, сколько вершин, это следует из задачи 31098 б). Пусть он, например, состоит из строк a1, ..., ak, где ai отличается от ai+1 только по i-му элементу, а ak от a1 – только по k-му. Но k-е элементы в a1 и a2, a2 и a3, ..., ak–1 и ak (а значит, в a1 и ak) совпадают. Противоречие.

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

журнал
Название "Квант"
год
Год 1980
выпуск
Номер 12
Задача
Номер М657
олимпиада
Название Турнир городов
Турнир
Дата 1980
Номер 1
вариант
Вариант
Задача
Номер 2

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

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