مسابقه شماره ۲۰۶
سوال
یک ساختمان قدیمی تعداد زیادی اتاق تودرتو دارد. دو اتاق مجاور تنها از طریق یک در با هم ارتباط دارند و بین انها راه رویی نیست. نقشه‌ی اتاق‌های این ساختمان به صورت مقابل است. در این نقشه در بین دو اتاق با یک خط نشان داده شده است. اتاق A تنها اتاقی است که به بیرون راه دارد. در یکی از اتاق‌های این ساختمان مار کوچک و خطرناکی مخفی شده است و ما می‌خواهیم با استخدام تعدادی نگهبان آن را قبل از خروج بگیریم. فرض کنید:
-جستوجوی هر اتاق وقت زیادی می‌گیرد , بنابراین هر اتاق را فقط یک‌بار می‌توان جستوجو کرد.
-مار می‌تواند از زیر اتاق‌ها و از یک اتاق به هر اتاقی که راه دارد برود و در آن‌جا مخفی شود.
-اگر در مسیر حرکت مار , اتاقی باشد که نگهبانی در آن ایستاده باشد , آن نگهبان مار را می‌بیند و می‌تواند آن را بگیرد.
حداقل چند نگهبان برای گرفتن مار لازم است ؟
پاسخ
در هر یک از نقاط پر رنگ وجود یک نگهبان الزامی است به شرطی که حرکت را از شاخه‌ی بالایی A شروع کنیم.