یک جایگشت از اعداد ۱، ۲، $\ldots$ و ۹ داریم. در هر مرحله میتوان جایگشت را به دو تکه از عناصر متوالی تقسیم کرد و ترتیب عناصر هر تکه را وارون کرد. برای مثال، جایگشت $\langle 1,2,3,4,5,6,7,8,9\rangle$ میتواند به جایگشت $\langle2,1,9,8,7,6,5,4,3\rangle$ تبدیل شود. توجه کنید تکهها میتوانند تهی باشند. یک جایگشت را مطلوب گوییم، اگر بتوان با شروع از آن و انجام چند مرحله، به جایگشت مرتب شده (از کوچک به بزرگ) رسید. چند جایگشت مطلوب داریم؟
پاسخ
گزینهی ۴ درست است.
اگر اعداد را دور دایره ببینیم، ترتیبشان تنها وارون میشود. پس ترتیب دوری عناصر باید مرتّب شده از کوچک به بزرگ یا بزرگ به کوچک باشد. انتخاب نقطهی شروع جایگشت از روی دایره نیز ۹ حالت دارد. پس $2 \times 9=18$ حالت داریم. دقّت کنید تمام این جایگشتهای ذکر شده قابل ساختن نیز هستند.