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