دانلود با لینک مستقیم و پر سرعت .
ک پرداخت و دانلود *پایین مطلب*
فرمت فایل:Word (قابل ویرایش و آماده پرینت)
تعداد صفحه:12
فهرست مطالب
چکیده:
اصل لانه کبوتر بسیار روشن است و بسیار ساده به نظر می‌رسد، گویی دارای اهمیت زیادی نیست، ولی در عمل این اصل دارای اهمیت و قدرت بسیار زیادی است، زیرا تعمیمهای آن حاوی نتایجی عمیق در نظریه ترکیباتی و نظریه اعداد است. وقتی می‌گوئیم در هر گروه سه نفری از مردم حداقل دو نفر، هم جنس‌اند در واقع اصل لانه کبوتر را به کار گرفته‌ایم. فرض کنیم به تازگی در دانشکده‌ای، یک گروه علوم کامپیوتر تاسیس یافته که برای 10 عضو هیئت علمی آن فقط 9 دفتر‌کار موجود باشد. آن‌گاه باز هم ایده نهایی در پشت این ادعای بدیهی که حداقل از یک دفتر‌کار بیشتر از یک نفر است استفاده می‌کنند، اصل لانه کبوتر است. اگر به جای 10 نفر 19 عضو هیئت علمی وجود داشته باشد، آن‌گاه حداقل از یک دفتر‌کار بیشتر از دو نفر استفاده می‌کنند. همین‌طور، اگر در دانشکده‌ای حداقل 367 دانشجو وجود داشته باشند، باز آشکار است S حداقل دو نفر از آنها روز تولدشان یکی است. می‌گویند که سرانسان دارای حداکثر 999 و 99 تار مو است. از این رو در شهری S جمعیت آن بیشتر از 4 میلیون باشد، حداقل 41 نفر وجود دارند که تعداد موهای سرشان یکی است (سر طاس مو ندارد). مثالهای زیادی نظیر این را می‌توانیم نقل کنیم.
ایده اساسی حاکم بر همه‌ی این موارد حقیقت ساده‌ای مشهور به اصل لانه‌کبوتر دیر بلکه است.
که عبارت است از:
فرض کنید k و n دو عدد طبیعی‌اند. اگر بخواهیم بیشتر از nk+1 شی را در n جعبه قرار دهیم، حداقل یک جعبه وجود دارد که در آن حداقل k+1 شی قرار گرفته باشد. در حالت خاص، اگر حداقل n+1 شی را در n جعبه قرار دهیم، جعبه‌ای وجود دارد که در آن حداقل دو شی قرار گرفته باشد.
- هفده نفر در جلسه‌ای حضور دارند. آنها درباره سه موضوع بحث می‌کنند، هر دو نفر آنها درباره یک و فقط یک موضوع بحث می‌کنند. ثابت کنید یک گروه حداقل سه نفری وجود دارد که افراد آن با هم راجع به یک موضوع بحث کرده باشند.
حل: می‌توانیم 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) به رنگ آبی باشد. آن‌گاه این یال‌ها با رنگ‌های قرمز یا زرد خواهیم داشت. و این به این معنی است که حداقل سه نفر وجود دارند که با هم راجع به یک موضوع بحث کرده باشند.
- فرض کنیم {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 را می‌شمارد یا برعکس.
- اکبر در طول تعطیل چهار‌هفته‌ای خود هر روز حداقل یک دور تنیس بازی می‌کند. ولی در طی این مدت جمعاً بیش از 40 دور بازی نخواهد کرد. ثابت کنید که توزیع دفعات دورهای بازی او در طی چهارهفته هر چه باشد، تعدادی از روزهای متوالی وجود دارد که طی آنها دقیقاً 15 دور بازی می‌کند؟
حل:
برای ، فرض کنید xi، تعداد کل دورهایی باشد که اکبر از آغاز تعطیلات تا پایان روز I بازی کرده است. پس:
و
اینک 28 عدد متمایز x1 و x2 و... و x28 عدد متمایز 15+x1 ،15+x2 ،....،15+x28 داریم.
این 56 عدد می‌توانند تنها 55 مقدار مختلف اختیار کنند، بنابراین حداقل دو تا از آنها باید مساوی بوده و نتیجه می‌گیریم که رابطه باشرط 15+x=xi وجود دارد. لذا از شروع (1+j)ام تا آخر روز I اکبر دقیقاً 15 دور بازی خواهد کرد.
- کیسه‌ای حاوی دقیقاً 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
- 10 عدد طبیعی متمایز و کوچکتر از 107 مفروضند. نشان دهید که دو زیرمجموعه مجزا و غیرخالی این 10 عدد یافت می‌شود S مجموع اعضایشان یکسان است.
حل:
بزرگترین 10 عددی که می‌توانیم داشته باشیم 97، 98،....106 هستند که مجموع آنها 1015 هست. بنابراین کافی است 1015 لانه کبوتر با شماره‌های 1 و2 و ...و 1015 را در نظر بگیریم. هر مجموعه 10 عضو شامل 1023=1-210 زیرمجموعه زیرتهی است، که 1023 را تعداد کبوترها در نظر می‌گیریم. لذا بنا به اصل لانه کبوتری، حداقل 2 زیرمجموعه با مجموع یکسان وجود دارند. اعداد متناظر را از 2 مجموعه حذف میکنیم.
- فرض کنیم فرد باشد. ثابت کنید که عدد صحیح مثبتی مانند n وجود دارد به طوری که m عدد 1-2n را عادی می‌کند؟
حل: 1+m عد صحیح مثبت 1-21، 1-22، 1-23، ....، 1-2m، 1-2m+1 را در نظر می‌گیریم.
بنابراین اصل لانه کبوتر و الگوریتم تقسیم، اعدادی مانند وجود دارند به طوری که
9= تعداد روز چهارم + روز پنجم
لذا حداقل دنبالهای از دو روز متوالی چهارم و پنجم یافت شد که مجموع ساعاتی که دونده در آنها دویده 9 ساعت شود.
- فرض کنید{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 عددی زوج است.
- برای تمام اعداد طبیعی و 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تایی آبی است.
- 6 مهره قرمز، 5 مهره سفید و 7 مهره آبی در یک کیسه داریم. مطلوب است تعیین کمترین تعداد مهره‌هایی که باید انتخاب شوند تا مطمئن شویم S حداقل 3 مهره قرمز یا حداقل 4 مهره سفید یا حداقل 5 مهره آبی انتخاب شده است؟
حل:
اگر x و y و z به ترتیب تعداد مهره‌هایی به رنگ قرمز و سفید و آبی باشند که بناست انتخاب شوند، آن‌گاه اگر x=2 و y=3 و z=4، آن‌گاه جواب 9 است، بنابراین وضعیت مطلوب پیش نمی‌آید بدین‌سان باید حداقل 10 مهره انتخاب کنیم. (پاسخ 10 مهره)
که نتیجه می‌دهد:
پس می‌توان B را برابر {aj و ...ai-2 وaih} در نظر گرفت.
- هر دنباله مرکب از (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 زیر دنبالهای اکیداً کاهشی بدست خواهد داد.
منابع
- اصول و فنون ترکیبات مترجمین: حسین ربیعی
حسین غفاری
- ریاضیات گسسته و ترکیباتی رالف.پ.گریمالدی
ترجمه: دکتر محمد‌علی رضوانی
دکتر بیژن شمس
- ریاضیات گسسته مقدماتی ترجمه: دکتر بیژن شمس
دکتر محمد‌علی رضوانی
تألیف: و.ئ.بالاکریشنمان
- ریاضیات گسسته و ترکیباتی از دیدگاه کاربردی (جلد اول) رالف گریمالدی
ترجمه: علی عمیدی
فهرست
چکیده
حل مسائل متنوع
منابع
