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