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