آزمون پنجم شاززز

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

سوال دوم‌:
یک گراف شونزده راسی بسازید. اگه آقای آ‌ آقای ب رو نگاه میکرد از آ‌ به ب یک یال بذارین. حالا درجه ورودی و خروجی هر کس تو این گراف ۷ ه (چرا؟). حالا یازده نفر رو در نظر بگیرید یکی از این یازده نفر هست که به هر ده نفر دیگه یال داره (ورودی یا خروجی). حالا اون ده نفر یک دور دارن . با استفاده از این دور و این که اون یک نفر که کنار گذاشتین به همه یال داره ثابت کنید دور به اندازه یازده هم داریم.
سوال سوم:
این سوال که سوال خیلی خیلی سختی بود ما پیشنهاد نمیکنیم که راه حلشو بخونید. ولی راه حلشو کامل میگیم.
اول این سوال رو برای ده ربات حل میکنیم. بعد از راه حل این برای ۳ کمک میگیریم. (اگه میخواین بیشتر رو این سوال فکر کنید دیگه ازینجاش نخونین)
از استقرا قوی استفاده میکنیم. حکم استقرا میگه اگر ما log n مامور داشته باشیم میتونیم درخت رو بگردیم.
همون طور که میدونید فرض استقرا همون حکمشه برای حالت های کوچیکتر پس ما لازم نیست فرض استقرا رو بنویسیم :)
حال هر ده مامور در یک راس جمع میشوند(اسم این راس را مقر میگذاریم). اگر این راس را از گراف حذف کنیم‌ ، تعدادی درخت به وجود می‌آید که از این تعداد حد اکثر یکی از آن ها تعداد راس هایش بیش از نصف است. طبق فرض استقرا باقی درخت ها با ۹ مامور گشته میشوند. پس ما باقی درخت ها را با ۹ مامور میگردیم. یک مامور هم در مقر نگهبانی میدهد که سوسک از درختی به درخت دیگری نرود. حال اگر ۹ مامور سوسک را پیدا نکنند به مقر برمیگردند. و قسمت بعدی کار آغاز میشود (گشتن در درختی که بیش از نصف راس ها را دارد). هر ده مامور روی یالی که به این درخت میرود حرکت میکنند و داخل راسی جدید میشوند. این راس را مقر جدید میگذارند و یکی در این راس نگهبانی میدهد. قطعن سوسک به بخش هایی از گراف که قبلن گشته شده نمیره.
پس میتونیم فرض کنیم اون درختا وجود ندارن و داریم تو یه درخت کوچیککتر با ده مامور میگردیم. دوباره همین کارو با راس مقر میکنیم تا کل درخت گشته بشه. :)
خب اگه این قسمت رو نفهمیدین از این جا به بعد رو هم نمیفهمین :) پس سعی کنین این قسمت رو بفهمین
اگر توجه کنین مقر های ما تشکیل یک مسیر رو میدن توی درخت که اگه ما اون مسیر رو حذف کنیم تمام درخت های باقی مونده کمتر از نصف تعداد راس های ما رو دارن.
حالا ما اگه بتونیم مسیری پیدا کنیم که با حذف کردنش تمام درخت های باقی مونده کمتر از ۱/۳ راس ها رو داشته باشن. میتونیم این کارو با ۶ رباتم بکنیم.
(یه مامور میذاریم میشه ۳۳۳ راسی. باز تو مقر جدید یه مامور میذاریم نگهبانی بده چند تا ۱۱۱ راسی میمونه. یا مامور جدید میذاریم چند تا ۳۶ راسی میمونه. یکی دیگه میذاریم چند تا ۱۱ راسی میمونه. یکی دیگه بذاریم چند تا سه راسی میمونه. که درخت سه راسی یک مسیره با یک مامورم میشه گشتش)
حالا میخوایم ثابت کنیم چنین مسیری وجود داره. دوباره استقرا میزنیم. اولین نکته اینه که راس درجه ۲ اگه وجود داشته باشه میتونیم حذفش کنیم و به جاش دو تا همسایه شو به هم وصل کنیم و استقرا بزنیم. پس راس درجه دو نداریم.
 اگه راسی وجود نداشته باشه که با حذفش بیشتر از یک درخت با کمتر از یک سوم راس ها به وجود بیاد مانند مثله قبل عمل میکنیم. یعنی ۶ نفر رو میذاریم تو یک راس دلخواه. سپس با ۵ نفر درخت هایی که کمتر از یک سوم دارن رو حل میکنیم بعد همگی میریم به درختی که بیشتر از یک سوم داره.
حالا اگه راسی وجود داشت که با حذفش دو تا درخت با بیش از یک سوم به وجود میومد (قطعن سه تا به وجود نمیاد :) ). خب فقط این راس و دو درختی که بیش از یک سوم راس دارد در نظر میگیریم و باقی درخت ها را حذف میکنیم (حد اقل یک درخت حذف میشه چون درجه همه راسا بیشتر از دو بود). حالا طبق فرض استقرا تو این درخت کوچکتر مسیری وجود داره که با حذفش همه درختای باقی مونده کمتر از یک سوم راس هارو دارن. همین مسیر تو گراف اصلی هم این خاصیت رو داره :)