====== سوال ۸ ======

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



  - $4$
  - $5$
  - $6$
  - $7$
  - $8$


<پاسخ>
گزینه (۲) درست است.

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

{{ :سوالات_المپیاد:مرحله‌ی_دوم:دوره‌ی_۲۶:selection_014.png |}}

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

</پاسخ>
  * [[سوال ۹|سوال بعد]]
  * [[سوال ۷|سوال قبل]]