این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.
ساده‌ترین صورت از اصل لانه کبوتری که اصل حجره‌ها نیز نامیده می‌شود به شکل زیر است:
اگرقطعه الماس درون جعبه توزیع شوند آنگاه حداقل یک جعبه شامل بیش از یک الماس است.
البته این اصل به این صورت نیز بیان می‌گردد که: کبوتر که می‌خواهند در لانه بنشینند آنگاه حداقل یک لانه شامل بیش از یک کبوتر خواهد بود.
این اصل ترکیبیاتی ساده اولین بار توسط دیریکله (1895 – 1805) در نظریه اعداد مورد استفاده قرار گرفت. این اصل بسیار ساده برخلاف انتظار، کابردهای بسیاری دارد و با استفاده از آن قضایای مهمی به اثبات می‌رسند.
فرانک رمزی یکی از کسانی بود که تعمیم‌های وسیعی از این اصل ارائه کرد. امروزه مبحث «اعداد رمزی» یکی از بخش‌های مهم در علم ترکیبیات است و بد نیست بدانید که پیشرفت در این شاخه به کندی صورت می‌گیرد و مسائل مبارزه طلب هر روز در آن بیشتر می‌شوند.
اغلب فهمیدن این موضوع که درکجا باید از اصل لانه کبوتری استفاده کرد کار سختی نیست، به عنوان مثال در مسائل وجودی مربوط به مجموعه‌های متناهی (و در بعضی موارد نامتناهی) این اصل می‌تواند کارساز باشد. کار مشکل در این بین پیداکردن الماس‌ها و جعبه‌ها (حجره‌ها) می‌باشد!
برای آشنایی بد نیست به چند مسئله بدون حل در این موارد توجه کنید.
1.در بین سه نفر حتماً دونفر با یک جنسیت وجود دارند.
2.در بین 13 نفر حتماً دو نفر هستند که در یک ماه متولد شده‌اند.
3.هیچ شخصی بیشتر از 300000 تار مو در سر خود ندارند. پایتخت کشورمان ایران بیش از 300000 نفر جمعیت دارد، آیا می‌توانید با اطمینان بگویید که دو نفر در این شهر هستند که تعداد موهای سرشان برابر است؟
4.چند نفر لازم می‌دانید که مطمئن باشید که دو نفر آنها در یک روز هفته متولد شده‌اند.
5.اگر الماس درون جعبه به دلخواه توزیع شوند. آنگاه حداقل یک جعبه شامل بیش از الماس است.
6.خط در صفحه مثلث قرار دارد به طوری که از رئوس مثلث عبور نمی‌کند. نشان دهید خط l نمی‌تواند تمام اضلاع مثلث را قطع کند .
7.یک صفحه از هیچ رأس از یک چهاروجهی منتظم نمی‌گذرد. این صفحه حداکثر چند ضلع از چهاروجهی را قطع می‌کند؟
8.یک صفحه هدف به شلیک مثلثی متساوی‌الاضلاع به ضلع 2 است.
الف.نشان دهید اگر 5 بار با تیر به آن بزنیم دو سوراخ روی آن است که فاصله آنها کمتر یا مساوی 1 است.
ب.اگر 17 بار با تیر به این هدف بزنیم کمترین فاصله بین سوراخ‌ها حداکثر چقدر می‌تواند بزرگ باشد؟
9.دوره تناوب نمایش اعشاری کسر که و نسبت به هم اولند. حداکثر برابراست.
10.یازده عدد اعشاری با نمایش نامتناهی داریم، نشان دهیدمی‌توان دو تا از آنها مانند و پیدا کرد به طوری که نمایش متناهی باشد یا نامتناهی صفر داشته باشد.
11.12 عدد دورقمی متمایز داریم، نشان دهید دو تا از آنها موجودند به طوری که تفاضلشان عددی به شکل است.
12.اگر هیچ‌کدام از اعداد بر بخش‌پذیر نباشند آنگاه و نسبت به هم اولند (یعنی ب . م . م آنها یک است.)
مثال‌های بعد پاره‌ای کابردهای خاص‌تر از اصل لانه کبوتری را نشان می‌دهند.
نفر در یک اتاق حاضر هستند. نشان دهید در بین آنها دو نفر وجود دارند که تعداد دوستانشان در این اتاق برابر است.
حل جعبه با شماره‌های در نظر می‌گیریم. اسم یک نفر را درون جعبه شماره نه قرار می‌دهیم اگر او در بین افراد حاضر در اتاق نه دوست داشته باشد. بنابراین نفر و جعبه داریم، جعبه‌های شماره 0 و همزمان نمی‌توانند پرباشند زیرا اگر شخصی باشد که با نفر دوست باشد یعنی با همه افراد اتاق (غیر از خودش) دوست باشد دیگر شخصی با تعداد صفر دوست در اتاق وجود ندارد. پس نفر در جعبه قرار گرفته‌اند، پس یک جعبه موجود است به طوری که شامل حداقل دو نفر است. پس دو نفر وجود دارند که تعداد دوستانشان با هم برابر است.
یک تنیس‌باز 77 روز فرصت دارد تا خود را برای یک مسابقه مهم آماده کند او می‌خواهد در هر روز اقلاً یک‌بار به طور تمرینی با دوستش بازی کند ولی در طول این مدت دقیقاً 132 بازی تمرینی انجام دهد. نشان دهید با این فرضیات حتماً دنباله‌ای از روزهای متوالی وجود دارند که طی آنها دقیقاً 21 بازی انجام داده است.
حل فرض کنید تعداد بازی‌هایی باشد که تا روز ام انجام داده است. در این صورت
در نتیجه
بنابراین دو عدد از بین 154 عدد و برابرند. در نتیجه دو اندیس متمایز، و وجود دارند به طوری که . پس این شطرنج باز در طول روزهای
روی هم 21 بازی انجام داده است.
فرض کنید ، عدد صحیح نه لزوماً نامساوی باشند. در این صورت زیرمجموعه‌ای از این اعداد وجود دارد که مجموع اعضایش بر بخش‌پذیر است.
حل عدد صحیح را در نظر بگیرید
اگر یکی از ها بر بخش‌پذیر باشد حکم مسأله ثابت شده، فرض کنید این‌طور نباشد و باقیمانده‌های عدد صحیح فوق به هنگ متفاوت باشد. چون برای باقیمانده‌های آنها در تقسیم بر ، امکان مختلف وجود دارد، دو تا از این اعداد مانند وجود دارند که باقیمانده آنها به هنگ برابر است، بنابراین تفاضل زیر بر بخش‌پذیر است.
عدد ازانتخاب شده است، نشان دهید از میان اعداد انتخاب شده یکی بر دیگری بخش‌پذیر است.
حل فرض کنید عدد مفروض باشند، آنها را به شکل می‌نویسیم که عددی فرد باشد. در این صورت ، عدد فرد می‌باشند که بین 1 و قرار دارند و چون در این بازه عدد فرد بیشتر نداریم پس دوتا از ها مانند و برابرند، بنابراین از دو عدد و یکی بر دیگری بخش‌پذیر است.
فرض کنید دو عدد نسبت به هم اول باشند. در این صورت ای متعلق به وجود دارند به طوری که حل اعداد را در نظر بگیرید، هیچ‌کدام از این اعداد طبق فرض بر بخش‌پذیر نیستند، زیرا اگر یکی از این اعداد مانندبر بخش‌پذیر باشد چون و بخش‌پذیر باشد چون و نسبت به هم اول می‌باشند، نتیجه می‌شود بر بخش‌پذیر است اما عددی بین 1 و است و چنین چیزی غیرممکن است. بنابراین اگر باقیمانده این عدد را در تقسیم بر در نظر بگیریم، باقیمانده صفر ظاهر نمی‌شود. از طرفی هیچ کدام از این عدد باقیمانده یکسان ندارند زیرا اگر مثلاً و باقیمانده یکسان داشته باشند نتیجه می‌شود بر بخش‌پذیر است یعنی بر بخش‌پذیر است و چون و بخش‌پذیر است و چون و نسبت به هم اول می‌باشند نتیجه می‌شود بر بخش‌پذیر است ولی این عدد از کمتر است و چنین چیزی ممکن نیست.
پس مجموعه باقیمانده‌های در تقسیم بر با مجموعه برابر است، در نتیجه عددی مانند وجود دارد که در تقسیم بر باقیمانده برابر یک دارد یعنی بر بخش‌پذیر استو این یعنی یا
تعمیم اصل لانه کبوتری به این صورت است که: اگر کبوتر بخواهند در لانه بنشینند لااقل در یک لانه لااقل کبوتر خواهد نشست.
اعداد 1 تا 101 را به ترتیبی دلخواه در یک سطر نوشته‌ایم. نشان دهید می‌توان 11 تا از آنها را بدون برهم زدن ترتیبشان در نظر گرفت به طوری که ترتیب آنها یکنوا (صعودی یا نزولی) باشد.
حل حال کلیتری از این مثال به شرح زیر است که سعی می‌کنیم آن را اثبات کنیم. اگر و دنباله‌ای تایی از اعداد صحیح داشته باشیم در این صورت می‌توان زیر دنباله‌ای صعودی با طول یا زیر دنباله‌های نزولی با طول از آن پیدا کرد.
دنباله داده شده از عدد را در نظر بگیرید، فرض کنید ، نشان‌دهنده طول بزرگترین زیردنباله صعودی باشد که به امین عضو دنباله ختم شده است و نشان‌دهنده طول بزرگترین زیر دنباله نزولی با شروع از امین عضو دنباله باشد.
ادعا می‌کنیم اگر و دو عدد با این شرط که باشند آنگاه حتماً یکی از دو رابطه یا اتفاق می‌افتد. زیرا با یا فرض کنید. حال بر حسب این که عضو ام دنباله از عضو k ام دنباله بزرگتر باشد یا کوچکتر، داریم یا. در حالت نیز اتفاقات مشابهی رخ خواهد داد. بنابراین ادعای گفته شده ثابت می‌شود.
بنابراین تمام زوج‌های متفاوت‌اند. حال فرض کنید که هیچ‌کدام از دو مورد گفته شده در حکم مسأله رخ ندهد. در این صورت می‌تواند تنها مقادیر و می‌تواند تنها مقادیر را اختیار کند. بنابراین به تعدادجعبه مختلف داریم کهتا زوج در آنها قرار دارند ولی این تناقض است زیرا به این معنا است که دو تا از زوج‌های با هم برابرند (طبق اصل لانه کبوتری).
5 نقطه شبکه‌ای در صفحه انتخاب شده‌اند. نشان دهید می‌توان دو تا از این نقاط را در نظر گرفت به طوری که روی پاره‌خط واصل میان آن دو، نقطه شبکه‌ای دیگری موجود باشد.
توضیح. نقاط شبکه‌ای در صفحه نقاطی هستند که مختصات آنها صحیح می‌باشد.
حل در اینجا الگوی مختصات نقاط صفحه را از نظر زوجیت در نظر می‌گیریم، چهار حالت بیشتر نداریم که عبارتند از: (زوج و زوج) ، (فرد و زوج) ، (زوج و فرد) و (فرد و فرد) . حال چون 5 نقطه داریم طبق اصل لانه کبوتری حداقل دو تا از آنها مانند و زوجیت مؤلفه‌هایشان یکسان است. نقطه وسط AB به نام L را در نظر بگیرید، داریم
چون زوجیت و همچنین یکسان است نیز نقطه‌ای شبکه‌ای خواهد بود.
در دنباله 1 , 1 , 2 , 3 , 5 , 8 , 3 , … با شروع از مرتبه سوم هر جمله رقم یکسان مجموع دو جمله قبلی‌اش است. نشان دهید دنباله متناوب است و ماکزیمم طول ممکن برای دوره تناوب را بیابید.
حل هر دو جمله متوالی از دنباله را که در نظر بگیرید تمامی جملات قبل و بعد را به طور یکتا مشخص می‌کنند، بنابراین برای این که نشان دهیم دنباله متناوب است کافی است نشان دهیم یک زوج متوالی از جملات مانند تکرار می‌شود و در ضمن اولین زوج تکرار شونده (1 و 1) است. 101 جمله اول این دنباله را در نظر بگیرید آنها 100 زوج (2 , 3) , (1 , 2) , (1 , 1) و … را درست می‌کنند، چون زوج (0 , 0) تکرار نمی‌شوند (زیرا این مطلب باعث می‌شود که همه جملات دنباله بر 10 بخش‌پذیر باشند) تعداد حالت‌های ممکن برای یک زوج متوالی مانند برابریعنی 99 است و در نتیجه طبق اصل لانه کبوتری در بین 100 زوج اول حداقل یک زوج تکرار می‌شود و در نتیجه دوره تناوب حداکثر 99 است.
دنباله فیبوناتچی به شکل زیر تعریف می‌شود
نشان دهید به ازای هر عددی از دنباله فیبوناتچی یافت می‌شود که به تا صفر ختم می‌شود.
حل جمله به صفر ختم می‌شود اگر و تنها اگر بر بخش‌پذیر باشد یعنی بنابراین باید دنباله فیبوناتچی را به هنگ در نظر بگیریم و نشان دهیم که در بین باقیمانده‌ها ظاهر می‌شود. جمله اول دنباله فیبوناتچی یعنی را در نظر بگیرید. با استفاده از آنها می‌توان جفت را درست کرد که اگر قرار باشد هیچ ای بر بخش‌پذیر نباشد زوج ( 0 , 0) در میان این جفت‌ها به هنگ ظاهر نمی‌شود. اما صرف‌نظر از زوج ( 0 , 0) از لحاظ باقیمانده به هنگ ، امکان برای زوج ها وجود دارد. بنابراین یک جفت تکرار می‌شود. پس طول دوره تناوب دنباله به هنگحداکثر است. همانند مثال 8، اولین جفت کمه تکرار می‌شود (1 ، 1) است ، به شکل زیر
که طول دوره تناوب است. در نتیجه داریم یا یعنی بر بخش‌پذیر است.
فرض کنید عددی طبیعی باشد که نسبت به 2 و 5 اول است. نشان دهید به ازای هر می‌توان توانی از پیدا کرد که بهختم می‌شود.
حل عدد را در نظر بگیرید. اگر باقیمانده آنها را به هنگ بررسی کنیم درمی‌یابیم که باقیمانده هیچ کدام برابر صفر نیست زیرا و 10 نسبت به هم اول هستند. بنابراین باقیمانده‌های این عدد از مجموعه می‌باشند. طبق اصل لانه کبوتری دو تا از آنها مانند و به هنگ باقیمانده یکسانی دارند در نتیجه تفاضل آنها بر بخش‌پذیر است یعنی
و اما پس در نتیجه وجود دارد که حال داریم ، اگر کمی دقت کنید خواهید دید که این تساوی بدین معناست که بهختم می‌شود.
درون یک اتاق به مساحت 5 متر مربع، 9 قالیچه به مساحت یک مترمربع و با شکل دلخواه پهن کرده‌ایم. (ممکن است قالیچه‌ها مستطیل شکل نباشند) نشان دهید دو قالیچه وجود دارند که به اندازه حداقل مترمربع اشتراک دارند.
حل فرض کنید حکم درست نباشد یعنی اشتراک هر دو قالیچه کمتر از مترمربع مساحت داشته باشد. قالیچه‌ها را یکی‌یکی مطابق الگوی اولیه در اتاق می‌اندازیم. قالیچه اول مساحتی به اندازه یک متر مربع یا را می‌پوشاند، قالیچه دوم مساحتی به اندازه بزرگتر از را به مساحت قبلی اضافه می‌کند، … به همین ترتیب قالیچه آخر مساحتی به اندازه بزرگتر از را اضافه می‌کند، پس مجموع مساحتی که کل قالیچه‌ها می‌پوشانند بزرگتر از است، این بدان معنی است که مساحت اتاق از 5 بیشتر است که تناقض است.
از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..
وزارت آموزش و پرورش > سازمان پژوهش و برنامه‌ريزی آموزشی
شبکه ملی مدارس ایران رشد
قطعه الماس درون 
جعبه توزیع شوند آنگاه حداقل یک جعبه شامل بیش از یک الماس است.
الماس درون 
جعبه به دلخواه توزیع شوند. آنگاه حداقل یک جعبه شامل بیش از 
الماس است.
در صفحه مثلث
قرار دارد به طوری که از رئوس 
که 
و 
نسبت به هم اولند. حداکثر برابر
است.
متناهی باشد یا نامتناهی صفر داشته باشد.
است.
بر 
و 
در نظر می‌گیریم. اسم یک نفر را درون جعبه شماره نه قرار می‌دهیم اگر او در بین افراد حاضر در اتاق نه دوست داشته باشد. بنابراین 
همزمان نمی‌توانند پرباشند زیرا اگر شخصی باشد که با 
تعداد بازی‌هایی باشد که تا روز 
ام انجام داده است. در این صورت
و
برابرند. در نتیجه دو اندیس متمایز، 
وجود دارند به طوری که
. پس این شطرنج باز در طول روزهای
روی هم 21 بازی انجام داده است.
، 
ها بر 
وجود دارند که باقیمانده آنها به هنگ 
عدد از
انتخاب شده است، نشان دهید از میان اعداد انتخاب شده یکی بر دیگری بخش‌پذیر است.
باشند، آنها را به شکل
می‌نویسیم که 
عددی 
، 
قرار دارند و چون در این بازه 
و 
برابرند، بنابراین از دو عدد 
و 
یکی بر دیگری بخش‌پذیر است.
دو عدد نسبت به هم 
ای متعلق به 
وجود دارند به طوری که
را در نظر بگیرید، هیچ‌کدام از این اعداد طبق فرض بر 
بر 
است و چنین چیزی غیرممکن است. بنابراین اگر باقیمانده این 
عدد را در تقسیم بر 
و
باقیمانده یکسان داشته باشند نتیجه می‌شود
بر 
بر 
بر 
در تقسیم بر 
برابر است، در نتیجه عددی مانند 
وجود دارد که در تقسیم بر 
بر 
یا
کبوتر بخواهند در 
کبوتر خواهد نشست.
و دنباله‌ای 
یا زیر دنباله‌های نزولی با طول 
، نشان‌دهنده طول بزرگترین زیردنباله صعودی باشد که به 
امین عضو دنباله ختم شده است و 
نشان‌دهنده طول بزرگترین زیر دنباله 
و 
باشند آنگاه حتماً یکی از دو رابطه
یا 
اتفاق می‌افتد. زیرا با 
یا 
فرض کنید
. حال بر حسب این که عضو 
یا
. در حالت
متفاوت‌اند. حال فرض کنید که هیچ‌کدام از دو مورد گفته شده در حکم مسأله رخ ندهد. در این صورت
می‌تواند تنها مقادیر
و
می‌تواند تنها مقادیر
را اختیار کند. بنابراین به تعداد
جعبه مختلف داریم که
با هم برابرند (طبق اصل لانه کبوتری).
و
زوجیت مؤلفه‌هایشان یکسان است. نقطه وسط AB به نام L را در نظر بگیرید، داریم
و همچنین 
یکسان است 
نیز نقطه‌ای شبکه‌ای خواهد بود.
تکرار می‌شود و در ضمن اولین زوج تکرار شونده (1 و 1) است. 101 جمله اول این دنباله را در نظر بگیرید آنها 100 زوج (2 , 3) , (1 , 2) , (1 , 1) و … را درست می‌کنند، چون زوج (0 , 0) تکرار نمی‌شوند (زیرا این مطلب باعث می‌شود که همه جملات دنباله بر 10 بخش‌پذیر باشند) تعداد حالت‌های ممکن برای یک زوج متوالی مانند
برابر
یعنی 99 است و در نتیجه طبق اصل لانه کبوتری در بین 100 زوج اول حداقل یک زوج تکرار می‌شود و در نتیجه دوره تناوب حداکثر 99 است.
بخش‌پذیر باشد یعنی 
بنابراین باید دنباله فیبوناتچی را به هنگ 
جمله اول دنباله فیبوناتچی یعنی
را در نظر بگیرید. با استفاده از آنها می‌توان 
جفت 
را درست کرد که اگر قرار باشد هیچ 
ای بر 
امکان برای زوج ها وجود دارد. بنابراین یک جفت تکرار می‌شود. پس طول 
یا
یعنی 
بر 
ختم می‌شود.
را در نظر بگیرید. اگر باقیمانده آنها را به هنگ 
می‌باشند. طبق اصل لانه کبوتری دو تا از آنها مانند 
به هنگ 
و
پس 
در نتیجه 
وجود دارد که
حال داریم 
، اگر کمی دقت کنید خواهید دید که این تساوی بدین معناست که
به
ختم می‌شود.
مترمربع اشتراک دارند.
را می‌پوشاند، قالیچه دوم مساحتی به اندازه بزرگتر از 
را به مساحت قبلی اضافه می‌کند، … به همین ترتیب قالیچه آخر مساحتی به اندازه بزرگتر از 
است، این بدان معنی است که مساحت اتاق از 5 بیشتر است که تناقض است.