سوال ۲۰
یک جدول $4 \times 4$ را در نظر بگیرید. دو خانه از این جدول را مجاور گوییم، اگر یک ضلع مشترک داشته باشند. فرض کنید از یک خانه‌ی این جدول شروع کنیم و در هر مرحله به یک خانه‌ی مجاور برویم، طوری که از هر خانه‌ی جدول دقیقا یک بار عبور کنیم و در انتها به خانه‌ی آغازین باز‌گردیم. به چنین حرکتی، دور همیلتنی می‌گوییم. به چند طریق می‌توان دو خانه از جدول را حذف کرد، طوری که خانه‌های باقی‌مانده‌ی جدول دور همیلتنی داشته باشند؟
- ۱۲
- ۱۶
- ۲۰
- ۲۴
- ۳۲
راهنمایی
خانه ها به سه دسته ی •خانه های چهار گوشه •چهار خانه ی وسط •دو خانه ی وسط ردیف بالا و پایین و ستون چپ و راست
حال بررسی کنید از هر دسته چند خانه حذف می شود
پاسخ
گزینه‌ی ۴ درست است.
خانه‌های سیاه شکل زیر سمت راست را در نظر بگیرید. اگر هر کدام از این خانه‌ها حذف شوند، خانه‌ی گوشه‌ی مجاور آن‌ها باید حذف شود؛ زیرا در غیر این صورت درجه‌ی خانه‌ی گوشه‌ی مجاور آن در گراف متناظر، کم‌تر از دو خواهد بود و نمی‌تواند در دور باشد. هم‌چنین اگر یکی از این خانه‌ها به همراه گوشه‌ی مجاور حذف شوند (به $4 \times 2$ حالت)، به شکل زیر دور همیلتنی خواهیم داشت:
پس تنها بررسی حالاتی باقی می‌ماند که دو خانه‌ی حذف شده از گوشه‌ها یا خانه‌های وسط باشند. اگر دو خانه‌ی حذف شده یکی از حالات زیر باشند:
- در دو گوشه‌ی مقابل
- در یک گوشه و یک خانه‌ی وسط که به همراه آن گوشه روی یک قطر اصلی هستند
- در دو خانه‌ی وسط غیر مجاور
آن گاه یا رأس درجه‌ی ۱ وجود دارد، یا با کشیدن یال‌هایی از مسیر که به طور یکتا تعیین می‌شوند (برای مثال یال‌های رئوس با درجه‌ی دو)، مشاهده می‌شود که امکان وجود دور همیلتنی نیست.
اگر دو خانه‌ی حذف‌شده در حالاتی جز حالات بالا باشند به شکل زیر دور همیلتنی وجود دارد:
تعداد حالات انتخاب دو خانه به شکل بالا (به ترتیب از راست به چپ) برابر ۴، ۸ و ۴ است. پس پاسخ نهایی برابر $8+4+8+4 = 24$ است.