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



