Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱

یک جدول ‎(n1)×(n1)‎ داریم. ‎k‎ پلیس و ‎۱‎ دزد با هم بازی می‌کنند. در هر مرحله، پلیس‌ها ‎k‎ نقطه از ‎n2‎ نقطه‌ی جدول را انتخاب می‌کنند و در این ‎k‎ نقطه مستقر می‌شوند و سپس دزد با دیدن مکان پلیس‌ها، یک نقطه انتخاب می‌کند و به آن‌جا می‌رود. توجه کنید در هیچ مرحله‌ای، پلیس‌ها نمی‌دانند دزد کجاست.

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

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

  1. ثابت کنید اگر ‎kn+1‎ باشد، پلیس‌ها می‌برند.
  2. ثابت کنید اگر ‎kn1‎ باشد، دزد می‌برد.

ابزار صفحه