سوالی از بوسنی و هرزگوین 2008 (ترکیبیات)

[Goharshady]

8 دانش آموز در یک آزمون چندگزینه ای 8 سوالی شرکت کردند. می دانیم که هر سوال حداقل توسط 5 دانش آموز حل شده است. ثابت کنید 2 دانش آموز وجود دارند که هر سوال حداقل توسط یکی از آنها حل شده است.

 

[navidjalalmanesh]

به راحتی اثبات می شه که دانش آموزی وجود داره که بیشتر یا مساوی 5 مسئله حل کرده است , به این دلیل که هر مسئله توسط حداقل 5 نفر حل شده پس در مجموع حداقل 40 حل داریم . حال اگر کسی بیشتر یا مساوی 5 مسئله حل نکرده باشه آنگاه تعداد حل ها کمتر یا مساوی 8 * 4 = 32 می شه که تناقضه .

فرض کنید دقیقا 5 مسئله حل کرده باشد :

بدون لطمه خوردن به کلیت می توان فرض کرد مسئله های 1 و 2 و 3 توسط او حل نشده باشد . در این صورت مسئله 1 و 2 و 3 , 15 بار حل شده اند (حداقل) اما 7 نفر داریم پس طبق اصل لانه کبوتری یک نفر وجود دارد که هر سه مسئله را حل کرده باشد که این دو نفر زوج مطلوب مسئله هستند .

حالت هایی که آن دانش آموز دقیقا 6 و 7 و 8 مسئله حل کرده باشد نیز به طریق مشابه اثبات می شود .

 

[Goharshady]

بله!
به همین سادگی
من واقعا نمی دونم چه جوری با چنین سوالاتی تیم انتخاب می کنن!!