فرهاد و علی‌رضا در منهتن

فرهاد و علی‌رضا یک جدول $m \times n$ دارند ($m, n> 1$) و روی آن بازی می‌کنند. خانه‌ی واقع در سطر $i$-ام و ستون $j$-ام جدول را با $(i, j)$ نشان می‌دهیم. فاصله‌ی دو خانه‌ی $(r_1, c_1)$ و $(r_2, c_2)$ را، برابر $|r_1 - r_2| + |c_1-c_2|$ تعریف می‌کنیم. برای مثال، در جدول زیر، فاصله‌ی دو خانه‌ی مشخص شده، برابر ۵ است:

فرهاد $k$ خانه‌ی $a_1, a_2, \ldots, a_k$ از جدول را انتخاب می‌کند و به علی‌رضا می‌گوید؛ سپس علی‌رضا یک خانه از جدول مانند $X$ را انتخاب می‌کند و پس از این انتخاب، اعداد $b_1, b_2, \ldots, b_k$ را به فرهاد می‌گوید که $b_i$، فاصله‌ی خانه‌ی $X$ تا خانه‌ی $a_i$ است. حال باید فرهاد با توجه به این $k$ عدد، خانه‌ی مورد نظر علی‌رضا ($X$) را پیدا کند. فرهاد در صورتی می‌برد که خانه‌ی مورد نظر علی‌رضا را بفهمد. فرض کنید هر دو نفر به به‌ترین نحو ممکن بازی می‌کنند.

اگر $k$ کم‌ترین عددی باشد که فرهاد روشی برای انتخاب $k$ خانه داشته باشد که ببرد، تعداد روش‌های انتخاب این $k$ خانه را که فرهاد، با انتخاب آن‌ها به هدفش می‌رسد، به دست آورید. توجه کنید تنها با یافتن $k$، می‌توانید تا ۱۵ نمره بگیرید.

پاسخ

ابتدا ثابت می‌کنیم کمینه‌ی $k$ برابر ۲ است. ابتدا نشان می‌دهیم کمینه‌ی $k$ نمی‌تواند ۱ باشد. اگر فرهاد تنها یک خانه را انتخاب کند و علی‌رضا پاسخ ۱ به او بدهد، از آن‌جایی که هر خانه دست کم ۲ خانه‌ی مجاور (ضلعی) دارد، پس فرهاد نمی‌تواند به طور یکتا خانه‌ی مورد نظر علی‌رضا را مشخص کند. حال نشان می‌دهیم فرهاد می‌تواند با انتخاب ۲ خانه، به هدفش برسد. فرض کنید فرهاد دو خانه‌ی $(1, 1)$ و $(1, m)$ را انتخاب کند و علی‌رضا برای این دو خانه، به ترتیب پاسخ‌های $p$ و $q$ بدهد. اگر خانه‌ی مورد نظر علی‌رضا $(r, c)$ باشد، باید $r + c = p + 2$ و $c - r = q - (m - 1)$ باشد. با حل دو معادله و دو مجهول بالا، $r, c$ به طور یکتا دست می‌آید.

حال ثابت می‌کنیم تعداد روش‌های انتخاب ۲ خانه، طوری که فرهاد به هدفش برسد، ۴ است. اگر فرهاد دو خانه‌ی گوشه‌ای در طول یک ضلع را انتخاب کند، مانند روش بالا فرهاد می‌تواند به هدفش برسد. حال فرض کنید دو خانه به صورتی دیگر انتخاب شوند و این دو خانه، $(r_1, c_1), (r_2, c_2)$ باشند. ثابت می‌کنیم فرهاد نمی‌تواند به هدفش برسد. دو حالت داریم:

  • فرض کنید این دو خانه، دو خانه در دو گوشه‌ی روبه‌روی جدول باشند. دو خانه‌ی مجاور $(r_1, c_1)$ را در نظر بگیرید. اگر علی‌رضا یکی از این دو خانه را انتخاب کند، در هر صورت دنباله‌ی اعدادی که به فرهاد تحویل می‌دهد، یک‌سان است و فرهاد به هدفش نمی‌رسد.
  • فرض کنید دست کم یکی از این دو خانه، در گوشه نباشند. بدون از دست دادن کلیت فرض کنید $(r_1, c_1)$ در گوشه نباشد. پس حداقل ۳ خانه‌ی مجاور دارد. اگر فاصله‌ی دو خانه‌ی انتخابی فرهاد را $d$ در نظر بگیریم، فاصله‌ی خانه‌ی $(r_2, c_2)$ تا ۳ خانه‌ی مذکور تنها می‌تواند $d-1$ یا $d+1$ باشد. فاصله‌ی این ۳ خانه‌ی مذکور تا $(r_1, c_1)$ نیز ۱ است. پس طبق اصل لانه کبوتر، حداقل دو تا از این خانه‌ها هستند که اگر علی‌رضا آن‌ها را انتخاب کند، دنباله‌ی اعداد یک‌سانی به فرهاد تحویل داده می‌شود و فرهاد به هدفش نمی‌رسد.

پس در هر حالت جز ۴ حالت گفته شده، فرهاد نمی‌تواند به هدفش برسد و پاسخ برابر ۴ است.