سوال ۸

همان سؤال قبل را در نظر بگیرید. چهار خانه شامل عدد ۱ را که هم‌سطر باشند، یک-خطی می‌نامیم. حداکثر مقدار $n$ را بیابید به طوری که جدولی وجود داشته باشد که در آن هیچ چهار خانه‌ی صفر-مستطیلی و هیچ چهار خانه‌ی یک-خطی وجود نداشته باشد؟

  1. $4$
  2. $5$
  3. $6$
  4. $7$
  5. $8$

پاسخ

گزینه (۲) درست است.

برای $n=5$، جدول زیر را در نظر بگیرید:

حال کافی است ثابت کنیم هیچ جدول $6 \times 6$ با شرایط گفته شده وجود ندارد. فرض کنید چنین جدولی وجود دارد. هر سطر این جدول حداقل ۳ خانه‌ی صفر دارد. پس حداقل شامل $\binom{3}{2}$ جفت خانه‌ی صفر است. پس کل جدول شامل حداقل ۱۸ جفت خانه‌ی صفر هم‌سطر است. تعداد جفت ستون‌های ممکن $\binom{6}{2}=15$ است. پس دو جفت هم‌سطر از خانه‌های صفر وجود دارد که ستون‌های‌شان یک‌سان باشد. این چهار خانه یک چهار خانه‌ی صفر-مستطیلی است که تناقض است و حکم ثابت می‌شود.