سوال ۱۷

بازی «تنبل‌کُش» یک بازی یک نفره است. که روی یک جدول $۳\times۳$ انجام می‌شود. در ابتدای بازی اعداد ۱ تا ۸ به ترتیب نامعینی در ۸ تا از خانه‌های جدول قرار گرفته‌اند و یکی از خانه‌های جدول خالی است. در هر حرکت می‌توان عدد یکی از خانه‌های مجاور ضلعیِ خانه‌ی خالی را به خانه‌ی خالی انتقال داد. هدف بازی این است که با حداقل تعداد انتقال، اعداد جدول به صورت شکل زیر، مرتّب شوند.

آقای «تنبل»، قصد دارد بدون انجام دادن بازی، حدس بزند که حدّاقل انتقال‌های لازم برای مرتّب کردن یک جدول چند حرکت است. از این رو، وی برای هر یک از اعداد ۱ تا ۸، تعداد حرکت‌های لازم برای انتقال آن عدد به مکان مطلوب در جدول نهایی (با فرض خالی بودن تمام خانه‌های دیگر را) محاسبه کرده و مجموع ابن اعداد ($K$) را به عنوان حدس خود درنظر می‌گیرد.

اگر حدّاقل تعداد انتقال‌های لازم برای مرتّب کردن جدول و رسیدن به جدول نهایی را $A$ بنامیم، کدام یک از گزینه‌های زیر درست است؟ فرض کنید جدول‌های ابتدایی مورد بحث، همواره پس از متناهی حرکت مرتّب می‌شوند.

1. برای تمامی جدول‌های اوّلیه $K\le \frac A2$
2. برای تمامی جدول‌های اوّلیه $\frac A2 \le K \le A$
3. برای تمامی جدول‌های اوّلیه $K\le A$ و جدولی اوّلیه وجود دارد که $K\lt \frac A2$
4. برای تمامی جدول‌های اوّلیه $ A \le K \le 2A$
5. هیچ‌کدام

• سوال بعد
• سوال قبل