پس از بازی جدول منهتنی(رجوع شود به آزمون مرحله دوم ۱۳۹۴)، فرهاد و علی‌رضا تصمیم گرفتند بازی جدول تنتتنی را انجام دهند. آن‌ها در این بازی یک جدول $m \times n$ دارند ($m, n> 2$) و روی آن بازی می‌کنند. خانه‌ی واقع در سطر $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$ را انتخاب می‌کند. فرض کنید فاصله‌ی خانه‌ی $a_i$ تا $X$ برابر $b_i$ باشد. علی‌رضا دنباله‌ی اعداد $b_1, b_2, \ldots, b_k$ را در نظر می‌گیرد و این $k$ عدد را به ترتیبی دل‌خواه به فرهاد می‌گوید. در واقع تفاوت این بازی با بازی جدول منهتنی این است که فرهاد نمی‌داند هر عدد علی‌رضا مربوط به کدام یک از $a_i$ ها است. حال باید فرهاد با توجه به این $k$ عدد، خانه‌ی مورد نظر علی‌رضا ($X$) را پیدا کند. فرهاد در صورتی می‌برد که خانه‌ی مورد نظر علی‌رضا را بفهمد. فرض کنید هر دو نفر به به‌ترین نحو ممکن بازی می‌کنند و $k$ کم‌ترین عددی باشد که فرهاد روشی برای انتخاب $k$ خانه داشته باشد که ببرد. $k$ را بیابید.

• سوال بعد