چند تا سوال از اصل لانه کبوتری

[CHAPTER]

با سلام اگر امکان داره جواب این سوال ها رو می خواستم (اگر بر خلاف قوانین نیست )

1- 10 عدد طبیعی متمایز و کوچکتر از 107 مفروض هستند. با استفاده از اصل لانه کبوتری نشان دهید که دو زیر مجموعه مجزا و نا تهی از این دو عدد یافت میشود که مجموع آنها یکسان است.

2 - n+1 عدد از مجموعه { 1, 2, 3 , .... 2n}انتخاب شذه اند نشان دهید :
الف ) حداقل دو تا از اعداد انتخاب شده نسبت به هم اول هستند.
ب ) حداقل دو تا از اعداد انتخاب شده دارای مجموعی برابر 1+2n
2 به توان n منهای 1 هستند.

3- ثابت کنید هرگاه 101 عدد از مجموعه {3,2,1,...,200} = A انتخاب نماییم بین آنها دو عدد وجود دارد که یکی مقسوم علیه دیگری است.

4 - نشان دهید هر زیر مجموعه شش عضوی مجموعه {3,2,1,...,9} شامل دو عضو است که حاصل جمع آنها 10 است.
5 - فرض کنید m عددی فرد طبیعی باشد ثابت کنید یک عدد طبیعی مانند n وجود دارد که m عدد 1- 2n را عاد می کند.

6- نشان دهید هرگاه 14 عدد از مجموعه {3,2,1,...,25} انتخاب نماییم دو عدد در این انتخاب وجود دارند که حاصل جمع آنها 26 است.

7- چند بار تاسی را پرتاب کنیم به طوری که : حداقل n بار نتیجه یکسان به دست آید.

8- در یک مسابقه دوره ای که هر دو بازیکن دقیقا 1 بار با هم مسابقه می دهند فرض کنید هر بازیکن حداقل یک بار برنده شود. نشان دهید حداقل 2 بازیکن وجود دارند که تعداد برد های آنها یکسان است.

[saber57]

با سلام اگر امکان داره جواب این سوال ها رو می خواستم (اگر بر خلاف قوانین نیست )


2 - n+1 عدد از مجموعه { 1, 2, 3 , .... 2n}انتخاب شذه اند نشان دهید :
الف ) حداقل دو تا از اعداد انتخاب شده نسبت به هم اول هستند.
ب ) حداقل دو تا از اعداد انتخاب شده دارای مجموعی برابر 1+2n هستند.

جواب سوال 2 :
در حالت کلی بدون اصل لانه کبوتری:
از مجموعه فوق هر مقداری برای n خاصه کوچکترین مقدار آن یعنی n=1 ،دو عدد 1 و 2 را در مجموعه خواهیم داشت . و میدانیم 2 و 1 نسبت به هم اولند ! پس حداقل دو عدد 1 و 2 رو که داریم .
در مورد قسمت( ب) هم مجموعه فوق یک تصاعد حسابی با قدر نسبت یک هست (جمله ابتدای تصاعد 1 و انتهای اون n+1 هست) اگر دو جمله متوالی دلخواه رو از این تصاعد مثل دو جمله آخر n و n+1 در نظر گرفته بشه ملاحظه میشه که مجموع اونا هست n+n+1=2n+1 پس حداقل دو عدد پیدا شد
نمیتونم ساده تر از این بگم

این مسائل فکر کنم مربوط به فصل سوم درس ساختمان گسسته باشه. از اونجایی که هنوز موفق نشدم این درس و فصل رو بخونم ، از شما فرصت میخام . با تشکر

[CHAPTER]

ممنون از توجه تون دوست عزیز
ولی مشکل همین هست که من بدونم کبوتر و لانه در این مسایل چی هستند و با استفاده از این اصل مسئله رو تحلیل کنم
وگرنه همه این مسایل دارای جواب بدیهی هستند.

[saber57]

جواب سوال3

برای حل این سوال به لینک زیر بروید و پس از دانلود فصل سوم ساختمان داده ، سوال 16 حل المسائل جواب سوال شما رو داده

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

ارادتمند سرباز خسته

[CHAPTER]

دست شما درد نکنه این دقیقا جواب سوال 3 هست ممنون
موند 7 تا دیگه (عجب پر رویی هستم)

[soheilsmart]

با سلام اگر امکان داره جواب این سوال ها رو می خواستم (اگر بر خلاف قوانین نیست )



2 - n+1 عدد از مجموعه { 1, 2, 3 , .... 2n}انتخاب شذه اند نشان دهید :
الف ) حداقل دو تا از اعداد انتخاب شده نسبت به هم اول هستند.
ب ) حداقل دو تا از اعداد انتخاب شده دارای مجموعی برابر 1+2n هستند.

