سوال ۱

افشین در یک خانه از جدول $n\times n$ ($n>1$) قرار دارد و پیمان می‌خواهد او را دستگیر کند. در هر گام افشین باید به یکی از خانه‌های مجاور (مجاور ضلعی) محل‌ کنونی‌اش که مسدود نشده باشد، برود. پیمان نیز در هر گام می‌تواند یک خانه را انتخاب کند و همه‌ی خانه‌های هم‌سطر و هم‌ستون آن را مسدود کند. افشین در دو صورت زیر دستگیر می‌شود:

اگر پیمان نتواند محل افشین در جدول را ببیند، حداقل چند خانه باید انتخاب کند تا مطمئن باشد افشین را دستگیر کرده است؟

  1. $\lceil{\frac{n}{2}}\rceil$
  2. $\lceil{\frac{n}{4}}\rceil$
  3. $\lfloor{\frac{n}{2}}\rfloor$
  4. $n$
  5. $n-1$

پاسخ

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

برای دستگیر کردن افشین، پیمان کافیست تا برای هر $1\leq i \leq \lfloor \frac{n}{2} \rfloor$، خانه‌ی $(2i,2i)$ از جدول را انتخاب کند. در این صورت افشین یا در یک خانه‌ی مسدود است یا در خانه‌ای مجاور یک خانه‌ی مسدود، پس دستگیر می‌شود. علاوه بر این این تعداد خانه لازم نیز می‌باشد زیرا در غیر این‌صورت دو خانه‌ی مجاور هستند که هیچ کدام مسدود نشده‌اند و افشین می‌تواند بین آن دو به صورت متناوب حرکت کند.