دانلود مقاله اصل لانه كبوتر در فایل ورد (word)

توضیحات

  مقاله اصل لانه كبوتر در فایل ورد (word) دارای 16 صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد مقاله اصل لانه كبوتر در فایل ورد (word)  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل ورد می باشد و در فایل اصلی مقاله اصل لانه كبوتر در فایل ورد (word)،به هیچ وجه بهم ریختگی وجود ندارد

بخشی از متن مقاله اصل لانه كبوتر در فایل ورد (word) :

اصل لانه كبوتر
چكیده:
اصل لانه كبوتر بسیار روشن است و بسیار ساده به نظر می‌رسد، گویی دارای اهمیت زیادی نیست، ولی در عمل این اصل دارای اهمیت و قدرت بسیار زیادی است، زیرا تعمیمهای آن حاوی نتایجی عمیق در نظریه تركیباتی و نظریه اعداد است. وقتی می‌گوئیم در هر گروه سه نفری از مردم حداقل دو نفر، هم جنس‌اند در واقع اصل لانه كبوتر را به كار گرفته‌ایم. فرض كنیم به تازگی در دانشكده‌ای، یك گروه علوم كامپیوتر تاسیس یافته كه برای 10 عضو هیئت علمی آن فقط 9 دفتر‌كار موجود باشد.

آن‌گاه باز هم ایده نهایی در پشت این ادعای بدیهی كه حداقل از یك دفتر‌كار بیشتر از یك نفر است استفاده می‌كنند، اصل لانه كبوتر است. اگر به جای 10 نفر 19 عضو هیئت علمی وجود داشته باشد، آن‌گاه حداقل از یك دفتر‌كار بیشتر از دو نفر استفاده می‌كنند. همین‌طور، اگر در دانشكده‌ای حداقل 367 دانشجو وجود داشته باشند، باز آشكار است S حداقل دو نفر از آنها روز تولدشان یكی است.

می‌گویند كه سرانسان دارای حداكثر 999 و 99 تار مو است. از این رو در شهری S جمعیت آن بیشتر از 4 میلیون باشد، حداقل 41 نفر وجود دارند كه تعداد موهای سرشان یكی است (سر طاس مو ندارد). مثالهای زیادی نظیر این را می‌توانیم نقل كنیم.

ایده اساسی حاكم بر همه‌ی این موارد حقیقت ساده‌ای مشهور به اصل لانه‌كبوتر دیر بلكه است.

كه عبارت است از:
فرض كنید ‌k و n دو عدد طبیعی‌اند. اگر بخواهیم بیشتر از nk+1 شی را در n جعبه قرار دهیم، حداقل یك جعبه وجود دارد كه در آن حداقل k+1 شی قرار گرفته باشد. در حالت خاص، اگر حداقل n+1 شی را در n جعبه قرار دهیم، جعبه‌ای وجود دارد كه در آن حداقل دو شی قرار گرفته باشد.
1 هفده نفر در جلسه‌ای حضور دارند. آنها درباره سه موضوع بحث می‌كنند، هر دو نفر آنها درباره یك و فقط یك موضوع بحث می‌كنند. ثابت كنید یك گروه حداقل سه نفری وجود دارد كه افراد آن با هم راجع به یك موضوع بحث كرده باشند.

حل: می‌توانیم 17 نفر را 17 نقطه در نظر بگیریم كه هر دوتایی به توسط یك بال به هم وصل شده‌اند. بالی را كه X و Y را به هم متصل می‌كند، آبی می‌كنیم اگر آن دو درباره موضوع (1) بحث كرده باشند و قرمز می‌كنیم اگر راجع به موضوع (2) بحث كرده باشند و به رنگ زرد در می‌آوریم. اگر آن دو درباره موضوع (3) با هم به بحث پرداخته باشند. بنابراین هر كدام از 16 بالی كه از A گذشته‌اند با یكی از سه‌رنگ آبی،‌ قرمز یا زرد رنگ شده است.

