المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی اول:دوره‌ی ۹:سوال ۲۹

سوال ۲۹

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

حداقل به چند پلیس نیاز داریم تا به ازای هر موقعیت اولیه دزد و پلیس‌ها٬ مطمئن باشیم که می‌توانیم دزد را دستگیر کنیم؟

  1. ۱
  2. ۲
  3. ۳
  4. ۴
  5. ۵

پاسخ

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

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


ابزار صفحه