یک سوال خوب و خوش فکر ترکیبیاتی...
- ارسال ها
- 337
- لایک ها
- 82
- امتیاز
- 0
پاسخ : یک سوال خوب و خوش فکر ترکیبیاتی...
ببین اگه میخوای اثبات کنی دیگه از این کمتر نمیشه بگو که اگه مثلا n تا زبون داشته باشیم در اون صورت ترکیب n/2 از n میشه چون این بزرگترین تعداد میشه دیگه قبوله (تو ترکیب m از n بیشترین مقدار n/2 ) از طرفی اگه یه مقداری بیشتر از n/2 یا کمتر از n/2 بشه ما میتونیم تناظرش بدیم به یه مقدار تو دوتا نیمه ی اول یا دوم n/2 خب خودشم که گفته باید حتما هر دو فردی که بگیریم یه زبون متفاوت بلد باشن که اون یکی بلد نباشه واضحه که نمیتونیم همه ی زیر مجموعه ها رو بگیریم دیگه چون که تناقض میشه پس باید یه تعدادی رو بگیریم که بیشترین مقدار با کمترین تعداد زبون بده خب که اونم n/2 از n یه خورده بد میشه توضیحش داد اما خب راه حل قشنگ تر استقرا هست که هم راحت تره هم میتونی مینیمم بودن راحت تر از روش بگی
ببین اگه میخوای اثبات کنی دیگه از این کمتر نمیشه بگو که اگه مثلا n تا زبون داشته باشیم در اون صورت ترکیب n/2 از n میشه چون این بزرگترین تعداد میشه دیگه قبوله (تو ترکیب m از n بیشترین مقدار n/2 ) از طرفی اگه یه مقداری بیشتر از n/2 یا کمتر از n/2 بشه ما میتونیم تناظرش بدیم به یه مقدار تو دوتا نیمه ی اول یا دوم n/2 خب خودشم که گفته باید حتما هر دو فردی که بگیریم یه زبون متفاوت بلد باشن که اون یکی بلد نباشه واضحه که نمیتونیم همه ی زیر مجموعه ها رو بگیریم دیگه چون که تناقض میشه پس باید یه تعدادی رو بگیریم که بیشترین مقدار با کمترین تعداد زبون بده خب که اونم n/2 از n یه خورده بد میشه توضیحش داد اما خب راه حل قشنگ تر استقرا هست که هم راحت تره هم میتونی مینیمم بودن راحت تر از روش بگی