از آن‌جایی كه 1+3×5=16، طبق اصل لانه كبوتری حداقل 1+5 رأس یافت می‌شود، كه با یك رنگ به A متصل شده باشند. بدون اینكه به كلیت مساله لطمه بخورد فرض می‌‌‌كنیم یال‌‌های AG,AF,AE,AD,AC,AB با رنگ آبی، رنگ‌آمیزی شده باشند. حال 6 رأس G,F,E,D,C,B را در نظر بگیرید كه با 15 یال به هم متصل شده‌اند. اگر هر كدام از این یال‌ها (مثلاً BC) به رنگ آبی باشد. آن‌گاه این یال‌ها با رنگ‌های قرمز یا زرد خواهیم داشت. و این به این معنی است كه حداقل سه نفر وجود دارند كه با هم راجع به یك موضوع بحث كرده باشند.

2 فرض كنیم {n2 و ;و 3و2و1}=X و فرض نمائیم S زیر مجموعه‌ای (1+n) عنصری از x باشد. آن‌گاه حداقل دو عدد در S وجود دارند به طوری كه یكی دیگری را می‌شمارد.

اثبات: هر عدد دلخواه r متعلق به S را می‌توان به صورتS .2t= r نمایش داد كه در آن،T یك عدد صحیح نامنفی و S عدد فرد متعلق به X، به نام قسمت فرد (r) است. برای S حداكثر n انتخاب وجود دارد، زیرا n عدد فرد در X وجود دارد. این n قسمت فرد را می‌توان به عنوان n لانه كبوتر در نظر گرفت كه قرار است (1+n) عدد متعلق به S را بین این لانه‌ها پخش كنیم. به عبارت دیگر، دو عدد مانند x و y در s وجود دارند كه قسمت فرد آنها یكی است. فرض كنیم s.2t=x و.2u.s=y آن‌گاه یا x عدد y را می‌شمارد یا برعكس.

3 اكبر در طول تعطیل چهار‌هفته‌ای خود هر روز حداقل یك دور تنیس بازی می‌كند. ولی در طی این مدت جمعاً بیش از 40 دور بازی نخواهد كرد. ثابت كنید كه توزیع دفعات دورهای بازی او در طی چهارهفته هر چه باشد، تعدادی از روزهای متوالی وجود دارد كه طی آنها دقیقاً 15 دور بازی می‌كند؟
حل:
برای ، فرض كنید xi، تعداد كل دورهایی باشد كه اكبر از آغاز تعطیلات تا پایان روز I بازی كرده است. پس:
و

اینك 28 عدد متمایز x1 و x2 و; و x28 عدد متمایز 15+x1 ،15+x2 ،;.،15+x28 داریم.
این 56 عدد می‌توانند تنها 55 مقدار مختلف اختیار كنند، بنابراین حداقل دو تا از آنها باید مساوی بوده و نتیجه می‌گیریم كه رابطه باشرط 15+x=xi وجود دارد. لذا از شروع (1+j)ام تا آخر روز I اكبر دقیقاً‌ 15 دور بازی خواهد كرد.

4 كیسه‌ای حاوی دقیقاً 5 مهره قرمز،8 مهره آبی، 10 مهره سفید و 12 مهره سبز و 7 مهره زرد است. مطلوب است تعیین تعداد مهره‌هایی كه باید انتخاب شوند تا مطمئن شویم كه:
الف)‌ حداقل 4 مهره همرنگ‌اند
ب) حداقل 7 مهره همرنگ‌اند
پ) حداقل 6 مهره همرنگ‌اند
ت) حداقل 9 مهره همرنگ‌اند

حل:
5 رنگ داخل كیسه وجود دارد. لذا 5 لانه كبوتر داریم:

ج الف) 16
ب) 30=1+4×6+5
پ) 26=1+4×5+5
ت) 37=1+2×8+7+8+5

