روی n استقرا می زنیم و برای گام استقرا 2 حالت در نظر می گیریم

حالت 1:عدد n ام به آخر جایگشت برسه:در این حالت بعد از اینکه این عدد به آخر جایگشت برسه در مرحله بعد به اول جایگشت میاد و دیگه تکون نمی خوره و طبق فرض از جایی به بعد دیگه جایگشت عوض نمی شه

حالت 2:عدد n ام به آخر جایگشت نرسه:در این حالت دوتا اتفاق خوب می افته اولی این که عدد اول جایگشت تغییر نمی کنه و دومی اینکه اگر به جای n هر عدد دیگه ای هم باشه فرقی نمی کنه پس به جای n عدد اول جایگشت رو می زاریم و اول جایگشت رو حذف می کنیم و طبق فرض از یه جایی به بعد همواره این این جایگشت بدون تغییر می مونه

سلام.

تعریف عدد یک جایگشت : به هر جایگشت یک رشته دودویی از اعداد به طول $n$ نسبت می دیم به طوری که رقم $i$ -امش برابر 1 هست اگر و فقط اگر $π_i =i $. حالا ما یک رشته دودویی به طول $n$ داریم که عدد جایگشت برابر همین رشته هست.برای مثال اگه جایگشت «4 1 3 5 2» رو در نظر بگیریم، داریم :

جــایـــگــاه ها : 1 2 3 4 5

جــایــگشـــت : 4 1 3 5 2

عدد جایگشت : 0 0 1 0 0

که عدد جایگشت برابر 00100 میشه.

حالا بر میگردیم به ادامه سوال. حالا ما میایم روی این عدد ناوردا میزنیم و ادعا می کنیم این عدد هر بار افزایش پیدا می کنه و این ادعا رو اثبات می کنیم.

برهان: تنها کافیه به این نکته توجه کنید که اگر در مرحله ای اولین عدد $x$ باشه ، عددی که در جایگاه $x$ -ام است برابر $x$ نیست. پس رقم $x$ -ام عدد باینری جایگشت برابر 0 هست و وقتی $x$ رقم اول جایگشت رو برعکس می کنیم عدد $x$ به جایگاه $x$ -ام جایگشت میره پس عدد $x$ -ام عدد باینری جایگشت جدید برابر 1 خواهد بود.همچنین چون عدد های بعد از جایگاه $x$ -ام هیچ تغییری نمی کنند پس عدد بزرگتر می شود.برای مثال به مراحل بعد جایگشت بالا تو جه کنید:

مرحله اول:

جــایــگشـــت : 4 1 3 5 2

عدد جایگشت : 0 0 1 0 0

مرحله دوم:

جــایــگشـــت : 5 3 1 4 2

عدد جایگشت : 0 0 0 1 0

مرحله سوم:

جــایــگشـــت : 2 4 1 3 5

عدد جایگشت : 0 0 0 0 1

مرحله چهارم:

جــایــگشـــت : 4 2 1 3 5

عدد جایگشت : 0 1 0 0 1

مرحله پنجم:

جــایــگشـــت : 3 1 2 4 5

عدد جایگشت : 0 0 0 1 1

مرحله ششم:

جــایــگشـــت : 2 1 3 4 5

عدد جایگشت : 0 0 1 1 1

مرحله هفتم:

جــایــگشـــت : 1 2 3 4 5

عدد جایگشت : 1 1 1 1 1

به سادگی می تونید ببینید که عدد های جایگشت بزرگ میشن.

حالا با استفاده از این برهان می تونیم بگیم از اونجایی که عدد جایگشت یک حد خاصی دارد ( $n$ رقم 1) پس این عمل بهمیشه متوقف می شود که متوقف شدن آن متناظر با این است که یا جایگشت کاملأ مرتب شده است یا رقم یک به ابتدای آن رسیده است که حالت اول نیز متناضر با حالات دوم است.پس حکم ثابت است.

سلام.

میایم یه گراف در نظر میگیرییم و برای هر جایگشت یه یال میزاریم.درجه خروجی هر راس یکه.چون گراف متناهیه برای نامتناهی بودن حرکات باید تو یه دور بیفتیم.حالا بزرگترین عددی رو که توی این دور توی جایگاه n ام ظاهر میشه رو k درنظر بگیرید.بعد از یه بار که تو جایگاه n ام قرار میگیره به جایگاه n-k+1 میره .برای اینکه این عدد باز هم بیاد تو جایگاه n ام ، باید یه عدد بزرگتر مساوی با k تو جایگاه n ام قرار بگیره که همچین چییزی ممکن نیست.

موفق باشید!

نمی‌دونم این راه حل درسته یا نه. برای هر i یک راس تعریف می‌کنیم. و هر راس به حداکثر دو راس دیگه وصل میشه . یکی به اون راسی که در جایگاه i ـم قرار داره و دیگری راسی که الان عدد i در اون قرار داره مثلا در جایگشت 1.2.5.4.6.3 راس متناظر شده به 3 به رئوس 4 و 1 وصل هستش. حالا برای راسی که در جایگاه اول از سمت راست قرار داره دو حالت پیش میاد.

1 ؛ عدد یک باشه ؛ در این‌صورت مساله حل شده. 2 ؛ عددی غیر از یک مثلا j باشه. در این‌صورت راس j به 2 راس دیگه وصل هستش که یکی از اون‌ها 1 هستش و دیگری عددی که در جایگاه jـم قرار داره حال، می‌دونیم این راس‌ها تشکیل یک دور میدن. با حذف این دور می‌دونیم که عدد 1 میره تو جایگاه خودش . پس حکم ثابت میشه