المپیاد کامپیوتر

سؤالها  http://www.mmehraban.blogfa.com/post-17.aspx
جوابها :

روز1
1)
این سوال یک حکم ضعیف داشت زیرا می توان ثابت کرد می توان |n\2 | خانه انتخاب کرد که هر کدام حداکثر 1 بار آمده باشد
ابتدا عدد یک را از ستون اول انتخاب می کنیم سپس عدد 2 را در این ستون در نظرگرفته و سراغ سطری می رویم که شامل عدد یک انتخابی و این عدد 2 در این ستون نباشد سپس عدد 2 را در آن انتخاب می کنیم
به همین ترتیب در هر مرحله تمام اعدادی را که قبلا انتخاب کردیم انتخاب میکنیم و مثلا اگر عدد بعدی که می خواهیم انتخاب کنیم k باشد آنگاه تمام ستون هایی را که قبلا از آنها عدد انتخاب کردیم را انتخاب کرده و تمام سطرهای شامل این k ها را در نظر می گیریم و عدد k را از سطری غیر از این سطر ها و سطرهایی که قبلا از آنها عدد انتخاب کردیم انتخاب می کنیم بدین ترتیب هم اعداد متمایزند و هم هیچکدام در هیچ سطر یا ستونی نیستند زیرا همیشه ما ستونی داریم که عدد بعدی را از آن انتخاب کنیم زیرا تعداد اعدادی که ما قبلا انتخاب کردیم حد اکثر 1-|n\2 | تا هست و عدد بعدی حداکثر در 1-|n\2 | تا سطر متمایز دیگر آمده و چون می دانیم n بزرگتر است از 2-|n\2 |2 پس همواره سطری برای انتخاب ما وجود دارد

2)
الف)این قسمت سوال بر خلاف قسمت قبلی بسیار بدیهی است به این صورت عمل می کنیم که خانه بالا و سمت چپ را به صورت مارپیچ با خانه های 1*1 ادغام میکنیم
ب) دو دنباله a ها و b ها را در نظر بگیرید اولی فقط 1 و2 دومی بیشتر از 2می دانیم تعداد این ها برابر است زیرا در هر مرحله یک شکل از مجمه n به توان 2 شکل کم می شود و در نهایت یکی می مونه پس در نهایت n به توان 2 منهای یک تا عضو a ها و همین قدر b ها دارند
یک های موجود در مجموعه a ها را حذف و به همین مقدار از مجموعه b ها یک کم می کنیم سپس :
برهان خلف :بنابر قضیه کوشی شوارتز اگر a ها به توان 2 را در تعدادشان ضرب کنیم بزرگتر مساوی مجموعشان به توان 2 است و چون همه a ها برابر 2 است پس حالت تساوی رخ می دهدولی اگر همین کار را برای b ها بکنیم حالت تساوی رخ نمی دهد زیرا در بینشان اعداد برابر وجود ندارد و چون مجموع b ها و a ها برابر است پس توان دوم a ها کوچکتر است از توان دوم b ها و چون می دانیم تهدادشان برابر است پس با استفاده از 2 ها و 1 ها به طور یکتا می توان این دنباله را تشکیل داد که تعداد 2 ها و 1 ها در آن همواره ثابت است.
این کلیت اثبات است اما نواقصی دارد که به دلیل طولانی بودن در اینجا نمی گنجد.

3)
از انتها به ابتدا رنگ آمیزی را بررسی میکنیم در ابتدا یک جدول n درn داربم می دانیم آخرین رنگ یا یک سط یا یک ستون را شامل می شود پس این ستون یا سطر را از جدول برداشته و بقیه را بررسی می کنیم حال یک جدول n-1 درn داریم در هر مرحله از آخر به ترتیب به اول رنگ ها را به این ترتیب از جدول جدا می کنیم چون می دانیم در هر مرحله یکی از ستون یا زا سطر کم میشود و این کار زمانی تمام می شود که یا ستون یا سطر برابر صفر گردد پس حداکتر ما 2n-1 رنگ می توانیم استفاده کنیم

4)
الگوریتم این سوال به این صورت است : ابتدا به خانه اول می رویم و در آنجا می مانیم تا یک شبکه را دوبار ببینیم سپس به سالن بعدی می رویم اگر شبکه ای که در آنجا می بینیم را قبلا دیده ایم به سالن بعد می رویم وگر نه در آنجا میمانیم تا یک شبکه را ببینیم که قبلا دیده ایم اثبات درست بودن این الگوریتم هم ساده است
روز2
5)
باید ثابت کنیم شکل مورد نظر یک ستاره است که یک شهر در مرکز قرار دارد و اگر d برابر 2k باشد شاخه های این ستاره هر کدام k تا شهر را شامل می شود و اگر d برابر 2k+1 باشد یک شاخه شامل k-1 راس و بقیه شامل K+1 راس هستند و صورت کلی این تعداد برابر است با n -1 منهای کف d\2 سپس حاص این عبارت تقسیم بر سقف d\2 سپس حاصل کف این عبارت به علاوه یک