5 10 عدد طبیعی متمایز و كوچكتر از 107 مفروضند. نشان دهید كه دو زیرمجموعه مجزا و غیرخالی این 10 عدد یافت می‌شود S مجموع اعضایشان یكسان است.
حل:
بزرگترین 10 عددی كه می‌توانیم داشته باشیم 97، 98،;.106 هستند كه مجموع آنها 1015 هست. بنابراین كافی است 1015 لانه كبوتر با شماره‌های 1 و2 و ;و 1015 را در نظر بگیریم. هر مجموعه 10 عضو شامل 1023=1-210 زیر‌مجموعه زیرتهی است، كه 1023 را تعداد كبوترها در نظر می‌گیریم. لذا بنا به اصل لانه كبوتری، حداقل 2 زیرمجموعه با مجموع یكسان وجود دارند. اعداد متناظر را از 2 مجموعه حذف می‌كنیم.

6 فرض كنیم فرد باشد. ثابت كنید كه عدد صحیح مثبتی مانند n وجود دارد به طوری كه m عدد 1-2n را عادی می‌كند؟
حل: 1+m عد صحیح مثبت 1-21، 1-22، 1-23، ;.، 1-2m، 1-2m+1 را در نظر می‌گیریم.
بنابراین اصل لانه كبوتر و الگوریتم تقسیم، اعدادی مانند وجود دارند به طوری كه

9= تعداد روز چهارم + روز پنجم
لذا حداقل دنباله‌ای از دو روز متوالی چهارم و پنجم یافت شد كه مجموع ساعاتی كه دونده در آنها دویده 9 ساعت شود.
7 فرض كنید{a5 و ;..a2 وa1}=A مجموعه‌ای از 5 عدد صحیح و مثبت باشد. نشان دهید كه برای هر جایگشت مانند{ai5 و;وai1}=B از مجموعه A حاصل ضرب
(ai1-a1) (ai2-a2)…(ai5-a5)
عددی زوج است.

حل:
ضرب n عدد زوج است، هرگاه حداقل یكی از اعداد زوج باشد، بنابراین یكی از (aij-aj) عدد زوج است. یعنی aj و aij یا هردو زوج‌اند و یا هردو فردند. طبق اصل لانه كبوتری، حداقل 3 عضو از مجموعه A دارای زوجیت یكسان هستند.
به عنوان مثال، a1 و a2 و a3 از مجموعه A را در نظر می‌گیریم كه هر سه فردند یا زوج. لذا روشن است كه Q {a13 و a12 و a11} {a3 و a2 و a1} (زیرا مجموعه A بایست حداقل دارای 6 عضو {a13,a12,ali,a3,a2,a1} باشد). به عبارتی دیگر مجموعه {a1,a2,a3,a11,a12,a13}=c حداقل دو عضو برابر دارد. فرض كنید a11= a3. بنابراین a1-a3=a1-a11 در نتیجه a1-a11 عددی زوج است.

8 برای تمام اعداد طبیعی و p ثابت كنید R+ R (p,q) R .
اثبات:
فرض كنیم . طبق قضیه رمزی (برای تمام اعداد طبیعی2 q و p، عدد R(p.q) با شرط ذكر شده، وجود دارد.) و برای اثبات قضیه كافی است كه نشان دهیم كه اگر دسته نقطه‌ی nتایی را بادو رنگ قرمز و آبی رنگ كنیم، آن‌گاه یك دسته‌ی نقطه‌ای pتایی با یك دسته نقطه‌ی qتایی قرمز وجود دارد. سه نقطه‌‌ی nتایی را با kn نشان می‌دهیم.

یك رأس ثابت V در Kn را در نظر بگیرید. از v، 1-n یال در kn عبور كرده است:

طبق تعمیم یافته اصل لانه كبوتری R(P-1,q) یال گذرنده از v وجود دارد كه با آبی رنگ شده‌اند یا R(P,q-1) گذرنده v وجود دارند كه با قرمز رنگ شده‌اند. فرض می‌كنیم حالت اول درست باشد. فرض كنید x مجموعه نقاطی باشد كه این R(P,q-1) به v وصل شده‌اند. از آن‌جا كه طبق تعریف مجموعه‌ی x شامل یك دسته‌ی نقطه (p-1)تایی آبی باشد، آن‌گاه مجموعه {v} x یك دسته نقطه qتایی آبی است.

