راهنمایی حل سوالات مرحله دوم دوره هجده

مساله اول، خانه های دورنگی
خانه‌ی سالم رو، خانه‌ای تعریف می‌کنیم که اگر انتخابش کنیم، هیچ‌کدام از شرط های مساله رو نقض نکنه !
در ابتدا n² خانه‌ی سالم داریم، در هر مرحله یکی از خانه‌های سالم رو به دلخواه انتخاب می‌کنیم و حداقل تعداد خانه‌های سالم باقی‌مانده رو پیدا می‌کنیم. کافیست ثابت کنید در  1 -  [n/2] مرحله اولیه این مقدار از صفر بیشتر خواهد بود !

مساله دوم، برش نواحی
الف)
فرض استقرا : می‌توانیم تمامی خانه‌های k سطر بالا زا به یک ناحیه تبدیل کنیم [این ناحیه را ناحیه اصلی می‌نامیم] و خانه‌های n - k سطر پایینی تغییری نکنند و در هر مرحله A_i حداکثر دو باشد.
گام استقرا : سطر k + 1 اُم را در نظر میگیریم، و سمت چپ ترین خانه‌اش که هنوز به مربع یک در یک است را به ناحیه اصلی اضافه می‌کنیم، واضح است A_i  حداکثر دو است. (چرا؟!)
ب)در هر مرحله تعداد نواحی یک واحد کم می‌شود، پس دقیقا n² - 1 مرحله داریم. چون در هر مرحله  تعداد خط‌هایی که پاک شده‌اند را به عنوان A_i  در نظر می‌گیریم، پس A_i∑ برابر (n-1) * (2n) است.
حال فرض کنید در حالت مینیمم، یکی از A_i   ها از دو بیشتر باشد. طبق لانه کبوتری حداقل یکی از A_i ها برابر یک است. از A_i ای که از دو بیشتر است یک واحد کم می‌کنیم و به A_i ای که برابر یک است یک واحد اضافه می‌کنیم. چون A_i²∑ کمتر شد و ما حالت مینیمم را در نظر گرفته بودیم، پس تناقض ایجاد شده‌است. پس هر کدام از A_i ها حداکثر دو است. حال به راحتی می‌توان فهمید که مقدار مینیمم برابر (n-1) * (4n - 2) است.

مساله سوم، عمو نقاش
جواب مساله برابر 2n - 1 است.
روش : ابتدا سطر های یک تا n را با رنگ های یک تا n رنگ‌آمیزی می‌کنیم، سپس ستون های دو تا n را با رنگ های n+1 تا 2n - 1 رنگ‌آمیزی می‌کنیم.
اثبات بیشینه بودن : فرض کنید تعداد مراحل رنگ‌آمیزی از 2n بیشتر باشد، واضح است حداقل یک سطر یا یک ستون را دور بار رنگ کرده‌ایم، پس می‌توان فرض کرد که مرحله اول رنگ آمیزی آن بی‌تاثیر بوده است، پس آن را حذف می‌کنیم.
فقط حالتی که هر کدام از سطر ها و ستون ها را دقیقا یکبار رنگ کنیم مانده است، در این حالت فرض کنید در اولین مرحله یک سطر را رنگ کرده‌ایم، از آنجا که در مراحل بعدی تمامی ستون‌ها را رنگ کرده‌ایم، پس رنگ این سطر کاملا از بین رفته است، و در این حالت نیز 2n - 1 رنگ مختلف داریم.

مساله چهارم، تلویزیون
از سالن شماره یک شروع می‌کنیم، تا زمانی که شبکه‌ی این سالُن تکراری نشده باشد، توی همین سالن به کارمون ادامه می‌دیم.اگر امروز شبکه شماره i را ببینیم و فردا شبکه شماره j، یعنی مقدار i اُمین خانه جایگشتمان برابر j است. زمانی که برنامه این سالُن تکراری شد، به سالن بعدی می‌رویم و همین روند را ادامه می‌دهیم، ولی اگر اولین برنامه سالن جدید را قبلا دیده بودیم، به سالن بعدی می‌رویم. البته هیچگاه به سالن n ام نمی‌رویم، چون در مراحل قبلی حداقل n - 1 خانه از جایگشت را پیدا کرده‌ایم، و یک خانه باقیمانده، یکتا تعیین می‎شود.

اثبات 2n - 1 بودن این الگوریتم‌ :‌ به ازای هر دور به اندازه P، ما P+1 روز صبر کرده ایم. به ازای هر خانه که در دوری جدید نباشد نیز یک روز صبر کرده ایم. پس اگر تعداد دور های ما m تا باشند، n + m + (n - m) - 1 روز از عمرمان را تلف کرده ایم. :(