پاسخ : مسائلی از گراف
دو)2n نفر ادم قرمز و 2nنفر ادم آبی و2n نفر ادم نارنجی داریماینارو دور یه دایره می نشونیم
هرکی که دو تا همسایه اش همرنگ بودن بقیه رو مهمون نمی کنه
حداکثر چن نفر می تونن بقیه رو مهمون نکنن؟
---- دو نوشته به هم متصل شده است ----
سه) ان نفر داریم. هر 4 تاشون که بگیریم سه تاشون هست که یا باهم دوستن یا دشمن
ثابت کنین میشه اینا رو دو دسته کرد که تو یه دسته همه باهم رفیق باشن و توی یه دسته همه با هم دشمن
چهار) یه گراف داریم که همه راساش سفیده تو هر مرحله میتونیم یه راسو انتخاب کنیم و رنگ اون راس و همه ی همسایه هاشو عوض کنیم
یعنی از سیاه به سفید یا از سفید به سیاه
خب آیا میشه همیشه گراف رو کاملا سیاه کنیم؟
---- دو نوشته به هم متصل شده است ----
پنج)
یه جدول n*k داریم . توی هر خونه یه عدد از یک تا ان نوشته شده و توی هیچ سطر و ستونی عدد تکراری وجود نداره
ثابت کنین میشه تعدادی ستون به سمت راست جدول اضافه کرد که جدول n*n بشه و بازم تو هیچ سطرو ستونیش عدد تکراری نداشته باشه؟
شش)
ان نفرادم داریم . که هر سه نفر شونو در نظر بگیریم دو تاییشون هستن که باهم دشمن باشن
هرجور اینا تو دو تا اتوبوس بشینن ، دو نفری وجود داره که باهم دوست باشن و توی یه اتوبوس باشن
ثابت کنین کسی هست که تعداد دوستاش حداکثر 2n/5 ـه؟
