المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۰

یک جدول $4 \times 4$ را در نظر بگیرید. دو خانه از این جدول را مجاور گوییم، اگر یک ضلع مشترک داشته باشند. فرض کنید از یک خانه‌ی این جدول شروع کنیم و در هر مرحله به یک خانه‌ی مجاور برویم، طوری که از هر خانه‌ی جدول دقیقا یک بار عبور کنیم و در انتها به خانه‌ی آغازین باز‌گردیم. به چنین حرکتی، دور همیلتنی می‌گوییم. به چند طریق می‌توان دو خانه از جدول را حذف کرد، طوری که خانه‌های باقی‌مانده‌ی جدول دور همیلتنی داشته باشند؟

  1. ۱۲
  2. ۱۶
  3. ۲۰
  4. ۲۴
  5. ۳۲

پاسخ

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

خانه‌های سیاه شکل زیر سمت راست را در نظر بگیرید. اگر هر کدام از این خانه‌ها حذف شوند، خانه‌ی گوشه‌ی مجاور آن‌ها باید حذف شود؛ زیرا در غیر این صورت درجه‌ی خانه‌ی گوشه‌ی مجاور آن در گراف متناظر، کم‌تر از دو خواهد بود و نمی‌تواند در دور باشد. هم‌چنین اگر یکی از این خانه‌ها به همراه گوشه‌ی مجاور حذف شوند (به $4 \times 2$ حالت)، به شکل زیر دور همیلتنی خواهیم داشت:

پس تنها بررسی حالاتی باقی می‌ماند که دو خانه‌ی حذف شده از گوشه‌ها یا خانه‌های وسط باشند. اگر دو خانه‌ی حذف شده یکی از حالات زیر باشند:

  • در دو گوشه‌ی مقابل
  • در یک گوشه و یک خانه‌ی وسط که به همراه آن گوشه روی یک قطر اصلی هستند
  • در دو خانه‌ی وسط غیر مجاور

آن گاه یا رأس درجه‌ی ۱ وجود دارد، یا با کشیدن یال‌هایی از مسیر که به طور یکتا تعیین می‌شوند (برای مثال یال‌های رئوس با درجه‌ی دو)، مشاهده می‌شود که امکان وجود دور همیلتنی نیست.

اگر دو خانه‌ی حذف‌شده در حالاتی جز حالات بالا باشند به شکل زیر دور همیلتنی وجود دارد:

تعداد حالات انتخاب دو خانه به شکل بالا (به ترتیب از راست به چپ) برابر ۴، ۸ و ۴ است. پس پاسخ نهایی برابر $8+4+8+4 = 24$ است.


ابزار صفحه