Probando el principio de palo en los planos de corte.

Question

Ejercicio 3 de Https://Massimolauria.net/courses/2015.prootherComplexity/ lecture6.pdf

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

Encuentre una derivación de $ \ sum_ {i= 1} ^ n x_i \ leq 1 $ en $ o ( n ^ 2) $ longitud.

Si fuera solo el álgebra, podría mostrar por contradicción que a la mayoría de un $ x_i $ podría ser 1 y hacerse, pero ¿cómo lo traduce en aviones de corte? ¿PD? Supongo que una idea similar estaría obteniendo $ \ sum_ {i= 1} ^ n x_i \ leq n-1 - (n-2) x_i $ para todos < Span Class="Math-contenedor"> $ i $ a través de la adición de $ x_i + x_j $ para todos $ 1 \ leq j \ leq n $ Pero estoy atrapado allí.

Gracias por su ayuda.

Answer 1

La prueba es por inducción.Aquí está el paso inductivo.

Supongamos que conocemos las dos siguientes desigualdades: $$ x_1 + \ cdots + x_m \ leq 1 \\ x_2 + \ cdots + x_ {m + 1} \ leq 1 $$ Añadirlos a conseguir $$ x_1 + 2x_2 + \ cdots + 2x_m + x_ {m + 1} \ leq 2 $$ Agregue el axiom $ x_1 + x_ {m + 1} \ leq 1 $ para obtener $$ 2x_1 + \ CDOTS + 2x_ {M + 1} \ leq 3 $$ Dividir por 2 y redondear hacia abajo para obtener $$ x_1 + \ cdots + x_ {m + 1} \ leq 1 $$ Te dejaré completar los detalles restantes.