إثبات مبدأ الحمام في قطع الطائرات

Question

التمرينات 3 من https://massimolauria.net/courses/2015. lecture6.pdf

النظر في مجموعة من عدم المساواة $ x_i + x_j \ leq1 $ for $ 1 \ leq i .

ابحث عن اشتقاق $ \ sum_ {i= 1} ^ n x_i \ leq 1 $ في $ o ( n ^ 2) $ الطول.

إذا كانت جبرا فقط، فقد أعرض فقط من خلال التناقض أنه على الأكثر $ X_I $ يمكن أن يكون 1 ويتم القيام به ولكن كيف يترجمها إلى الطائرات ملاحظة؟ أعتقد أن فكرة مماثلة ستكون من خلال الحصول على $ \ sum_ {i= 1} {i 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 + \ CDOTS + 2X_M + X_ {م + 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 $ سأسمح لك بملء التفاصيل المتبقية.