سوالات ترکیبیات (اصل لانه کبوتری)

[rezoos]

1.مسئله ی تفنن: شطرنج بازی 11 هفته فرصت دارد که خود را برای شرکت در مسابقه ای آماده کند. برای این منظور تصمیم میگیرد که هر روز حداقل 1 دست بازی کند ولی برای اینکه خسته نشود در هیچ هفته ای بیش از 12 دست بازی نمی کند. ثابت کنید چند روز متوالی وجود دارد که شطرنج باز طی آنها دقیقا 20 دست بازی کرده است. (منبع: کتاب ترکیبیات علیپور ، ص105-راه حل اولش رو فهمیدم. راه حل دومش رو لطفا توضیح بدین)

2.فرض کنید S زیر مجموعه ای 7 عضوی از مجموعه ی اعداد 1 تا 23 باشد. ثابت کنید دو زیر مجموعه ی نا تهی و مجزا از S مانند A و B وجود دارند که مجموع اعضای A با مجموع اعضای B برابر است.

3.ثابت کنید اگر در سوال قبل به جای چجموعه ی اعداد 1 تا 23 ، مجموعه ی اعداد 1 تا 25 را قرار دهیم باز هم حکم مساله درست است.
(سوال 2 و 3 ص 106 کتاب علیپور هست)

 

[Goharshady]

2.فرض کنید S زیر مجموعه ای 7 عضوی از مجموعه ی اعداد 1 تا 23 باشد. ثابت کنید دو زیر مجموعه ی نا تهی و مجزا از S مانند A و B وجود دارند که مجموع اعضای A با مجموع اعضای B برابر است.

3.ثابت کنید اگر در سوال قبل به جای چجموعه ی اعداد 1 تا 23 ، مجموعه ی اعداد 1 تا 25 را قرار دهیم باز هم حکم مساله درست است.
(سوال 2 و 3 ص 106 کتاب علیپور هست)

پاسخ 2:
هر زیرمجموعه ی 7 تایی از مجموعه ی اعداد 1 تا 23 دقیقا

زیرمجموعه ناتهی سره دارد. جمع اعضای هر یک از این زیرمجموعه ها کمتر از

است و این کمتر از تعداد زیرمجموعه ها. پس حتما دو زیرمجموعه با مجموع اعضای مساوی در بین زیرمجموعه های آن وجود دارد. اگر این دو زیرمجموعه جدا از هم نباشند ، کافی است اشتراک آنها را از هر دو کم کنیم.
پاسخ 3:
چون

و این هم کمتر از تعداد زیرمجموعه ها است ، همان حکم بالا برقرار است.

 

[Goharshady]

مسئله ی تفنن قبلا با عنوان لانه کبوتری (i) که i عددی طبیعی است و من نمی دانم چند است ، مطرح شده است.

 

[Goharshady]

با این حال اگر شما بخواهید ، توضیح خواهم داد.

 

[abdi]

مسئله ی تفنن قبلا با عنوان لانه کبوتری (i) که i عددی طبیعی است و من نمی دانم چند است ، مطرح شده است.

لانه كبوتر (1) بود: ftopict-2243.html

 

[rezoos]

سوال 1 رو تو اون لانه کبوتر 1 با یه روشی حل کردین که من بلدم

! اون روش اول برای حل مساله هست. روش دیگه اینه که اعداد مجموعه ی

را طوری دسته بندی کنیم که تفاضل دو عدد متعلق به یکی از دسته ها برابر 20 شود. سپس از اصل لانه کبوتری نتیجه میگیریم که حداقل دو تا از Si ها متعلق به یک دسته هستند.(اینو تو کتاب علیپور نوشته ص105)من اینو میخواستم بفهمم که چطور با این راه حل ، حل میشه! خوبه که آدم واسه یه سوال چند تا راه حل بلد باشه

!

 

[Goharshady]

شما که اینو کامل نوشته اید
پس ما باید چی رو توضیح بدیم؟

 

[rezoos]

مثلا بگین چطور دسته بندی میکنین؟

 

[rezoos]

 

[rezoos]

 

[soroush419]

پاسخ : سوالات ترکیبیات (اصل لانه کبوتری)

سلام من یک سوال دارم !
درون یک اتاق به مساحت ۴ متر مربع ۷ فرش با مساحت ۱ متر مربع و با اشکال دلخواه پهن کرده ایم . نشان دهد ۲ فرش وجود دارد که اشتراک ان ها کمتر از ۱/۷ متر مربع هست ؟

 

[soroush419]

پاسخ : سوالات ترکیبیات (اصل لانه کبوتری)

