راه حل اول) استقرا (بازگشتی)

ابتدا با برهان خلف ثابت می‌کنیم سمت‌راست‌ترین عدد یا ۱ هست یا ۱۰.

فرض کنیم سمت‌راست‌ترین عدد $x$ باشه که نه ۱ هست و نه ۱۰ (فرض خلف). فرض هم کنیم سمت‌چپ‌ترین عدد جایگشت، عدد $a$ هست. حالا $a$ و $x$ دو حالت دارن:

1. اگه $a\lt x$ باشه، می‌یایم دنباله‌ی $\langle x+1, x+2, \cdots x+k \rangle$ رو در نظر می‌گیریم. از اون‌جا که $x \lt 10$ پس این دنباله تهی نیست. این اعداد به‌ترتیب برای این‌که ارضا بشن چاره‌ای ندارند جز این‌که هر کدوم الزاماً سمت چپ عدد قبلی‌شون باشن. اما آخرین عدد این دنباله که $x+k$ باشه، باید حتماً ابتدای جایگشت یعنی همون $a$ باشه؛ که این با فرض $a\lt x$ در تناقض هست. پس به تناقض فرض خلف می‌رسیم.
2. اگه $a \gt x$ باشه، می‌یایم دنباله‌ی $\langle x-1, x-2, \cdots x-m \rangle$ رو در نظر می‌گیریم. مشابه حالت قبلی چون $x \gt 1$ پس این دنبال تهی نیست. و این اعداد برای ارضا شدن باید الزاماً هر کدوم سمت چپ قبلی باشن تا جایی که به $x-m$ برسیم که باید سمت‌چپ‌ترین عدد جایگشت یعنی همون $a$ باشه. که مشابه حالت قبلی با فرض $a \gt x$ این بار هم به تناقض می‌رسیم.

پس در هر دو حالت به تناقض رسیدیم. پس عدد اول دنباله یا ۱ هست یا ۱۰.

تعداد حالت‌هایی که تهشون ۱۰ باشه می‌شه جواب همین مسئله برای جایگشت ۱ تا ۹. برای شمردن حالت‌هایی که تهشون ۱ باشه، هم کافیه همه جایگشت‌های ۱ تا ۹ که شرط مسئله دارن رو بسازیم، بعد همه اعدادشون رو یکی اضافه کنیم (که بشن ۲ تا ۹) بعد این ۱ رو بذاریم تهش. پس اگه جواب مسئله رو $T(10)$ در نظر بگیریم داریم $T(10) = 2 \times T(9)$. با داشتن پایه‌ی $T(2)=1$ به فرمول $T(n)=2^{n-1}$ می‌رسیم و جواب برای $n=10$ برابر $2^9$ می‌شه.

راه حل دوم) ترکیبیاتی (صریح)

فرض کنیم عدد سمت چپ دنباله $b$ باشه. عدد بعدی (سمت‌راستیش) الزاماً باید یا $b-1$ باشه یا $b+1$ و توی بازه‌ی ۱ تا $n=10$ هم باشه. مستقل از این‌که دو عدد اول $\langle b, b-1\rangle$ باشن یا $\langle b, b+1\rangle$، عدد بعدتری (سومی از سمت راست) حالا باید یا یکی بیشتر از بیشینه‌ی این دو عدد اول باشه، یا یکی کمتر از کمینه‌ی دو عدد اول (و در محدوده ۱ تا ۱۰ باشه). با همین رویه می‌بینیم که $k$ تا عدد اول دنباله همیشه باید متوالی باشن و عدد $k+1$اُم حداکثر دو تا امکان داره، یا یکی بیشتر از بیشینه‌ی اعداد قبلی، یا یکی کمتر از کمینه‌ی اعداد قبلی (در محدوده ۱ تا ۱۰).

حالا می‌یایم از هر جایگشت مطلوب یه رشته‌ی حرفی می‌سازیم به این صورت که ابتدا سمت‌چپ‌ترین عدد دنباله رو می‌نویسیم، بعد برای هر کدوم از اعداد بعدی اگه یکی بیشتر از بیشینه‌ی قبلی‌ها بود $U$ و اگه یکی کمتر از کمینه‌ی قبلی‌ها بود $D$ می‌نویسیم. مثلاً جایگشت مطلوب $\langle 5,4,6,3,7,8,9,10,2,1\rangle$ برابرست با رشته‌ی $5DUDUUUUDD$. واضحه که از هر رشته دقیقاً یک جایگشت ساخته می‌شه. پس کافیه بیایم این رشته‌های مطلوب رو بسازیم و بشماریم. می‌دونیم که همه رشته‌ها مطلوب نیست. مثلاً رشته‌ای که با ۱ شروع بشه توش نمی‌تونه $D$ ظاهر بشه!

برای این کار کافیه دقت کنیم که رشته‌ای که با $k$ شروع بشه، دقیقاً توش $k-1$ تا دونه $D$ هست و الباقی کاراکترهای رشته‌ی $n-1$ حرفی همگی $U$ هستن. چنین رشته‌ای هم الزاماً مطلوب هست. (چرا؟)

پس کافیه چنین رشته‌هایی رو بشماریم که تعدادشون می‌شه $\sum_{k=1}^{n} {n-1 \choose k-1} =\sum_{i=0}^{n-1} {n-1 \choose i} = 2^{n-1}$.

ابتدا ثابت کنید عدد سمت راست یا یک است یا 10 .

سپس ثابت کنید عدد دوم از سمت راست برابر با ماکزیمم یا مینیمم اعداد باقیمانده است .

این کار را همین طور تکرار کنید تا به جواب $2^9$ برسید .