جدولی $3 \times 3$ داریم که ۹ شیء مختلف در خانههای آن قرار گرفتهاند. در هر مرحله میتوان یکی از دو کار زیر را انجام داد:
یک جدول را سلطانی گوییم، اگر بتوان آن را با دقیقن ۱۳۹۵ مرحله ساخت. چند جدول سلطانی مختلف داریم؟
پاسخ
گزینهی ۲ درست است.
در یک جایگشت از اعداد، هر گاه عدد $A$ قبل از عدد $B$ آمده باشد، امّا $A>B$ باشد، گوییم یک وارونگی رخ داده است.
بدون از دست دادن کلیت مسئله فرض کنید اشیاء برابر اعداد ۱، ۲، $\ldots$ و ۹ بوده و در ابتدا به ترتیب زیر در جدول قرار گرفته باشند:
عدد ۵ همواره سر جای خود باقی میماند. همچنین اگر با گذاشتن سطرهای جدول به دنبال هم، عناصر جدول را به شکل یک جایگشت ببینیم (که در ابتدا برابر جایگشت مرتّب شده است)، زوجیّت تعداد وارونگیها تغییر میکند (بررسی گامها و تغییرات تعداد وارونگیها به خواننده واگذار میشود). از آنجایی که تعداد وارونگیها در ابتدا زوج و تعداد مراحل فرد است، در انتها باید تعداد وارونگیها فرد باشد. پس به حداکثر $\frac{8!}{2}$ جدول مختلف میتوانیم برسیم.
حال ثابت میکنیم به هر جدولی که تعداد وارونگیهایش فرد باشد، میتوان رسید. هر دو عنصر در جدول (به جز ۵) را میتوان با حداکثر پنج گام جابهجا کرد، طوری که ترتیب بقیهی عناصر با هم نریزد. پس میتوان با حداکثر هشت جابهجایی عنصر (یعنی حداکثر $8 \times 5$ مرحله) از جایگشت ابتدایی به هر جایگشت دلخواه رسید. با توجه به فرد بودن تعداد وارونگیهای جایگشت مقصد، تعداد مراحل طی شده تا رسیدن به آن جایگشت با الگوریتم گفته شده، فرد است. پس از رسیدن به جایگشت دلخواه، دو عنصر قابل جابهجایی با گام نوع ۱ در نظر گرفته و مرتّبن آنها را جابهجا میکنیم تا ۱۳۹۵ مرحله انجام شود. تعداد مراحل انجام این قسمت زوج است، پس عملن پس از پایان کار، مراحل این قسمت تغییری در جایگشت ایجاد نمیکند. پس در انتها به جایگشت مورد نظر میرسیم.
پس پاسخ برابر $\frac{8!}{2}$ است.