سوال اول --> لانه ی کبوتری :
الف ) طبق اصل لانه ی کبوتری حداقل n قطاع به رنگ x داریم ... در این جا 3 حالت داریم ...
حالت 1: (x=نارنجی) ... همه قطاع ها را نارنجی می کنیم ...
حالت 2: (x=زرد) ... همه قطاع ها را بنفش می کنیم ...
حالت 3: (x=بنفش) ... همه قطاع ها را زرد می کنیم ...
در هر 3 حالت قطعه هایی که ببعی رنگ زده و به رنگ x هستند تشکیل قطاع نارنجی می دهند ...
(و تعدادشان بیشتر مساوی n می باشد)
ب ) در مرحله اول ببعی طوری 3n قطاع را رنگ می کند که از هر رنگ n تا موجود باشد ...
در مرحله 2 گاوی آرایش رنگی خود را رائه می دهد ... (A تا نارنجی , B تا بنفش , C تا زرد)
حال می خواهیم ثابت کنیم که در 3n حالتی که ببعی با چرخش به آن ها می رسد ...
حالتی وجود دارد که حداکثر n قطاع نارنجی ایجاد شود ...
اثبات : تعداد قطاع های نارنجی ایجاد شده را در 3n حالت موجود می شماریم ...
هر قطاع دایره اول, یک بار بر روی همه ی قطاع های دایره دوم قرار می گیرد (در مجموع 3n چرخش) ...
هر قطاع ی نارنجی در دایره اول با A قطاع از دایره دوم تشکیل قطاع نارنجی می دهد (A*n تا) ...
هر قطاع ی بنفش در دایره اول با C قطاع از دایره دوم تشکیل قطاع نارنجی می دهد (C*n تا) ...
هر قطاع ی زرد در دایره اول با B قطاع از دایره دوم تشکیل قطاع نارنجی می دهد (B*n تا) ...
در مجموع --> (n * (A+B+C قطاع نارنجی ایجاد می شود ... و تعداد حالات برابر 3n است ...
در نتیجه طبق اصل لانه ی کبوتری حالتی وجود دارد که در آن کمتر مساوی n قطاع نارنجی ایجاد می شود.
سوال دو --> اثبات مستقیم :
الف) مهره ها رو به n دسته ی 3 تایی تقسیم می کنیم ... (از 1 تا n)
گراف زیبا رو به این نحو میسازیم که به جای هر مهره یک راس قرار میدیم ...
حالا اگه 2 تا مهره رو با هم مقایسه کنیم بینشون یال می کشیم و جواب رو, رو یال می نویسیم ...
(بله یا خیر)
لم خشگل : بین هر 3 راس یا همه ی یال ها بله است یه 2 تا از آن ها خیر هستند ...
اثبات : یا همه راس ها 1 گرمی هستند (که هر سه یال بله می شوند) ... یا 1 نیم گرمی داریم ...
(2 یال متصل به نیم گرمی خیر هستند)
یا 2 نیم گرمی داریم (تنها یال بین 2 نیم گرمی بله می شود)
حالا میایم تو هر دسته 2 تا یال از بین 3 یال موجود رو می کشیم (مقایسه می کنیم) ...
اولین دسته ای رو که یک یال خیر توش بود رو در نظر می گیریم ... حالا 3 حالت ممکنه پیش بیاد ...
حالت 1: اولین یال خیر تو دسته ی 1 باشه ...
چون n>2 پس 3 مقایسه ی دیگر داریم ... طبق لم خشگل هر 3 یال دسته 1 رو می دونیم ...
اونی رو که 2 تا خیر بهش وصل هستش (راس Gh) رو در نظر می گیریم و با 3 تا راس دیگه (خارج از دسته 1) مقایسه می کنیم ...
اگر Gh نیم گرمی باشد حداقل 2 تا از یال های جدید خیر هستند ...
اگر Gh یک گرمی باشد هر 3 یال بله هستند (طبق لم خشگل 2 راس دیگه ی دسته 1 نیم گرمی هستند)
حالت 2: اولین یال خیر تو دسته ی i باشد ... (n > i > 1)
چون تو دسته های قبل با اطمینان می توان گفت همه راس ها 1 گرمی هستند پس راسی رو که 2 تا خیر داره رو با قبلی ها مقایسه می کنیم و به ماهیت هر 3 عضو دسته ی i پی می بریم ... (طبق لم خشگل)
حالت 3: تا دسته ی n_ام همه یال ها بله باشد ...
یه یال تو دسته ی n_ام می کشیم اگه بله بود هر 2 نیم گرمی هستند ...
اگر خیر بود راس دیگر در دسته n_ام حتما نیم گرمی است (طبق لم خشگل).
ب ) برهان خلف ... گراف گفته شده در بخش الف را می سازیم ...
(برای راه حلی با کمتر از 2n-1 حرکت (طبق برهان خلف))
لم گوگول مگولی:
ثابت می کنیم در گراف مزبور نمی توان 4 راس درجه 1 داشته باشیم که به هم وصل باشند ...
(به یکی میگیم گوگول به اون یکی مگول)
اثبات : هر 2 تایی رو که پرسید طوری مقدار دهی می کنیم که جواب بله باشه ...
اما در پایان 2 حالت واسه گوگول , مگول داریم که درنتیجه نمی تونیم مهره های نیم گرمی رو پیدا کنیم ...
(حالت 1: هر 2 راس گوگول نیم گرمی باشند حالت 2: هر دو راس مگول نیم گرمی باشند)
حال می خواهیم ثابت کنیم اگر گرافی داشته باشیم (با 3n راس) که A , B را نداشته باشد ...
حداقل 2n-1 یال دارد ...
به هر مولفه ی همبند یک عدد قشنگ نسبت می دهیم --> (تعداد راس تقسیم بر تعداد یال) ...
اگر بخواهیم تعداد یال ها کمینه شود باید عدد قشنگ مولفه ها بیشینه باشد ...
در مولفه ها دور نداریم زیرا می توان با حذف یک یال در دور عدد قشنگ مولفه را افزایش داد ...
پس هر مولفه یک درخت است (دور ندارد ... همبند هم هست) ...
عدد قشنگ مربوط به یک درخت k راسی برابر --> k تقسیم بر k-1 است ...
(به صورت آشکارا هر چه K افزایش یابد عدد قشنگ درخت مزبور کم تر می شود)
طبق لم گوگول مگولی از درخت 2 راسی یه دونه بشتر نداریم ...
پس طبق گفته های بالا باید بقیه گراف را به درخت های 3 راسی افراز کنیم ...
که در نتیجه تعداد یال های لازم برابر 2n-1 می شود ...
نکته :
تعداد راس های درجه 0 بیشتر از 2 نیست ...
(ممکن است 2 تا نیم گرمی بین این 3 راس باشند و ما قادر به تشخیص آن ها نیستیم)
اگه 2 تا راس درجه 0 داشته باشیم پس حتما یه درخت بزرگتر مساوی 4 راسی نیز داریم ....
که تعداد یال ها را حداقل یک واحد زیاد می کند ... که در کل تعداد یال ها بزرگتر مساوی 2n-1 می شود.
سوال سه --> اکسترمال :
الف ) یک گراف کامل n راسی را در نظر می گیریم ... سپس یال بین A , B را پاک می کنیم ...
برای رسیدن از A به B باید از یکی از راس های دیگر نیز بگزریم (آن راس را X بنامید) ...
زیرا به طور مستقیم بین A , B یالی وجود ندارد ...
درجه A + درجه B + درجه X برابر است با 3n-5 ... پس حداقل به این مقدار نیازمندیم ...
ب ) کوتاه ترین مسیر یالی بین 2 راس A , B را در نظر می گیریم ... (تعداد راس های کوتاه ترین مسیر = x)
ادعا میکنیم هزینه ی این مسیر کوچکتر مساوی 3n-5 است ...
نکته : هیچ دو راس غیر متوالی از کوتاه ترین مسیر به هم وصل نیستند ...
زیرا با پیمودن یال مذکور طول مسیر کاهش میابد ...
لم آبیکه : هر راس خارج از کوتاه ترین مسیر حداکثر به 3 عضو از اعضای مسیر متصل است ...
اثبات : برهان خلف ... راسی وجود دارد که حداقل به 4 عضو مسیر متصل است ... (این راس را Gh بنامید)
به ترتیب حضور در مسیر آن ها را A , B , I , K می نامیم ... مسیر را این گونه تغییر می دهیم ...
A , Gh , K دو یال (A , Gh) (Gh , K) اضافه شده و 3 یال (A , B) (B , I) (I , K) حذف می شوند ...
در نتیجه طول مسیر کاهش میابد ... که این مخالف فرض است و در نتیجه تناقض ...
حال مجموع درجات مسیر را می شماریم ...
مجموع درجات راس های داخل مسیر با خودشان برابر 2-2x می باشد ...
تعداد راس های بیرون مسیر برابر n-x بوده و هرکدام حداکثر به 3 عضو از کوتاه ترین مسیر متصل اند ...
(طبق لم آبیکه)
درنتیجه : 3n-3x+2x-2 = 3n-x-2 ... برای x های بزرگتر از 2 که حکم مسئله برقرار است ...
برای x مساوی 2 نیز طبق بخش الف حکم برقرار است ...
سوال چهار بزودی
