3 تا سوال

جواب 1) کافیه ثابت کنید که از هر ستون لازم و کافیه که تنها آخرین دستور sort اون ستون اجرا بشه. لازمش که بدیهیه چون کافیه سطرها همه‌ی اعدادشون مساوی باشند و فقط در همین یه ستون با هم فرق کنند. کافیش هم تقریبا واضحه چون کلا دستوراتی که قبل از دستور sort_i میان، بود و نبودشون فقط در جابجایی افرادی مهم هست که عضو iامشون با هم یکسانه که خوب یه دستور sort_i دیگه، تغییری در اونها ایجاد نمیکنه.

جواب 2) داریم استقرا میزنیم روی n. اگه یکی از بازه‌ها کاملا در یکی دیگه قرار داشته باشه، کافیه اون بزرگه رو حذف کنیم و سپس بنابر استقرا اون k-1 نقطه‌ی مناسب رو انتخاب کنیم. حالا چون یکی از نقاط داخل کوچیکه هست، پس از بزرگه هم یکی انتخاب شده و تموم. حالا فرض کنیم حالتی هست که هیچ بازه‌ای کاملا داخل دیگری نیست. میایم همه نقاط شروع بازه‌ها رو مرتب میکنیم. حالا زودترین شروع رو در نظر بگیرید. بیاید نقطه‌ی انتهای این بازه رو بعنوان یکی از نقاط انتخابیمون در نظر بگیرید. چون همه‌ی بازه‌هایی که بین شروع و پایان این بازه، باز شدن، بعد از پایان این بازه، بسته شده‌اند(وگرنه کاملا داخله بازه‌ی انتخابیه ما میومده)؛ لذا با انتخاب این نقطه‌ی خاص، از همه‌ی بازه‌هایی که قبل از بسته شدن اولین بازه، باز شده‌اند، یک نقطه انتخاب شده. پس حالا همین کار را ادامه میدهیم. یعنی باز اولین بازه‌ای رو در نظر میگیریم که بعد از تمام شدن اولی، شروع شده. و نقطه‌ی انتهایش را بعنوان یکی دیگر از نقاط انتخابی در نظر میگریم. و همینطور ادامه می‌دهیم. واضحه که همه‌ی بازه‌ها حداقل یک نقطه‌یشان انتخاب شده. حالا میمونه ثابت کنم تعداد نقاط حداکثر k-1 هست. این هم واضحه‌ چون بازه‌هایی که ما نقاط انتهایشان رو انتخاب کرده بودیم، کاملا جدا از هم هستند، لذا اگر تعداد این بازه‌ها بیشتر از k-1 باشد، اونوقت توانسته بودیم که k تا بازه در نظر بگیریم که با هم هیچ اشتراکی ندارند و این با فرض مسئله در تناقضه.

جواب 3) یه گراف جهت‌دار وزندار می‌سازیم. اینطوری که به ازای هر حالت از چینش کتاب‌ها(حداکثر میشه دو به توان n در n فاکتوریل) یک راس میذاریم. و از راس a یک یال جهت‌دار به b با وزن i میذاریم اگر بوسیله‌ی swap_to_i بشه از حالت a به b رسید. توجه کنید که این گراف به ازای هر یال از a به b یک یال با همون وزن از b به a داره.(در حقیقت یه جورایی این رو میشه بصورت گراف بدون جهت دیدش ولی برای اثبات راحت‌تر اینجوری در نظر میگیریمش). حالا اعمال ما مثل طی کردن یک گشت توی این گراف میمونه. چون تعداد یال‌ها متناهیه زمانی ما از یک یال مجددا عبور خواهیم کرد(همینجا جهت‌دار بودنش کار رو راحت میکنه). پس یال e اولین یالی هست -مثلا با وزن i- که پس از طی چند عمل دوباره به خودش میرسه. بدیهیه که نه تنها e بلکه همه‌ی یالهای توی گذر بسته‌ی از e به e همینجوری هستن و چون یه یال توی این گذر هست که وزنش یکه(کافیه اینقدر طبق الگوریتم حرکت کنیم تا برسیم به 1 دیگه). فرض کنیم این یال 1 که بوسیله‌ی حرکات الگوریتممون توی یک گذر بستن، از a به b باشه. پس ما از a با شروع از یال 1 و طی چند حرکت میرسیم به خودش. این دقیقن مثل وقتی هست که ما از حالت اولیمون شروع کردیم به حرکت. نکته اینجان که ما اگه از راس فلان طی چند حرکت به خودش برسیم، از هر راس دیگه‌ای هم اون حرکات خاص رو انجام بدیم باز به خوده اون راسه میرسیم. بعبارت واضح‌تر حرکات ما مستقل از وضعیت کتابا هستن. لذا اگه یه راس بتونه با شروع از 1 برسه به خودش(که راس a الآن اینجوریه) راس شروع ما هم باید براش همین اتفاق بیفته.

خوب اینم از حل سوالا. کلی واستون مرام گذاشتما. آخه بجای اینکه برم بازی کنم دارم واسه شما چرت و پرت تایپ میکنم. البته اگه اینجوری که من نوشتم توی امتحان بنویسید 0.0000000001 هم نمیشید. من تقریبا بعنوان یه راهنمایی-حل نوشتمش.