لانه كبوتر (4)

abdi · 1389/1/1

فرض كنيد

$A_{1}, A_{2}, A_{3},..., A_{50}$

، 50 زيرمجموعه از مجموعه متناهي X باشند، به طوري كه هركدام از آنها شامل بيش از نصف اعضاي X باشد. ثابت كنيد مي‌توان زيرمجموعه‌اي حداكثر 5 عضوي از X پيدا كرد، بطوريكه با هريك از مجموعه‌هاي

$A_{1}, A_{2}, A_{3},..., A_{50}$

، دست كم يك عضو مشترك داشته باشد.

Goharshady · 1389/1/1

abdi گفت

در مجموع

$A_{i}$

ها حداقل

عضو دارند. پس عضوی وجود دارد که در حداقل

زیر مجموعه قرار دارد.این عضو را در مجموعه ی

عضوی مورد نظر وارد می کنیم. بدیهی است که بیش ترین تعداد عضو لازم برای برقراری شرط مسئله زمانی است که این عضو در بیش از

تا از

$A_{i}$

ها وجود نداشته باشد ، بنابراین در بدترین حالت (در مرحله دوم هرگز از این عبارت استفاده نکنید!!)

زیر مجموعه شامل این عضو هستند. همه ی آنها را کنار می گذاریم. حال سایر

$A_{i}$

ها در مجموع

عضو دارند. پس عضوی در

مجموعه (غیر از 25 تای اول است)است. با ادامه ی این روند اعضایی را می یابیم که در

مجموعه ی مجزا از

$A_{i}$

ها وجود دارند، پس 5 عضو یافتیم که در

تا از

$A_{i}$

ها هستند.
اما حالا باید اثبات کنیم که این بدترین حالت است (این عبارت را هرگز هرگز هرگز به کار نبرید!!)
فرض کنیم عضو اول (که فرض کردیم در

زیر مجموعه است) در بیش از

زیر مجموعه باشد. مثلا در

زیرمجموعه، در این صورت

زیرمجموعه را کنار می گذاریم ، در حالی که از تعداد مجموعه های عضو بعدی حداکثر

کم می شود ، که به صورت بدیهی باعث می شود با همان

عضو اول تعداد بیشتری از

$A_{i}$

ها را پوشش دهیم پس وضعیت بهتر شده است. (از این عبارت هم هرگز استفاده نکنید!)
ببخشید که بد و طولانی نوشتم و از عبارات ممنوعه! استفاده کردم. (به جای این عبارات باید تعبیر ریاضی آنها را بیاورید ، مثلا به جای بدترین حالت بگویید حالتی که در آن بیشترین تعداد عضو برای پوشش یک مجموعه لازم است.) ضمنا ایکس دوم به ایکس منهای یک دوم و ... تبدیل می شود که بهتر (!) است.
راستی باید می گفتید تعداد اعضای X بیشتر از 5 است و من فرض کردم تعداد اعضای X برابر x باشد.
باز هم ببخشید که طولانی نوشتم

لانه كبوتر (4)

abdi

New Member

Goharshady

New Member