اصل لانه کبوتر

لینک دانلود و خرید پایین توضیحات

فرمت فایل 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 مهره همرنگ‌اند

دانلود مقاله اصل لانه کبوتر

لینک دانلود و خرید پایین توضیحات

فرمت فایل 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 لانه کبوتر داریم: