مجموعه ها

[n_maths]

زیر مجموعه هایی K عضوی از مجموعه X هستند.ثابت کنید هر عضو X را میتوان با دو رنگ آبی و قرمز طوری رنگ کرد که حد اکثر

تا از A[SUB]i [/SUB]ها تکرنگ باشند.(زیر مجموعه ای از X مانند A را تکرنگ مینامیم،هرگاه همه ی اعضای A همرنگ باشند)
سوالیست بسیار ساده،ولی خب،من راه حلشو متوجه نمیشم...):65:

 

[n_maths]

پاسخ : مجموعه ها

این سوال 28.4.2 صفحه ی 43 کتاب زرد دکتر علیپور بوده

 

[Aref]

پاسخ : مجموعه ها

زیر مجموعه هایی K عضوی از مجموعه X هستند.ثابت کنید هر عضو X را میتوان با دو رنگ آبی و قرمز طوری رنگ کرد که حد اکثر

تا از A[SUB]i [/SUB]ها تکرنگ باشند.(زیر مجموعه ای از X مانند A را تکرنگ مینامیم،هرگاه همه ی اعضای A همرنگ باشند)
سوالیست بسیار ساده،ولی خب،من راه حلشو متوجه نمیشم...):65:

تو این سوال یه مقدار برخورد احتمالی به آدم کمک می کنه. ببینین اگه هر عضو X رو رندوم رنگ کنیم، و متغیر تصادفی مون رو تعداد [A[i های تکرنگ بگیریم، اونوقت امید ریاضی متغیر تصادفی ما میشه

پس یه رنگ آمیزی خوب وجود داره.
حالا که شهود احتمالاتی رو گرفتید اثبات ترکیبیاتی:
همه ی حالت های رنگ آمیزی اعضای X را در نظر بگیرید. فرض کنید

رنگ آمیزی مختلف برای اعضای X داشته باشیم.

را به ترتیب تعداد زیرمجموعه های تکرنگ از

در رنگ آمیزی های یکم، دوم، ... و

ام می گیریم.
ما می خواهیم ثابت کنیم یکی از

ها حداکثر

است.
ادعا می کنیم

و حکم ثابت می شود.
حالا برای این، کافیه ثابت کنیم توی

رنگ آمیزی ها

تکرنگه.
برای این اول اعضای

رو رنگ می کنیم، که چون همشون باید همرنگ باشند دو انتخاب داریم.برای بقیه ی اعضا هم طبق اصل ضرب باید

انتخاب می داشته ایم.
پس مساله حل شد.