سوال ۱

یک جدول $(n-1)\times{}(n-1)$ داریم. $k$ پلیس و ۱ دزد با هم بازی می‌کنند. در هر مرحله، پلیس‌ها $k$ نقطه از $n^2$ نقطه‌ی جدول را انتخاب می‌کنند و در این $k$ نقطه مستقر می‌شوند و سپس دزد با دیدن مکان پلیس‌ها، یک نقطه انتخاب می‌کند و به آن‌جا می‌رود. توجه کنید در هیچ مرحله‌ای، پلیس‌ها نمی‌دانند دزد کجاست.

فرض کنید در مرحله‌ای دزد نقطه‌ی $P$ و پلیس‌ها مجموعه‌ی $A$ از نقاط را انتخاب کنند. هم‌چنین در مرحله‌ی قبل، دزد در نقطه‌ی $Q$ و پلیس‌ها در مجموعه‌ی $B$ بوده باشند. دزد تنها در صورتی می‌تواند از نقطه‌ی $Q$ به نقطه‌ی $P$ برود که مسیری از $Q$ به $P$ با استفاده از یال‌های جدول وجود داشته باشد، طوری که از نقاط $A\cap{}B$ نگذرد؛ در غیر این صورت دزد دست‌گیر می‌شود.

در صورتی که پلیس‌ها به طور تضمینی بتوانند در متناهی حرکت، دزد را دست‌گیر کنند، می‌برند و در غیر این صورت می‌بازند.

  1. ثابت کنید اگر $k\ge{}n+1$ باشد، پلیس‌ها می‌برند.
  2. ثابت کنید اگر $k\le{}n-1$ باشد، دزد می‌برد.