======خانه‌های دورنگی======

یک جدول $n \times n$ از اعداد ٬۲٬۱ تا ... $n$ داده شده است. در هیچ سطر یا ستونی از این جدول عدد تکراری یافت نمی‌شود؛ به عبارت دیگر در هر سطر یا ستون تمام اعداد ٬۲٬۱ تا ... $n$ وجود دارند. 

اگر $x$ یک عدد اعشاری باشد٬ $\lfloor x \rfloor$ بزرگ‌ترین عدد صحیحِ کوچک‌تر از $x$ است. با این تعریف٬ ثابت کنید که می‌توان $\lfloor \frac n2 \rfloor$ تا از خانه‌های این جدول را انتخاب نمود که هیچ زوج از خانه‌های انتخاب شده در یک سطر یا ستون قرار نداشته باشند و به ازای هر عدد $1 \le i \le n$ حداکثر دو تا از این خانه‌ها شامل عدد $i$ باشند. 


  * [[سوال دو|سوال بعد]]