المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۷:سوال ۱۷

سوال ۱۷

بازی «تنبل‌کُش» یک بازی یک نفره است. که روی یک جدول $۳\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. هیچ‌کدام

پاسخ

گزینه‌ی (۳) درست است.

واضح است که تعداد حرکات واقعی از تعداد حرکات تخمین زده شده بیش‌تر است. زیرامیزان تخمین برای زمانی است که بتوان به صورت مستقیم خانه‌ها را جابه‌جا کرد ولی می‌دانیم برای جابه‌جا شدن یک خانه ممکن است مجبور به جابه‌جایی خانه‌های دیگر نیز بشویم که این باعث بروز حرکاتی بیش‌تر از مقدار تخمین زده شده خواهد شد. از طرفی برای برخی جدول‌ها این مقدار بیش از 2 برابر مقدار تخمین زده شده خواهد بود. شکل زیر را در نظر بگیرید:

گزینه ج صحیح خواهد بود.


ابزار صفحه