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

[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]

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

[saber57]

جواب سوال3

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



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

[ برای مشاهده لینک ، لطفا با نام کاربری خود وارد شوید یا ثبت نام کنید ] [ برای مشاهده لینک ، لطفا با نام کاربری خود وارد شوید یا ثبت نام کنید ]
ارادتمند سرباز خسته

[CHAPTER]

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

[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]

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

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

[saber57]

دوست عزیز ممنون
جواب بقیه رو نمیشه بگید :40: مخصوصا 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 ضریب دلخواهی هست :thumbsdow


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





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

[CHAPTER]

می دونم وقت شما رو دارم میگیرم
خلاصه خیلی مخلصیم :40::11::10:
ولی یک مونده هنوز :20:

[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} میتونن باشند



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

[CHAPTER]

همین که وقت گذاشتید و پاسخ دادید ممنون :10:
این سوال یک یه جورایی گنگ هستش

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

نمی دونم جواب شما درست هستش (جسارتا)

[saber57]

همین که وقت گذاشتید و پاسخ دادید ممنون :10:
این سوال یک یه جورایی گنگ هستش

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

نمی دونم جواب شما درست هستش (جسارتا)

ببینید شما باید دو زیر مجموعه پیدا کنید که اعداد 10 و 107 در اونا وجود داشته باشه البته بصورت مجزا

54 زیر مجموعه تعریف کردم که مجموع اعدادشون یکسان بود . من تصور میکنم منظور مساله از یکسان بودن مجموع ، یکسان بودن مجموع اعداد واقع در هر زیر مجموعه هست . ما از اعداد 1 تا 107 ، 10 عدد طبیعی میخایم انتخاب کنیم که شرایط بالا رو داشته باشه . همونطور که دیدیم هر زیر مجموعه از 54 زیر مجموعه ای که تعریف شد ، یکی از اعداد 1 تا 107 رو دارا بود و در عین حال تمام مجموعه ها مجزا از هم بودند .

اگه از سوال مطمئن هستید، از دوستانی که در زمینه مبحث ریاضیات گسسته کار کرده اند خواهش دارم کمک کنند

[CHAPTER]

شاید باید از اول می گفتم اینا تمرینات صفحه 48 کتاب ریاضیات گسسته دکتر مسعود نیکوکار هستش

[soheilsmart]

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



.

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

8- در یک مسابقه دوره ای که هر دو بازیکن دقیقا 1 بار با هم مسابقه می دهند فرض کنید هر بازیکن حداقل یک بار برنده شود. نشان دهید حداقل 2 بازیکن وجود دارند که تعداد برد های آنها یکسان است.
7- برای حل این گونه مسائل باید از اصل لانه ی کبوتری به طور درست استفاده نماییم.
حالتی را در نظر میگیرم که در ان هر کدام از اعداد روی وجوه تاس n-1 بار آمده اند اگر بار دیگر تاس را پرتاب کنیم یکی از اعداد در مجموع پرتاب ها n بار ظاهر شده است!
بنابراین تعداد حالات مطلوب برابر است :
6*(n-1)
+1
6n-5=
برای حل این مسائل چون ما حالت کلی رو بررسی میکنیم باید بدترین حالت(این اسمی که من میگم- هر کسی یه تعریفی داره از این حالت) رو در نظر بگیریم
8-فرض می کنیم تعداد بازیکنان n تاست.هر بازیکن بار هر بازیگن دیگه دقیقا یکبار بازی میکنه.
بنابرین هر نفر با n-1 نفر بازی میکنه
چون میدانیم که هر بازیکن حداقل یک بازی رو میبره !
بنابراین تعداد بردهای هر بازیکن می تونه عددی بین 1 تاn-1 باشه( کلا n-1 حالت وجود داره)
اما n تا بازیکن ( کبوتر ) داریم که می خوان وارد این n-1 لانه بشن!
پس حداقل در یکی از لانه ها دو تا بازیکن وجود داره یعنی حداقل دو نفر وجود دارن که تعداد بردهای اونا یکسانه!

[soheilsmart]

همین که وقت گذاشتید و پاسخ دادید ممنون :10:
این سوال یک یه جورایی گنگ هستش

1- 10 عدد طبیعی متمایز و کوچکتر از 107 مفروض هستند. با استفاده از اصل لانه کبوتری نشان دهید که دو زیر مجموعه مجزا و نا تهی از این دو عدد یافت میشود که مجموع آنها یکسان است.
)
هر زیر مجموعه دلخواه از مجموعه مفروض دلخواه در نظر بگیریم
این رابطه برقرار است.
106+105+104+103+102+101+100+99+98+97>=مجموع اعضای هر زیر مجموعه ی دلخواه>=1
1015>=مجموع اعضای هر زیر مجموعه ی دلخواه>=1
اما می دانیم که یک مجوعه 10 عضوی
10-1^2
زیر مجموعه ناتهی دارد که برابر 1023 است.
تعداد لانه ها 1015 تا است
در صورتی که تعداد کبوتر ها 1023 است
به وضوح معلوم است
که در یکی از لانه ها حداقل دو کبوتر وجود دارد:11:

[CHAPTER]

البته یه خورده دیر شده , تمرینات رو تحویل دادم :20: کاش زودتر گفته بودی
ولی از مرام و معرفت بچه های p30world چیزی کم نمی شه :10:
من شرمنده دوستان شدم :11:
دست شما درد نکه آقا سهیل و همچنین آقا صابر (اگر اشتباه نکم) :40:
دکمه تشکر برای شما کمه

[baran latifi]

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

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 بازیکن وجود دارند که تعداد برد های آنها یکسان است.
با عرض سلام و خسته نباشید من تازه عضو شدم نمی دونستم سوالمو کجا مطرح کنم این جا نوشتم ببخشید
می شه راجع به صورت قوی تر اصل لانه کبوتری توضیح بدین ممنون:11: