آمار پرسش:
- پرسیده شده: 2019-08-18 03:32:00 -0500
- مشاهده شده: 255 بار
- بروز شده: 2019-08-26 10:11:06 -0500
پرسش‌های مشابه:
تعداد جواب های معادله ${1\over x}+{1\over y}={1\over n}$ در دستگاه اعداد صحیح
n نفر با کلاه های قرمز و آبی و حدس زدن بیشترین تعداد درست
سوال 3 روز اول مرحله دوم چهارمین المپیاد کامپیوتر ایران
برابر بودن یا نبودن تعداد اعداد زوج و فرد
یافتن تعداد مستطیل های یک شبکه نقطه ای
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
فرض کنید S اجتماع تعدادی مجموعه های متناهی و k عددی ثابت باشد...
فرض کنید S اجتماع مجموعه های متناهی $A1,..An $ و k عددی ثابت باشد که $ 1<=k و k<=n $
و اجتماع هر k تا از $Ai$ ها برابر S باشدولی اجتماع هیچ k-1 تا از $Ai$ ها برابر S نباشد
ثابت کنید تعداد اعضای S بزرگتر مساوی از $ {n \choose k-1} $ هست
1 پاسخ
خب برای راحتی کار صرفا یه تابع تعریف میکنیم که ورودی هاش زیرمجموعه های k-1 عضوی از مجموعه {A1 ,A2......An} و خروجیش از زیرمجموعه های مجموعه اعضای S عه. تابع ما به این صورت عمل میکنه که هر زیرمجموعه k-1 عضوی که بهش بدین اون اعضایی از S رو بهمون میده که در اجتماع این k-1 تا Ai نیستن.
با توجه به فرض مشخصه زیرمجموعه خروجی همیشه عضو داره و تهی نیست. با توجه به فرض معلومه که هیچ عضوی از S دو بار در زیرمجموعه های خروجی نمیاد( چون اگه میومد K تا پیدا میشدن که شامل این عضو نیستن و این وجود این K تا خلاف فرضه.)
خب با توجه به نتیجه های بالا به هر ورودی ما ( که تعدادشون به اندازه انتخاب k-1 از n عه ) حداقل یه عضو "متمایز" از S نسبت داده شده پس با شمردن تعداد اعضای ورودی هامون ما داریم تعداد اعضای یه زیرمجموعه از اعضای S رو میشمریم که تعدادش کمتر مساوی تعداد کل اعضای S عه به وضوح. پس حکم نتیجه میشه.