6) n کلمه زبان پیشوند آزاد را در نظر می گیریم و برای هر کلمه ابتدا تمام حروف آن را نوشته سپس مجددا حروف آن را از آخرین حرف به اوین حرف دنبال آن می نویسیم و به سادگی ثابت می شود که این کامه هم پیشوند و هم پسوند آزاد است بنابراین چون وزن آن برابر 2x است پس حکم ثابت می شود

7)این سوال انصافا سخت ترین و قشنگترین سوال این دوره بود اما به دلیل سختی تایپ آن نمی توانم به صورت کامل اثبات را بنویسم
و تنه ابه صورت کلی راه حل بسنده می کنم
به این صورت عمل می کنیم که n زیر مجموعه 3 عضوی را در نظر می گیریم و درجه هر عدد را تعداد تکرار آن در این زیر مجموعه ها می نامیم سپس اعداد را به ترتیب از تعداد درجه کم به تعداد درجه زیاد مرتب می کنیم در هر مرحله از درجه کمتر شروع می کنیم و به ترتیب اعداد را از درجه کمتر به بیشتر بررسی می کنیم در هر مرحله یک عدد باقیمانده را که درجه آن از بقیه کمتر است را برمی داریم و رنگ می کنیم اگر هیچ زیر مجموعه ای نسازد که سه عضو آن رنگ شده در غیر این صورت آن را رنگ نمی کنیم و به سراغ عدد بعد ی می رویم و با استفاده از این نکته که مجموع درجات برابر 3n است و این که اگر عددی رنگ نشده به معنای آن است که حداقل یک زیر مجموعه 3 عضوی تکمیل شده که 2 عضو قبلی آن را رنگ کردیم و همچنین اینکه در هر مرحله میانکین درجات اعدادی که بررسی کردیم کوچکتر یا مساوی 3 است می توان نتیجه گرفت که حکم درست است

8)
الف ) باید تمام حالات ممکن برای قرار گیری دایره های a و bو c وd را در نظر بگیرید با این کار حکم ثابت می شود
ب)به استقرا ثابت می کنیم که حکم ثابت است برای پایه استقرا که واضح است حال فرض کنید برای n درست است می خواهیم برای n+1 ثابت کنیم فردی را در نظر بگیرید که با بیشترین تعدا افراد آشناست آن فرد را از گروه حذف می کنیم بنا بر فرض استقرا برای بقیه افراد می توان این دایره ها را رسم کردحال فردی را که حذف کردیم وارد این جمع کرده و تمام کسانی که این فرد با آنها دوست است را وارد دایره این فرد می کنیم توجه کنید که در این کار تمام دایره هایی را که یکی از این افراد در آنهاست و تمام دایره هایی که درون دایره تمام این افراد است را با آنها وا رد دایره فرد ی میکنیم که حذف کردیم اگر کسی باشد که با این فرد دوست نیست ولی با یکی از دوستان این فرد دوست است و وارد دایره این نفر شده آنگاه بنا بر قسمت الف چون می دانیم یک راس وجود دارد که با یکی از دوستان فردی که حذف کردیم دوست است اما با آن دوست نیست می توان نتیجه گرفت که همان فردی که با فردی که حذف کردیم دوست است و با کسی دیگری هم دوست است تعداد دوستانش از راسی که حذف کردیم بیشتر بوده پس به تناقض می رسیم و حکم درست است .
البته اینها در واقع قسمتی از راه حل اصلی است و بقیه راه حل با همت خود خاننده به راحتی کامل می شود امسال سطح سوالات از پارسال سخت تر بود و کف هم احتمالا تا 100 برسه امید وارم همه خوب داده باشین لطفا اگر ایرادی در این جواب ها هست یا جایی جوب زده شده حتما بگید ممنون میشم لطفا هر کسی هم میاد بگه خودش و مدرسش چیکار کردن تا دوستان دیگر تغریبا از کف قطعی مطلع شوند امید وارم همه این امتحانو خوب داده باشین و قبول بشین البته بنا بر اصل لانه کبوتری این دعا رو تنها برای تعداد خاصی باید بکنم در پایان هم به قول آریو دی ... و به قول دوستان مینی المپیاد یا حق