Доказательство принципа голубя в режущих плоскостях

Question

Упражнение 3 из https://massimolauria.net/coureses/2015. Лекция6.PDF

Рассмотрим множество неравенств $ x_i + x_j \ leq1 $ для $ 1 \ leq i .

Найти вывод $ \ sum_ {i= 1} ^ n x_i \ leq 1 $ в $ o ( n ^ 2) $ длина.

Если бы это была просто алгебра, я мог бы просто показать противоречие, что не более одного $ x_i $ может быть 1 и быть сделано, но как он переводит его в резки плоскостей PS? Я думаю, что аналогичная идея будет путем получения $ \ sum_ {i= 1} ^ n x_i \ leq n-1 - (n-2) x_i $ для всех SPAN CLASS= «Математический контейнер»> $ i $ через добавление $ x_i + x_j $ для всех $ 1 \ leq j \ leq n $ Но я там застрял.

Спасибо за вашу помощь.

Answer 1

Доказательство по индукции.Вот индуктивный шаг.

Предположим, что мы знаем оба из следующих неравенств: $$ x_1 + \ cdots + x_m \ leq 1 \\ x_2 + \ cdots + x_ {m + 1} \ leq 1 $$ Добавьте их, чтобы получить $$ x_1 + 2x_2 + \ cdot + 2x_m + x_ {m + 1} \ leq 2 $$ Добавьте Axiom $ x_1 + x_ {m + 1} \ leq 1 $ , чтобы получить $$ 2x_1 + \ CDOTS + 2x_ {m + 1} \ leq 3 $$ Разделить на 2 и раунд вниз, чтобы получить $$ x_1 + \ cdots + x_ {m + 1} \ leq 1 $$ Я позволю вам заполнить оставшиеся детали.