یه سوال دیه هم دارم :
دو دایره یکی شامل ان نقطه و دیگری شامل تعدادی کمان هست که مجموع ان ها کمتر از ۲پی/ان هست . تابت کنید می توان دو دایره را طوری روی هم طوری رویه هم قرار داد که هیچ نقطه ای روی کمان ها نباشد ؟

 

[goodarz]

پاسخ : سوالات ترکیبیات (اصل لانه کبوتری)

یه سوال دیه هم دارم :
دو دایره یکی شامل ان نقطه و دیگری شامل تعدادی کمان هست که مجموع ان ها کمتر از ۲پی/ان هست . تابت کنید می توان دو دایره را طوری روی هم طوری رویه هم قرار داد که هیچ نقطه ای روی کمان ها نباشد ؟

دوتا دایره رو روی هم بذارین و یکی رو روی اون یکی بچرخونین, یه نقطه بَده اگه روی یه کمان باشه.....هر نقطه حداکثر به اندازه کمتر از

کمان میتونه بد باشه, پس در کل جمع کمان هایی که یه نقطه میتونه بد باشه از

کمتره, پس حتما یه جا هست که هیچ نقطه ای روی هیچ کمانی قرار نگرفته....(شرمنده اگه بد توضیح دادم, بهتر از این نمیشد)

 

[hh1546]

پاسخ : Re: سوالات ترکیبیات (اصل لانه کبوتری)

پاسخ 2:
هر زیرمجموعه ی 7 تایی از مجموعه ی اعداد 1 تا 23 دقیقا

زیرمجموعه ناتهی سره دارد. جمع اعضای هر یک از این زیرمجموعه ها کمتر از

است و این کمتر از تعداد زیرمجموعه ها. پس حتما دو زیرمجموعه با مجموع اعضای مساوی در بین زیرمجموعه های آن وجود دارد. اگر این دو زیرمجموعه جدا از هم نباشند ، کافی است اشتراک آنها را از هر دو کم کنیم.
پاسخ 3:
چون

و این هم کمتر از تعداد زیرمجموعه ها است ، همان حکم بالا برقرار است.

من گفتم بهتره یکم درسای سوم دبستان رو هم مرور کنیم ! به خاطر همین یکم از ضرب و جمع ها رو تکرار کردم

البته نتیجه بدست آمده بسیار تعجب براگیز بود
در ضمن چیز عجیبی نیست از این جمع و ضرب ها باید زیاد تو ایران تمرین بشه (شاید کم کاری معلمای دبستان بوده) :کشف یک تناقض جدید در ریاضیات! - تیم المپیاد ریاضی ایران

 

[soroush419]

پاسخ : سوالات ترکیبیات (اصل لانه کبوتری)

یه صوال دیگه :
فرض کنید a1,s2,s3...,a50 زیر مجموعه از مجموعه متناهی ایکس باشند به طوری که هر کدام از ان ها شامل بیش از نصف اعضای ایکس باشند. ثابت کنید می توان زیر مجموعه ای حداکتر ۵ عضوی از ایکس پیدا می شه به طوری که با هر یک ار مجموعه های a1,s2,s3...,a50 حداقل ۱ عضو مشترک داشته باشد.

 

[goodarz]

پاسخ : سوالات ترکیبیات (اصل لانه کبوتری)

یه عضو هست که تو حداقل 26 تا اومده, اون 26 تارو بذارین کنار, یه عضو دیگه هست که تو حداقل 13 تا از 24 مجموعه باقیمونده اومده, اون 13 تارو بذارین کنار, یه عضو دیگه هست که تو حداقل 6 تا از 11 مجموعه باقیمونده اومده....

ضمنا, اون سواله نه صوال!!!!!

 

[ramram]

پاسخ : سوالات ترکیبیات (اصل لانه کبوتری)

سلام من یه عضو جدیدیم و یه سول دارم.
1-در بین اعداد 1 ا 95 ثابت کنید هر 20 عددی را که انتخاب کنیم تفاضل دو به دو هر یک،حداقل در سه عدد مشترک است.

امید وارم بتونید جوابشو بهم بدین.چون خیلی لازم دارم.

 

[math-sina]

پاسخ : سوالات ترکیبیات (اصل لانه کبوتری)

سلام من یه عضو جدیدیم و یه سول دارم.
1-در بین اعداد 1 ا 95 ثابت کنید هر 20 عددی را که انتخاب کنیم تفاضل دو به دو هر یک،حداقل در سه عدد مشترک است.

امید وارم بتونید جوابشو بهم بدین.چون خیلی لازم دارم.

در بین هر 20 عدد

تفاضل وجود داره که تفاضل ها بین اعداد 1 تا 94 هستند. پس طبق لانه عددی وجود داره که حداقل

بار تکرار شده.