======جای‌گشت======

به دنباله‌ی $\pi$ به طول $n$ از اعداد ${1,...,n}$ یک «جای‌گشت» می‌گوییم اگر و تنها اگر هرکدام از این اعداد دقیقاً یک بار در دنباله ظاهر شود. عددی که در مکان $i$ام جای‌گشت ظاهر می‌شود را با $\pi (i)$ نمایش می‌دهیم. برای مثال 
<۱٫۳٫۴٫۲> :$\pi$ 
یک جای‌گشت به طول ۴ می‌باشد. پدر علی به او جای‌گشتی از اعداد ۱ تا $2^k$ داده است ($1 \le k$). علی می‌خواهد کاری کند که به ازای هر $ 1 \le i \le n = 2^k$٬ داشته باشیم $\pi (i) = i$. او برای این کار از الگوریتم زیر استفاده می‌کند:
  - $i$ را برابر ۱ قرار بده.
  - عدد $\pi (i)$ را با $\pi (\pi (i))$ جا به جا کن.
  - به $i$ یک واحد اضافه کن. 
  - اگر $ \ i \le 2^k$ بود٬ به مرحله‌ی ۲ برو.
  - پایان.

مثلاً٬ پس از اجرای الگوریتم فوق برای مثال بالا 
(<۱٫۳٫۴٫۲> :$\pi$)٬ به جای‌گشت 
<۱٫۲٫۳٫۴> :$\pi'$
می‌رسیم. 

الف) ثابت کنید با $k$ بار اجرای الگوریتم فوق٬ تمام اعداد سر جای خود قرار می‌گیرند. 

ب) برای هر عدد $k$٬ جای‌گشتی مثال بزنید که نتوان با $k-۱$ بار اجرای الگوریتم فوق تمام اعداد را در جای خود قرار داد. 



  * [[سوال سه|سوال بعد]]
  * [[سوال یک|سوال قبل]]