====== سوالات ۲۷ و ۲۸ ======

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


{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۵:275.png |}}



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



{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۵:285.png |}}



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

====== سوال ۲۷ ======

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



<پاسخ>


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



{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۵:27.png |}}



**اثبات:** فرض می‌کنیم با حداقل $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$$

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

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

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



</پاسخ>


====== سوال ۲۸ ======

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


<پاسخ>

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

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


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




</پاسخ>

  * [[سوال ۲۹|سوال بعد]]
  * [[سوالات ۲۴ و ۲۵ و ۲۶|سوال قبل]]