- ارسال ها
- 2,239
- لایک ها
- 166
- امتیاز
- 0
منبع: 500 مسئله ی ریاضی پیکارجو
سوال پیکارجوی ترکیبیات (شماره ی 2)
- شروع کننده موضوع Goharshady
- تاریخ شروع
- برچسپ ها ترکیبیات ریاضی سوال
منبع: 500 مسئله ی ریاضی پیکارجو
- ارسال ها
- 114
- لایک ها
- 3
- امتیاز
- 0
هر زیر مجموعه از قول ها و مکمل اون زیر مجموعه رو تو یه دسته در نظر میگیریم. تعداد دسته ها 2^n-1 میشه. از هر دسته حداکثر یه عضو میتونیم انتخاب کنیم چون در غیر این صورت دو کاندیدا پیدا میشن که هیچ قول مشترکی ندارن و با فرض در تناقضه. پس تعداد کاندیدا ها حداکثر 2^n-1 میشه.
مثال برای 2^n-1 هم اینطوری میزنیم که یه قول رو تو مجموعه همه کاندیداها در نظر میگیریم (مثلا قول 1 ) و هر زیرمجموعه از بقیه قول ها رو به یه کاندیدا نسبت میدیم.
اینطوری همه کاندیدا ها قول 1 رو تو مجموعشون دارن و تعداد کاندیداها هم دقیقا 2^n-1 میشه.
2^n-1 = دو به توان (n-1)
مثال برای 2^n-1 هم اینطوری میزنیم که یه قول رو تو مجموعه همه کاندیداها در نظر میگیریم (مثلا قول 1 ) و هر زیرمجموعه از بقیه قول ها رو به یه کاندیدا نسبت میدیم.
اینطوری همه کاندیدا ها قول 1 رو تو مجموعشون دارن و تعداد کاندیداها هم دقیقا 2^n-1 میشه.
2^n-1 = دو به توان (n-1)