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

واضح آرشیو وب فارسی:سایت ریسک: View Full Version : چند تا سوال از اصل لانه کبوتری CHAPTER18-04-2009, 06:52 PMبا سلام اگر امکان داره جواب این سوال ها رو می خواستم (اگر بر خلاف قوانین نیست ) 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 بازیکن وجود دارند که تعداد برد های آنها یکسان است. saber5718-04-2009, 10:09 PMبا سلام اگر امکان داره جواب این سوال ها رو می خواستم (اگر بر خلاف قوانین نیست ) 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 پس حداقل دو عدد پیدا شد نمیتونم ساده تر از این بگم این مسائل فکر کنم مربوط به فصل سوم درس ساختمان گسسته باشه. از اونجایی که هنوز موفق نشدم این درس و فصل رو بخونم ، از شما فرصت میخام . با تشکر CHAPTER18-04-2009, 11:25 PMممنون از توجه تون دوست عزیز :11: ولی مشکل همین هست که من بدونم کبوتر و لانه در این مسایل چی هستند و با استفاده از این اصل مسئله رو تحلیل کنم وگرنه همه این مسایل دارای جواب بدیهی هستند. saber5719-04-2009, 01:02 AMجواب سوال3 برای حل این سوال به لینک زیر بروید و پس از دانلود فصل سوم ساختمان داده ، سوال 16 حل المسائل جواب سوال شما رو داده http://fanavari-it.ir/index.php?option=com_content&task=view&id=1212&Itemid=46 http://www.freezpic.com/pics/2cf01c0fbf807b 1c381eabd 25cdab 622.gif http://upload.iranblog.com/2/1203392080.gifhttp://upload.iranblog.com/2/1203392080.gifhttp://upload.iranblog.com/2/1203392080.gifhttp://upload.iranblog.com/2/1203392080.gif ارادتمند سرباز خسته CHAPTER19-04-2009, 09:56 AMدست شما درد نکنه این دقیقا جواب سوال 3 هست ممنون :10::11: موند 7 تا دیگه (عجب پر رویی هستم) :46: soheilsmart19-04-2009, 11:56 AMبا سلام اگر امکان داره جواب این سوال ها رو می خواستم (اگر بر خلاف قوانین نیست ) 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 قسمت ب CHAPTER19-04-2009, 12:10 PMدوست عزیز ممنون جواب بقیه رو نمیشه بگید :40: مخصوصا 1 و 5 5 - فرض کنید m عددی فرد طبیعی باشد ثابت کنید یک عدد طبیعی مانند n وجود دارد که m عدد 1- 2n 2 به توان n منهای 1 را عاد می کند. 1- 10 عدد طبیعی متمایز و کوچکتر از 107 مفروض هستند. با استفاده از اصل لانه کبوتری نشان دهید که دو زیر مجموعه مجزا و نا تهی از این دو عدد یافت میشود که مجموع آنها یکسان است. saber5719-04-2009, 05:52 PMدوست عزیز ممنون جواب بقیه رو نمیشه بگید :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 هست،این دو عدد مقادیر زیر در نظر گرفته شد : http://www.freezpic.com/pics/7a 399c9333c0cb 2fc1068f3baaf88120.gif s ضریب دلخواهی هست :thumbsdow http://www.freezpic.com/pics/c1ebe7a 2b 7a 8c6c05d 6c6365b 7d 42d 2f.gif ملاحظه شد که عدد فوق(عددی پیدا شد) مضربی ار m هست یا اینکه m اونو عاد کرده CHAPTER19-04-2009, 06:58 PMمی دونم وقت شما رو دارم میگیرم خلاصه خیلی مخلصیم :40::11::10: ولی یک مونده هنوز :20: saber5719-04-2009, 11:33 PMA رو مجموعه هایی در نظر بگیرین که مجموعشون با هم برابره . برای اینکه این مجموعه ها باهم برابر بشن اومدم عدد ابتدایی رو با انتهایی جمع کردم به این ترتیب که مجموع هر مجوعه برابر 108 بشه . ببینید : { a 1={1,107 { a 2={2,106 { a 3={3,105 { a 4={4,104 . . . { a 53={53,55 { a 54={54,54 مجموعه های فوق رو که 54 مجموعه هستند کبوتر و تعداد 10 عدد رو لانه کبوتر فرض کنید . چون تعداد کبوترها بیش از تعداد لانه هست لذا حداقل 2 زیر مجموعه وجود دارند که مجموعشون با هم برارند .از اونجایی که تمام مجموعه ها حتما یکی از اعداد 1 تا 107 رو دارند بنابراین دو مجموعه از اعداد 10 و 107 هم خواهیم داشت همونطور که میدونیم این دو مجموعه در افراز و تعریف بالا مثلا زیر مجموعه های {1,107} و {10,98} میتونن باشند اگه اشکال داشت دوستان کمک کنند تا با همفکری مسائل رو حل کنیم :46: CHAPTER19-04-2009, 11:51 PMهمین که وقت گذاشتید و پاسخ دادید ممنون :10: این سوال یک یه جورایی گنگ هستش 1- 10 عدد طبیعی متمایز و کوچکتر از 107 مفروض هستند. با استفاده از اصل لانه کبوتری نشان دهید که دو زیر مجموعه مجزا و نا تهی از این دو عدد یافت میشود که مجموع آنها یکسان است. نمی دونم جواب شما درست هستش (جسارتا) saber5720-04-2009, 12:12 AMهمین که وقت گذاشتید و پاسخ دادید ممنون :10: این سوال یک یه جورایی گنگ هستش 1- 10 عدد طبیعی متمایز و کوچکتر از 107 مفروض هستند. با استفاده از اصل لانه کبوتری نشان دهید که دو زیر مجموعه مجزا و نا تهی از این دو عدد یافت میشود که مجموع آنها یکسان است. نمی دونم جواب شما درست هستش (جسارتا) ببینید شما باید دو زیر مجموعه پیدا کنید که اعداد 10 و 107 در اونا وجود داشته باشه البته بصورت مجزا 54 زیر مجموعه تعریف کردم که مجموع اعدادشون یکسان بود . من تصور میکنم منظور مساله از یکسان بودن مجموع ، یکسان بودن مجموع اعداد واقع در هر زیر مجموعه هست . ما از اعداد 1 تا 107 ، 10 عدد طبیعی میخایم انتخاب کنیم که شرایط بالا رو داشته باشه . همونطور که دیدیم هر زیر مجموعه از 54 زیر مجموعه ای که تعریف شد ، یکی از اعداد 1 تا 107 رو دارا بود و در عین حال تمام مجموعه ها مجزا از هم بودند . اگه از سوال مطمئن هستید، از دوستانی که در زمینه مبحث ریاضیات گسسته کار کرده اند خواهش دارم کمک کنند CHAPTER20-04-2009, 09:41 AMشاید باید از اول می گفتم اینا تمرینات صفحه 48 کتاب ریاضیات گسسته دکتر مسعود نیکوکار هستش soheilsmart21-04-2009, 11:20 AMبا سلام اگر امکان داره جواب این سوال ها رو می خواستم (اگر بر خلاف قوانین نیست ) . 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 لانه بشن! پس حداقل در یکی از لانه ها دو تا بازیکن وجود داره یعنی حداقل دو نفر وجود دارن که تعداد بردهای اونا یکسانه! soheilsmart21-04-2009, 11:35 AMهمین که وقت گذاشتید و پاسخ دادید ممنون :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: CHAPTER21-04-2009, 07:11 PMالبته یه خورده دیر شده , تمرینات رو تحویل دادم :20: کاش زودتر گفته بودی ولی از مرام و معرفت بچه های p30world چیزی کم نمی شه :10: من شرمنده دوستان شدم :11: دست شما درد نکه آقا سهیل و همچنین آقا صابر (اگر اشتباه نکم) :40: دکمه تشکر برای شما کمه baran latifi17-05-2009, 11:34 PMبا سلام اگر امکان داره جواب این سوال ها رو می خواستم (اگر بر خلاف قوانین نیست ) 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: سایت ما را در گوگل محبوب کنید با کلیک روی دکمه ای که در سمت چپ این منو با عنوان +1 قرار داده شده شما به این سایت مهر تأیید میزنید و به دوستانتان در صفحه جستجوی گوگل دیدن این سایت را پیشنهاد میکنید که این امر خود باعث افزایش رتبه سایت در گوگل میشود

این صفحه را در گوگل محبوب کنید

[ارسال شده از: سایت ریسک]

[مشاهده در: www.ri3k.eu]

[تعداد بازديد از اين مطلب: 3093]