المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۷:سوال ۲۰

سوال ۲۰

یک جدول $3 \times 3$ داریم. دو خانه را مجاور گوییم، هر گاه یک ضلع مشترک داشته باشند. می‌خواهیم در هر یک از خانه‌های جدول، یکی از اعداد ۱، ۲ و ۳ را بنویسیم، طوری که عدد هر خانه برابر با تعداد اعداد ۱ در خانه‌های مجاورش باشد. خانه‌ی مرکزی چه اعدادی می‌تواند داشته باشد؟

  1. ۳
  2. هر سه عدد
  3. ۲
  4. ۲ و ۳
  5. هیچ یک از سه عدد نمی‌توانند در خانه‌ی وسط باشند

پاسخ

گزینه‌ی ۵ درست است.

خانه‌های گوشه تنها می‌توانند شامل اعداد ۱ و ۲ باشند. ادّعا می‌کنیم حداکثر یکی از گوشه‌ها می‌تواند شامل عدد ۲ باشد. فرض کنید در دست کم دو گوشه، عدد ۲ نوشته باشیم. دو حالت داریم:

  • دو گوشه‌ی واقع در یک ضلع با عدد ۲ داریم. تمام خانه‌های مجاور این دو عدد، باید شامل عدد ۱ باشند. پس چنین شکلی داریم: اکنون خانه‌ی وسط جدول بزرگ‌تر از ۱ است. در این صورت عدد ۱ مشخص شده با رنگ قرمز، عدد ۱ مجاور ندارد. تناقض حاصل ثابت می‌کند این حالت امکان ندارد.
  • دو گوشه‌ی واقع در یک قطر با عدد ۲ داریم. در این صورت نیز چنین شکلی داریم: اکنون عدد وسط جدول باید ۴ باشد که امکان ندارد.

پس جدولی با خواصّ گفته شده وجود ندارد.


ابزار صفحه