المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۴:تئوری:سوال ۳

دزد و پلیس

یک بازی بر روی یک جدول $2001\times 2001$ انجام می‌گیرد. مهره بازیکن اول «پلیس» و مهره بازیکن دوم «دزد» است. هر مهره در نوبت خود می‌تواند یک واحد در جهت جنوب یا یک واحد در جهت شرق و یا یک واحد در جهت شمال غربی حرکت کند. هم‌چنین مهره پلیس می‌تواند از خانه‌ی گوشه‌ی پایین سمت راست جدول با یک حرکت به خانه‌ی گوشه‌ی بالا سمت چپ جدول برود. پلیس از خانه‌ی وسط جدول شروع می‌کند و دزد از خانه‌ی شمال‌شرق خانه مرکزی شروع می‌کند. اگر پلیس پس از حرکت به خانه‌ای که دزد در آن قرار دارد برسد دزد را می‌گیرد. با این حال اگر دزد پس از حرکت خود به خانه‌ی پلیس برود دستگیر نمی‌شود و بازی ادامه پیدا می‌کند.

  1. نشان دهید دزد می‌تواند حداقل $10^4$ حرکت بکند بدون این‌که دستگیر شود.
  2. هم‌چنین نشان دهید در نهایت پلیس می‌تواند دزد را دستگیر کند.

ابزار صفحه