[mir@]

نوشته شده توسط mofidy1

با سلام

مجموعه ی دلخواه 10 عضوی از اعداد طبیعی کوچکتر از 100 را در نظر بگیرید. ثابت کنید که می توان دو زیر مجموعه ی ناتهی مجزا ( یعنی با اشتراک تهی) از این مجموعه چنان یافت که مجموع اعضای یکی با مجموع اعضای دیگری برابر باشد.

موفق باشید.

ارسال متن: شنبه 22 اردیبهشت 1386

درود

فرض کنیم S یک زیرمجموعه 10 عضوی دلخواه از اعداد طبیعی کوچک تر از 100 باشد.

در بدترین حالت، فرض کنیم S به صورت زیر باشد:

S={90,91,92,93,94,95,96,97,98,99}i

مجموع اعداد بالا مساوی است با 945.

اما تمام زیر مجموعه های S برابر است با 1024=10^2 که اگر زیرمجموعه تهی را حذف کنیم، 1023 زیر مجموعه از S خواهیم داشت.

از آنجا که مجموع اعضاء تمام زیرمجموعه های قابل تصور از S یک عدد صحیح مثبت و کوچکتر از یا مساوی با 945 است و 945<1023، لذا طبق اصل «لانه کبوتری» حتماً دو زیر مجموعه یافت می شود که مجموع اعضایشان با هم برابر است. ▲

پاسخ به شبهه مطرح شده توسط Iron:

در صورتی که دو زیر مجموعه اشتراک داشته باشند با هم، مشکل مهمی نیست. چرا که می توان اعضاء مشترک را از هر دو حذف کرد و اگر مجموع تا کنون مقدار M بود حالا برابر خواهد شد با M-m که m منظور مجموع اعضاء مشترک است.