سوال

نقشه یک استان در شکل زیر نشان داده شده است که در آن هر نقطه یک شهر و هر خط یک جاده بین دو شهر است. فاصله دو شهر A و B برابر است با حداقل تعداد جاده‌هایی که باید طی کنیم تا از A به B برسیم. یک دزد در یکی از این شهرها که از قبل مشخص نیست مخفی شده است. برای پیدا کردن این دزد مجاز هستیم به صورت زیر عمل کنیم.
در ابتدای هر روز یکی از شهرها به نام A را انتخاب و آن را جست و جو می‌کنیم. اگر دزد در آن شهر بود که او را دستگیر میکنیم. ولی اگر نبود به کمک دستگاهی فاصله شهر A تا شهری که دزد در آن قرار دارد را پیدا می‌کنیم.
در انتهای هر روز دزد از شهری که در آن قرار دارد به یکی از شهرهای مجاور آم می‌رود ( دو شهر را مجاور گوییم اگر با یک جاده به هم متصل باشند). دقت کنید که دزد حتما جای خود را عوض می‌کند.
حداقل به چند روز نیاز داریم تا مطمئن باشیم که دزد را دستگیر می‌کنیم.

الف) 6
ب) 7
ج) 8
د) 9
هـ) با گذشت هر چند روز نمی‌توان مطمئن بود که دزد را پیدا کردی‌ایم
 

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

حالت اول :
اگرفاصله 1 باشد یعنی دزد در شهر B است و درانتهای آن روز به یکی از دو شهر A و یا C خواهد رفت.
روز دوم به شهر C می‌رویم اگر دزد در آن‌جا بود دستگیر می‌کنیم , در غیر اینصورت او حتما در شهر A است که در انتهای روز به ناچار به شهر B خواهد رفت.
روز سوم به شهر B رفته و دزد را دستگیر می‌کنیم.

حالت دوم :
اگر فاصله 2 باشد آنگاه دزد در شهر C می‌باشد که در انتهای روز به یکی از دو شهر D و یا B خواهد رفت.
روز دوم به شهر D رفته و اگر دزد در آن شهر بود او را دستگیر می‌کنیم , در غیر این صورت او حتما در شهر B است که در انتهای روز به یکی از دو شهر C و یا A خواهد رفت.
روز سوم به شهر C رفته و اگر دزد در آن شهر بود او را دستگیر کرده و  در غیر این صورت متوجه  می‌شویم که او حتما در شهر A است که در انتهای روز به ناچار به شهر B خواهد رفت.
روز چهارم به شهر B رفته و دزد را دستگیر می‌کنیم.

حالت سوم :
اگر فاصله 3 باشد آنگاه دزد در شهر D می‌باشد که در انتهای روز به یکی از دو شهر C و یا E خواهد رفت.
روز دوم به شهر C رفته و اگر دزد در آن شهر بود او را دستگیر می‌کنیم در غیر این صورت او حتما در شهر E است که در انتهای روز به یکی از دو شهر F و D خواهد رفت.
روز سوم به شهر D رفته و اگر دزد در آن شهر بود او را دستگیرکرده و در غیر این صورت متوجه می‌شویم که او در شهر F است که در انتهای روز به ناچار به شهر E خواهد رفت.
روز چهارم به شهر E رفته و او را دستگیر می‌کنیم.

حالت چهارم :
اگر فاصله 4 باشد آنگاه دزد در شهر E می‌باشد که در انتهای روز به یکی از دو شهر F و یا D خواهد رفت.
روز دوم به شهر D رفته و اگر دزد در آن شهر بود او را دستگیر کرده و در غیر این صورت متوجه می‌شویم که او در شهر F است که در انتهای روز به ناچار به شهر E خواهد رفت.
روز سوم به شهر E رفته  و دزد را دستگیر می‌کنیم.

حالت پنچم
اگر فاصله 5 باشد , آنگاه دزد در شهر F می‌بباشد که در انتهای روز به شهر E خواهد رفت
روز دون به شهر E رفته و دزد را دستگیر می‌کنیم.