4 - نشان دهید هر زیر مجموعه شش عضوی مجموعه {3,2,1,...,9} شامل دو عضو است که حاصل جمع آنها 10 است.

6- نشان دهید هرگاه 14 عدد از مجموعه {3,2,1,...,25} انتخاب نماییم دو عدد در این انتخاب وجود دارند که حاصل جمع آنها 26 است.

.

.

الف) لانه های رو برای این قسمت به این صورت در نظر میگیریم
{1,2},{3,4},..........{2n-1,2n}
تعداد لانه ها برایر n تاست
اما n+1 کبوتر داریم پس حداقل در یکی از لانه ها 2 کبوتر موجود است!
اما می دانیم دو عدد متوالی نسبت به هم اولند!
ما هم در اینجا حداقل دو عدد متوالی داریم.پس حداقل دو عدد هستند که نسبت به هم اولند.
ب)این بار لانه ها رو به صورت زیر در نظر می گیریم
{1,2n},{2,2n-1},{3,2n-2},........
تعداد لانه ها هم در این جالت n تاست و تعداد کبوتر ها n+1
پس حداقل در یکی از این لانه ها دو کبوتر وجود دارد
اما می دانیم مجموع دو عدد در هر لانه برابر است یا 2n+1
پس حداقل دو عدد یافتیم که مجموع آنها 2n+1 است.

6- مانند سوال2 قسمت ب
4- مانند 2 قسمت ب

[CHAPTER]

دوست عزیز ممنون
جواب بقیه رو نمیشه بگید مخصوصا 1 و 5
5 - فرض کنید m عددی فرد طبیعی باشد ثابت کنید یک عدد طبیعی مانند n وجود دارد که m عدد 1- 2n
2 به توان n منهای 1 را عاد می کند.

1- 10 عدد طبیعی متمایز و کوچکتر از 107 مفروض هستند. با استفاده از اصل لانه کبوتری نشان دهید که دو زیر مجموعه مجزا و نا تهی از این دو عدد یافت میشود که مجموع آنها یکسان است.

[saber57]

دوست عزیز ممنون
جواب بقیه رو نمیشه بگید مخصوصا 1 و 5
5 - فرض کنید m عددی فرد طبیعی باشد ثابت کنید یک عدد طبیعی مانند n وجود دارد که m عدد 1- 2n
2 به توان n منهای 1 را عاد می کند.

1- 10 عدد طبیعی متمایز و کوچکتر از 107 مفروض هستند. با استفاده از اصل لانه کبوتری نشان دهید که دو زیر مجموعه مجزا و نا تهی از این دو عدد یافت میشود که مجموع آنها یکسان است.

جواب سوال 5

اگر m ،عدد 2 به توان n منهای 1 رو عاد کنه یعنی اینکه 2 به توان n منهای 1 بر m بخشپذیر بشه .r باقیمانده تقسیم دارای این مقادیر:

{ r={0,1,2,3,...,m-1

تعداد مقادیر r یعنی m رو لانه و مجموعه اعداد 2 به توان n منهای 1 کبوتر فرض کنید (مقسوم) چون تعداد کبوترها بیشتر از تعداد لانه هاست ،بنابراین حداقل در یک لانه میتونه بیشتر از دو کبوتر قرار بگیره که یعنی د. عدد هستند که باقیمانده تقسیم اونا همون r هست،این دو عدد مقادیر زیر در نظر گرفته شد :

s ضریب دلخواهی هست

ملاحظه شد که عدد فوق(عددی پیدا شد) مضربی ار m هست یا اینکه m اونو عاد کرده

[CHAPTER]

می دونم وقت شما رو دارم میگیرم
خلاصه خیلی مخلصیم
ولی یک مونده هنوز

[saber57]

A رو مجموعه هایی در نظر بگیرین که مجموعشون با هم برابره . برای اینکه این مجموعه ها باهم برابر بشن اومدم عدد ابتدایی رو با انتهایی جمع کردم به این ترتیب که مجموع هر مجوعه برابر 108 بشه . ببینید :

{ a1={1,107

{ a2={2,106

{ a3={3,105

{ a4={4,104
.
.
.
{ a53={53,55

{ a54={54,54

مجموعه های فوق رو که 54 مجموعه هستند کبوتر و تعداد 10 عدد رو لانه کبوتر فرض کنید . چون تعداد کبوترها بیش از تعداد لانه هست لذا حداقل 2 زیر مجموعه وجود دارند که مجموعشون با هم برارند .از اونجایی که تمام مجموعه ها حتما یکی از اعداد 1 تا 107 رو دارند بنابراین دو مجموعه از اعداد 10 و 107 هم خواهیم داشت

همونطور که میدونیم این دو مجموعه در افراز و تعریف بالا مثلا زیر مجموعه های {1,107} و {10,98} میتونن باشند

اگه اشکال داشت دوستان کمک کنند تا با همفکری مسائل رو حل کنیم