Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

теорема бонди

Неожиданно красивая теорема Бонди (Bondy, 1972). Пусть есть квадратная матрица, в которой все строки попарно отличаются друг от друга хотя бы в одном столбце. Тогда из нее можно удалить один столбец, так что в оставшейся матрице все еще все строки попарно отличаются. Можно попробовать придумать контрпример для матрицы 3x3, чтобы убедиться наглядно на уровне интуиции, почему контрпримеры не работают и как это получается.

В принципе теорема следует из принципа Дирихле (нельзя посадить n кроликов в n-1 клеток, чтобы в каждой клетке был один кролик). Но прямой чисто логический вывод ее из принципа Дирихле труден - есть работы логиков, показывающие, что такое доказательство должно быть длинным. Доказательство Бонди красиво использует элементарную теорию графов следующим образом.

Пусть есть матрица размером n на n, в которой все строки попарно отличаются. Скажем, что столбец i соединяет две строки, если при удалении этого столбца они становятся идентичными. Скажем, что столбец активен, если он соединяет хоть какую-то пару строк. Мы хотим доказать, что число активных столбцов меньше n. Если это так, то любой неактивный столбец можно удалить, и в оставшейся матрице все еще строки попарно отличаются.

Мы можем прыгать от строки к строке, пользуясь соединяющими столбцами, т.е. меняя каждый раз значение в одном столбце. Таким образом строки можно рассматривать как вершины графа: две вершины соединены ребром, если есть соединяющий их столбец. Все вершины распадаются на какое-то количество компонент связности. Вообще говоря один столбец может участвовать в большом количестве ребер между разными строками. Ясно, что в любом случае

(1) число активных столбцов меньше или равно числу ребер в графе.

Предположим, что в каждой компоненте связности нет циклов, т.е. нет возможности начать из одной строки и вернуться в нее же, не пользуясь дважды одним ребром. Тогда каждая компонента - дерево, а в дереве меньше ребер, чем вершин (на 1). Суммируя по всем компонентам, получаем, что во всем графе

(2) число ребер меньше числа вершин n.

Соединяя (1) и (2), получаем то, что мы хотели доказать.

Но может оказаться, что в каких-то компонентах есть циклы. Посмотрим на любой такой цикл. В нем мы путешествуем от строки к строке, ни разу не пользуясь одним и тем же ребром. Но несомненно нам придется пользоваться дважды одним *столбцом*. Например, если первым шагом мы меняем столбец i, то чтобы вернуться в исходную строку, нам рано или поздно опять придется поменять столбец i, хоть и между другими строками. Возьмем в любом цикле два таких ребра, принадлежащих одному столбцу, и одно из этих ребер выбросим из графа. Это разобьет цикл, но оставит число активных столбцов неизменным (потому что второе ребро того же столбца мы оставили). В новом графе (1) все еще верно, и число активных столбцов в нем то же, что и раньше. Будем продолжать так разбивать циклы, пока их не останется, после чего вышеприведенный аргумент заканчивает доказательство.

Update: красивое геометрическое доказательство hyperpov в комментариях, не пропустите!
Tags: математика
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 38 comments