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