اصل لانه كبوتري (2)

[rza]

6 نفر داريم. دوبه دو دوست يا دشمن اند ثابت كنيد در بين آنها 3 نفر هستند كه يا هر سه دوست اند يا هر سه دشمن اند.

 

[AidinT]

یک نفر رو در نظر می گیریم! این یه نفر با پنج نفر در ارتباطه! حالت بندی می کنیم:
1- شخص با 5 نفر دوست باشه:
اگه یکی از دوستاش با یه دوست دیگش دوست باشه مسأله حله و اگه هیچ کدوم از دوست هاش با هم دوست نباشن، 3 تا دوست این شخص هستن که با هم دشمنن!
2- شخص با 4 نفر دوست باشه:
به شکل مشابه بالا
3- شخص با 3 نفر دوست باشه:
باز هم به شکل مشابه
4 - شخص با 2 نفر دوست باشه:
از اینجا به بعد جای دوست ها و دشمن ها عوض می شه. یعنی اینجا ما سه تا دشمن داریم(به جای سه تا دوست) و مشابه حالت های قبل می تونیم واسشون استدلال کنیم، تنها فرقش اینه که جای دوست و دشمن عوض می شه
و الی آخر...

 

[mahdisaj]

از قضیه ی اعداد رمزی هم میشه استفاده کرد :

6 نفر را در نظر می گیریم ثابت می کنیم که از این 6 نفر حد اقل 3 نفر هستند که یا دوستند یا دشمن .

طبق قضیه اعداد رمزی اگر

نقطه داشته باشیم و این نقاط را به هم وصل کنیم و این خطوط را با n رنگ ، رنگ کنیم حتما یک مثلث با اضلاع هم رنگ وجود دارد . که e همان عدد نپر است.
حال به حل مسیله بر می گردیم : اگر هر فرد را یک نقطه در نظر بگیریم و رابطه ی دوستی را رنگ سبز و دشمنی را با رنگ قرمز آنگاه طبق قضیه فوق یک مثلث با اضلاع همرنگ وجود دارد پس در این جمع 6 نفره یک جمع 3 نفره وجود دارد که یا هر سه دوست و یا هر سه دشمن اند .

در ضمن ببخشید که من ریاضیم و تو این جا اومدم

 

[AidinT]

چه فرقی می کنه؟؟؟

من تو زیست و شیمی هم پست می ذارم!

 

[rza]

من قضيه مطرح شده از سمت آقاي mahdisaj بلد نبودم ولي ياد گرفتم ولي راه حل كه مد نظر من بود همين بود با اثبات قضيه .ولي جواب آقاي AidinT درست بود.

 

[Goharshady]

من فکر نمی کنم فرق زیادی بین قسمت ترکیبیات ریاضی و آنالیز ترکیبی کامپیوتر وجود داشته باشه.