====== سوال ۷ ======



یک جدول $n \times n$ داریم که در هر خانه‌ی آن یکی از دو عدد $0$ و $1$ نوشته شده است. چهار خانه شامل عدد $0$ را که از محل‌های تقاطع دو سطر و دو ستون به دست آیند،
**صفر-مستطیلی**
می‌نامیم. هم‌چنین چهار خانه شامل عدد ۱ را که هیچ دو تا از آن‌ها هم‌سطر و هم‌ستون نیستند، 
**یک-پراکنده**
می‌نامیم. حداکثر مقدار $n$ را بیابید به طوری که جدولی وجود داشته باشد که در آن هیچ چهار خانه‌ی صفر-مستطیلی و هیچ چهار خانه‌ی یک-پراکنده وجود نداشته باشد.




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


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


برای $n=4$ جدولی در نظر بگیرید که ۳ سطر نخست آن شامل عدد ۱ و سطر آخر آن شامل عدد ۰ باشد. حال کافی است ثابت کنیم هیچ جدول $5 \times 5$ با خاصیت گفته شده وجود ندارد. بیشینه‌ی تعداد خانه‌های ۱ را که هیچ دوتا هم‌سطر یا هم‌ستون نیستند، در نظر بگیرید. حداکثر این مقدار برابر ۳ است. پس حداقل ۲ سطر و ۲ ستون باقی می‌ماند که شامل این خانه‌ها نیست و شامل هیچ عدد ۱ نیست (زیرا در غیر این صورت تعداد این خانه‌ها بیش‌تر می‌شود). پس چهار خانه‌ی صفر-مستطیلی شامل ۰ پیدا می‌شود که تناقض است.


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