جای‌گشت

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

1. $i$ را برابر ۱ قرار بده.
2. عدد $\pi (i)$ را با $\pi (\pi (i))$ جا به جا کن.
3. به $i$ یک واحد اضافه کن.
4. اگر $\ i \le 2^k$ بود٬ به مرحله‌ی ۲ برو.
5. پایان.

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

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

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

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