سوال ۲۰
یک جدول $3 \times 3$ داریم. دو خانه را مجاور گوییم، هر گاه یک ضلع مشترک داشته باشند. می‌خواهیم در هر یک از خانه‌های جدول، یکی از اعداد ۱، ۲ و ۳ را بنویسیم، طوری که عدد هر خانه برابر با تعداد اعداد ۱ در خانه‌های مجاورش باشد. خانه‌ی مرکزی چه اعدادی می‌تواند داشته باشد؟
- ۳
- هر سه عدد
- ۲
- ۲ و ۳
- هیچ یک از سه عدد نمی‌توانند در خانه‌ی وسط باشند
راهنمایی
آیا خانه‌ای از ۴ خانه‌ی گوشه‌ای جدول می‌تواند عدد ۳ به خود بگیرد؟
راهنمایی
اگر یکی از ۴ خانه‌ی گوشه‌ای مقدار ۲ داشته باشد، عدد کدام خانه‌ها به طور یکتا تعیین می‌شود؟
راهنمایی
آیا می‌توان در دو گوشه‌ی مقابل عدد ۲ قرار داد؟
راهنمایی
آیا می‌توان در دو گوشه‌ی مجاور عدد ۲ قرار داد؟
راهنمایی
طبق راهنمایی‌های پیشین، حداکثر یک عدد ۲ در گوشه‌ها قرار دارد. هر دو حالت وجود داشتن یا نداشتن ۲ را بررسی کنید.
پاسخ
گزینه‌ی ۵ درست است.
خانه‌های گوشه تنها می‌توانند شامل اعداد ۱ و ۲ باشند. ادّعا می‌کنیم حداکثر یکی از گوشه‌ها می‌تواند شامل عدد ۲ باشد. فرض کنید در دست کم دو گوشه، عدد ۲ نوشته باشیم. دو حالت داریم:
- دو گوشه‌ی واقع در یک ضلع با عدد ۲ داریم. تمام خانه‌های مجاور این دو عدد، باید شامل عدد ۱ باشند. پس چنین شکلی داریم:
اکنون خانه‌ی وسط جدول بزرگ‌تر از ۱ است. در این صورت عدد ۱ مشخص شده با رنگ قرمز، عدد ۱ مجاور ندارد. تناقض حاصل ثابت می‌کند این حالت امکان ندارد. - دو گوشه‌ی واقع در یک قطر با عدد ۲ داریم. در این صورت نیز چنین شکلی داریم:
اکنون عدد وسط جدول باید ۴ باشد که امکان ندارد.
پس جدولی با خواصّ گفته شده وجود ندارد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
