المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۵:سوالات ۲۷ و ۲۸

سوالات ۲۷ و ۲۸

  • سه میله با شماره‌های ۲٬۱ و ۳ و چهار مهره سوراخ‌دار با شماره‌های ۱ تا ۴ مطابق شکل زیر داده شده است:

می‌خواهیم با حرکت دادن این مهره‌ها و رعایت قواعد زیر کلیه‌ی مهره‌ها را به صورت زیر بر میله‌ی سوم ببریم:

  • در هر حرکت تنها یک مهره حرکت داده شود.
  • هیچ‌گاه مهره‌ای با شماره‌ی بزرگ‌تر بر روی مهره‌ با شماره‌ی کوچک‌تر قرار نگیرد.

سوال ۲۷

آیا می‌توان با کم‌تر از ۱۱ حرکت این کار را انجام داد؟

پاسخ

اگر $n$ مهره به ترتیب شماره در داخل میله‌ی $A$ باشند و دو میله‌ی $B$ و $C$ خالی باشند٬ آن‌گاه حداقل با $2^n-1$ حرکت می‌توان مهره‌ها را از $A$ به $C$ منتقل کرد به طوری که مهره‌های با شماره‌ی بزرگ‌تر هرگز روی مهره‌های با شماره‌ی کوچک‌تر قرار نگیرند.

اثبات: فرض می‌کنیم با حداقل $h_{n-1}$ حرکت بتوان $n-1$ مهره با شرایط مذکور را از $A$ به $C$ منتقل کرد. ابتدا $n-1$ مهره را با $h_{n-1}$ حرکت از $A$ به $C$ منتقل می‌کنیم. فقط مهره‌ی $n$ در داخل میله‌ی $A$ باقی می‌ماند. با یک حرکت مهره‌ی $n$ را به $C$ منتقل می‌کنیم و با$h_{n-1}$ حرکت $n-1$ مهره‌ی دیگر را از $B$ به $C$ انتقال می‌دهیم. پس مجموع حرکات برای چنین کاری برابر $h_{n-1}+1+h_{n-1}$ یعنی $2h_{n-1}+1$ خواهد بود. پس:

$$h_n=2h_{n-1}+1 \quad\quad\quad (1)$$

می‌دانیم:

$$h_1=1,h_2=3,h_4=7,...$$

با استفاده از رابطه‌ی بازگشتی $(1)$ معلوم می‌شود که:

$$h_n=2^n-1$$

برای حل مسئله مورد نظر الگوریتم زیر را پیاده می‌کنیم:

  • مهره‌ی ۱ را به میله‌ی ۳ منتقل می‌کنیم(یک حرکت).
  • مهره‌ی ۲ را به میله‌ی ۱ منتقل می‌کنیم(یک حرکت).
  • مهره‌ی ۱ را به میله‌ی ۱ منتقل می‌کنیم(یک حرکت).
  • مهره‌ی ۴ را به میله‌ی ۳ منتقل می‌کنیم(یک حرکت).
  • مهره‌ی ۱ تا ۳ را به میله‌ی ۳ منتقل می‌کنیم(با توجه به لم۷٬ حرکت).

پس مجموعا ۱۱ حرکت می‌شود و با کم‌تر از این٬ ممکن نیست.

سوال ۲۸

در صورتی که ۵ مهره با شماره‌های ۱ تا ۵ داشته باشیم به طوری که مهره‌های ۳٬۱ و ۵ در میله‌ی اول و مهره‌های ۲ و ۴ در میله‌ی دوم باشندو آیا می‌توان با کم‌تر از ۲۲ حرکت این مسئله را حل کرد؟

پاسخ

برای حل مسئله الگوریتم زیر را پیاده می‌کنیم:

  • مهره‌ی ۲ را به میله‌ی ۳ منتقل می‌کنیم(یک حرکت).
  • مهره‌ی ۱ را به میله‌ی ۳ منتقل می‌کنیم(یک حرکت).
  • مهره‌ی ۳ را به میله‌ی ۲ منتقل می‌کنیم(یک حرکت).
  • مهره‌ی ۱ را به میله‌ی ۱ منتقل می‌کنیم(یک حرکت).
  • مهره‌ی ۱ را به میله‌ی ۲ منتقل می‌کنیم(یک حرکت).
  • مهره‌ی ۵ را به میله‌ی ۳ منتقل می‌کنیم(یک حرکت).
  • مهره‌ی ۱ تا ۴ را به میله‌ی ۳ منتقل می‌کنیم(با توجه به لم۱۵٬ حرکت).

پس مجموعا ۲۲ حرکت می‌شود و با کم‌تر از این٬ ممکن نیست.


ابزار صفحه