9 6 مهره قرمز، 5 مهره سفید و 7 مهره آبی در یك كیسه داریم. مطلوب است تعیین كمترین تعداد مهره‌هایی كه باید انتخاب شوند تا مطمئن شویم S حداقل 3 مهره قرمز یا حداقل 4 مهره سفید یا حداقل 5 مهره آبی انتخاب شده است؟
حل:
اگر x و y و z به ترتیب تعداد مهره‌هایی به رنگ قرمز و سفید و آبی باشند كه بناست انتخاب شوند، آن‌گاه اگر x=2 و y=3 و z=4، آن‌گاه جواب 9 است، بنابراین وضعیت مطلوب پیش نمی‌آید بدین‌سان باید حداقل 10 مهره انتخاب كنیم. (پاسخ 10 مهره)
كه نتیجه می‌دهد:

پس می‌توان B را برابر {aj و ;ai-2 وaih} در نظر گرفت.
10 هر دنباله مركب از (n2+1) عدد صحیح متمایز شامل زیر دنباله‌ای با حداقل (n+1) جمله است كه یا دنباله‌‌‌ای افزایشی است یا دنباله‌ای كاهشی.
اثبات: فرض كنیم دنباله مورد بحث ai (I=1,2,…,n2+1) باشد فرض كنیم ti عبارت باشد از تعداد جمله‌های واقع در طولانی‌ترین زیر دنباله افزایشی كه با ai شروع می‌شود. اگر به ازای iای داشته باشیم ti=n+1 آن‌گاه كار تمام است. فرض كنیم كه به ازای هر I داشته باشیم . قرار می‌دهیم {j=ti:ai}= HJ كه در آن n و ;2و1 = j . بدین‌سان n لانه كبوتر H1 و H2 و;Hn را داریم S بناست (n2+1) عدد ti را بین آنها پخش كنیم. از این رو بنابر اصل لانه‌ی كبوتر تعمیم یافته، لانه‌ای مانند Hr شامل بیش از kتا از این اعداد كه در آن k مقدار گردشده نقصانی است، وجود دارد.

بنابراین حداقل (n+1) تا از اعداد ti با هم برابرند. اینك این را ثابت می‌كنیم كه (n+1) عدد واقع در دنباله مفروض كه متناظر با این اعداد واقع در لانه Hrاند دنباله‌ای كاهشی تشكیل می‌دهند. فرض كنیم در Hr باشند یا یا زیرا عناصر مورد بحث متمایزند. فرض كنیم . حال ، مستلزم این است كه زیر دنباله‌ای به طول r وجود داشته باشد كه با aj شروع شود. از این‌رو، نتیجه می‌گیریم كه زیر دنباله‌ای به طول (Rh) وجود دارد كه با ai شروع می‌شود. این یك تناقص است زیرا با توجه به اینكه ai عنصری از Hr است نمی‌توان زیر دنباله‌ای به طول (r+1) داشت كه با ai شروع شود. بدین‌سان وقتی باید . از این رو، هر (n+1) عنصر دلخواه در Hr زیر دنباله‌ای اكیداً كاهشی بدست خواهد داد.

منابع
1 اصول و فنون تركیبات مترجمین: حسین ربیعی
حسین غفاری
2 ریاضیات گسسته و تركیباتی رالف.پ.گریمالدی
ترجمه: دكتر محمد‌علی رضوانی
دكتر بیژن شمس
3 ریاضیات گسسته مقدماتی ترجمه: دكتر بیژن شمس
دكتر محمد‌علی رضوانی
تألیف: و.ئ.بالاكریشنمان
4 ریاضیات گسسته و تركیباتی از دیدگاه كاربردی (جلد اول) رالف گریمالدی
ترجمه: علی عمیدی

برای دریافت اینجا کلیک کنید