مرتب کردن دیسک‌ها

تعداد $2^k$ دیسک داریم که روی هر کدام، یکی از عددهای ۱ تا $2^k$ نوشته شده است. $k+2$ میله با شماره‌های صفر تا $k+1$ در یک ردیف پست سر هم قرار گرفته‌اند. در ابتدا، دیسک‌ها با یک ترتیب داده شده در میله‌ی صفر روی هم قرار دارند. در هر حرکت می‌توان بالاترین دیسک موجود روی میله‌ی $i$ ام را برداشته و روی دیسک‌های میله‌ی $i+1$ ام قرار داد $(0\leq i\leq k)$. این حرکت را با $T_i$ نمایش می‌دهیم. حالت نهایی مرتب، حالتی است که در آن تمام دیسک‌ها به ترتیب از شماره‌ی ۱ تا $2^k$ (پایین به بالا) روی میله‌ی شماره‌ی $k+1$ قرار گرفته باشند. برای مثال، به ازای $k=1$ دنباله‌ی حرکت‌های لازم برای رسیدن به حالت نهایی مرتب از حالت اولیه‌ای به شکل زیر می‌تواند به صورت $(T_0,T_0,T_1,T_1)$ باشد.

ثابت کنید به ازای هر $k$ می‌توان از هر ترتیب اولیه‌ی دیسک‌ها روی میله‌ی شماره‌ی صفر به یک حالت نهایی مرتب رسید.

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