سؤال ۱۰
نقشه‌ی یک استان در شکل مقابل نشان داده شده است که در آن هر نقطه یک شهر و هر خط یک جاده بین دو شهر است. فاصله‌ی دو شهر $A$ و $B$ برابر است با حداقل تعداد جاده‌هایی که باید طی کنیم تا از $A$ به $B$ برسیم. یک دزد در یکی از این شهرها که از قبل مشخص نیست مخفی شده است. برای پیدا کردن این دزد مجاز هستیم به‌صورت زیر عمل کنیم.
• در ابتدای هر روز یکی از شهرها به نام $A$ را انتخاب و آن را جست‌وجو می‌کنیم. اگر دزد در آن شهر بود که او را دستگیر می‌کنیم. ولی اگر نبود به کمک دستگاهی فاصله‌ی شهر $A$تا شهری که دزد در آن قرار دارد را پیدا می‌کنیم.
• در انتهای هر روز دزد از شهری که در آن قرار دارد به یکی از شهرهای مجاور آن می‌رود (دو شهر را مجاور گوییم اگر با یک جاده به هم متصل باشند). دقت کنید که دزد حتماً جای خود را عوض می‌کند.
حداقل به چند روز نیاز داریم تا مطمئن باشیم که دزد را دستگیر می‌کنیم؟
- ۶
- ۷
- ۸
- ۹
- با گذشت هر چند روز نمی‌توان مطمئن بود که دزد را پیدا کرده‌ایم.
پاسخ
گزینه (۵) درست است.
بهترین حالت آن است که در یک روز از جستجو جای دقیق دزد را شناسایی کنیم. چون از هر شهر حداقل به دو شهر دیگر می‌توان رفت٬ بنابراین با گذشت زمان هرگز جای دقیق دزد معلوم نخواهد شد.