المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۳:سوال ۱۱

سؤال ۱۱

همان سؤال قبل اگر نقشه‌ی استان به‌صورت مقابل باشد.

  1. ۴
  2. ۵
  3. ۶
  4. ۷
  5. باگذشت هر چند روز نمی‌توان مطمئن بود که دزد را پیدا کرده‌ایم.

پاسخ

گزینه (؟) درست است.

شهرها را مطابق شکل مقابل نام‌گذاری می‌کنیم:

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

اگر فاصله ۱ باشد یعنی دزد دزد در شهر $B$ است و در انتهای آن روز به یکی از دو شهر $A$ و یا $C$ خواهد رفت.

  • روز دوم به شهر $C$ می‌رویم که اگر دزد در آن‌جا بود دستگیر می‌کنیم٬ در غیر این صورت او حتما در شهر $A$ است که در انتهای روز به ناچار به شهر $B$ خواهد رفت.
  • روز سوم به شهر $B$ رفته و دزد را دستگیر می‌کنیم.

اگر فاصله ۲ باشد آن‌گاه دزد در شهر $C$ می‌باشد که در انتهای روز به یکی از دو شهر $D$ و یا $B$ خواهد رفت.

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

اگر فاصله ۳ باشد آن‌گاه دزد در شهر $D$ می‌باشد که در انتهای روز به یکی از دو شهر $C$ و یا $E$ خواهد رفت.

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

اگر فاصله ۴ باشد آن‌گاه دزد در شهر $E$ می‌باشد که در انتهای روز به یکی از دو شهر $F$ و یا $D$ خواهد رفت.

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

اگر فاصله ۵ باشد آن‌گاه دزد در شهر $F$ می‌باشد که در انتهای روز به شهر $E$ خواهد رفت.

  • روز دوم به شهر $E$ رفته ودزد را دستگیر می‌کنیم.

ابزار صفحه