Prouver le principe du pigeonhole dans les plans de coupe

Question

Exercice 3 de https://massimolauria.net/courses/2015. Lecture6.PDF

Considérez l'ensemble d'inégalités $ x_i + x_j \ leq1 $ pour $ 1 \ Leq i .

Trouver une dérivation de $ \ SUM_ {I= 1} ^ N x_I \ LEQ 1 $ IN $ O ( n ^ 2) $ longueur.

Si c'était juste algèbre, je pouvais simplement montrer par contradiction que, au plus un $ x_i $ pourrait être 1 et être fait mais comment le traduit-il en avions de coupe Ps? Je suppose qu'une idée similaire serait en obtenant $ \ sum_ {i= 1} ^ n x_i \ leq n-1 - (n-2) x_i $ pour tous < SPAN CLASS="MATH-CONTENEUR"> $ I $ Par ajout de $ X_I + X_J $ Pour tous $ 1 \ LEQ J \ LEQ N $ Mais je suis coincé là-bas.

Merci pour votre aide.

Answer 1

La preuve est par induction.Voici l'étape inductive.

Supposons que nous sachions les deux inégalités suivantes: $$ x_1 + \ CDOTS + x_m \ Leq 1 \\ x_2 + \ CDOTS + x_ {m + 1} \ Leq 1 $$ Ajoutez-les pour obtenir $$ x_1 + 2x_2 + \ CDOTS + 2x_m + x_ {m + 1} \ Leq 2 $$ Ajoutez l'axiom $ x_1 + x_ {m + 1} \ Leq 1 $ pour obtenir $$ 2x_1 + \ CDOTS + 2x_ {m + 1} \ Leq 3 $$ Diviser par 2 et arrondi pour obtenir $$ X_1 + \ CDOTS + x_ {m + 1} \ Leq 1 $$ Je vous laisserai remplir les détails restants.