Provando o princípio de pombo em planos de corte

Question

Exercício 3 de https://massimolauria.net/courses/2015.proofcomplexity/ Lecture6.pdf

.

Considere o conjunto de desigualdades $ x_i + x_j \ leq1 $ para $ 1 \ leq i .

Encontre uma derivação de $ \ sum_ {i= 1} ^ n x_i \ leq 1 $ na $ O ( n ^ 2) $ comprimento.

Se fosse apenas álgebra eu poderia apenas mostrar por contradição que no máximo uma $ x_i $ poderia ser 1 e ser feito, mas como ele a traduz em planos de corte PS? Eu acho que uma ideia semelhante seria obtendo $ \ sum_ {i= 1} ^ n x_i \ leq n-1 - (n-2) x_i $ para todos < span class="contentor de matemática"> $ i $ através da adição de $ x_i + x_j $ para todos $ 1 \ leq j \ leq n $ mas estou preso lá.

Obrigado pela sua ajuda.

Answer 1

A prova é por indução.Aqui está o passo indutivo.

Suponha que conhecemos as duas das seguintes desigualdades: $$ x_1 + \ cdots + x_m \ leq 1 \\ x_2 + \ cdots + x_ {m + 1} \ leq 1 $$ Adicione-os para obter $$ x_1 + 2x_2 + \ cdots + 2x_m + x_ {m + 1} \ leq 2 $$ Adicione o axiom $ x_1 + x_ {m + 1} \ leq 1 $ para obter $$ 2x_1 + \ cdots + 2x_ {m + 1} \ leq 3 $$ Divida por 2 e redondo para baixo para obter $$ x_1 + \ cdots + x_ {m + 1} \ leq 1 $$ Eu vou deixar você preencher os detalhes restantes.