دوازده جنگلی (ترکیبیات)

[Goharshady]

نفر در یک جنگل که هیچ ارتباطی با بیرون ندارد زندگی می کنند. برخی از آنها با هم دوست هستند. دوستی ها دوطرفه و دائمی است! هر نفر یک کلبه دارد و کلبه ی هر نفر قرمز یا آبی است. هر ماه از سال به یکی از این افراد تعلق دارد. در این ماه آن فرد به دیدار همه ی دوستانش می رود. در پایان ماه ، آن شخص رنگ خانه اش را عوض می کند اگروتنهااگر رنگ کلبه ی بیش از نیمی از دوستانش با او فرق کند. (توجه کنید که دوستی الزاما خاصیت تعدی ندارد) ثابت کنید بعد از تعداد متناهی ماه ،دیگر هیچ کس رنگ کلبه اش را عوض نمی کند.

 

[mahanmath]

Che jaleb !!

Tedade ravabete doosti bein do fard ba khane haye yekrang=X

dar har marhale adade X bishtar mishavad

va Max 2 az 12 ta rabete doosti darim pas pas az tedadi motanahi ....mmm

 

[30na]

گراف معادل مسئله رو میکشیم.
بین دوستا یال ها رو میکشیم و راسهارو به رنگ قرمز یا «آبی و یال های متناظر با رئوس همرنگ را سیاه و متناظر با رئوس ناهمرنگ را سفید میکنیم.در هر گام یال های سیاه رو به افزایشاند و از آنجا که تعداد یالها متناهی است زمانی میرسد که همه یال ها سیاهند!(ناوردایی)