اصل لانه کبوتری یا اصل حجره ها

اصل لانه کبوتری، یا اصل حجره های دیریکله ، بیان می‌کند که اگر دو عدد طبیعی n و m را با خاصیت   n>m داشته باشیم، اگر n شیء در m لانه کبوتر قرار گیرد، آن‌گاه حداقل یک لانه کبوتر (یا قفسه) دارای بیش از یک شیء خواهد بود. 

به طور رسمی، این قضیه بیان می‌کند که وجود ندارد تابعی یک به یک روی مجموعه‌های متناهی که هم‌دامنهٔ (برد) آن کوچکتر از دامنهٔ‌اش باشد.

بیانی دیگر از این اصل به این صورت است که اگر در m لانه حداکثر m شیء آن هم با شرط در هر لانه یک شیء، قرار گرفته است؛ اضافه کردن یک شیء دیگر ما را مجبور می‌کند که از یکی از لانه‌ها بار دیگر استفاده کنیم (با این شرط که m متناهی باشد).

 

 

اصل لانه کبوتری مثالی از اصل شمارش است که برای بسیاری از مسائل شهودی شامل آن ‌هایی که با مجموعه‌های متناهی درگیر می‌شوند و نمی‌توانند با ویژگی‌های یک تابع یک به یک مطابقت داده شوند، اجرا می‌شود.

اگر N+1 یا تعدادی بیشتر کبوتر را در  N لانه  قرار دهیم، آن وقت لانه ای باید شامل دو یا تعدادی بیشتر کبوتر باشد. به ابهام موجود در عبارت " لانه ای باید شامل.." و "دو یا تعدادی بیشتر..." توجه کنید. این موضوع در حقیقت وجه تمایز اصل لانه کبوتری است که بعضی وقتها به کمک آنها می توانیم به نتیجه گیری هایی کاملا دور از انتظار برسیم، حتی مواقعی که به نظر می رسد اطلاعاتمان کافی نباشد.

اثبات این اصل کاملا ساده است و در آن فقط از شمارش معمولی کبوترها در لانه هایشان استفاده می شود. فرض کنید در هیچ یک از لانه ها بیش از یک کبوتر نباشد. در این صورت روی هم بیش از N کبوتر وجود ندارد و این نتیجه با این فرض که تعداد کبوتر ها N +1 است تناقض دارد بنابراین اصل لانه کبوتری با استفاده از روش اثبات با رسیدن به تناقض، ثابت می شود.

مثال: فرض کنید 4کبوتر و 3 لانه داریم و میخواهیم کبوتر ها را در لانه ها قرار دهیم و هر لانه هم به اندازه همه آنها جای دارد .بهترین حالت این است که سعی کنیم همه کبوتر ها را در لانه ها پخش کنیم در این صورت سه کبوتر را قرار می دهیم و کبوتر چهارم مجبور است در یکی از لانه ها که قبلا پر شده قرار بگیرد پس در یکی از لانه ها حداقل دو کبوتر قرار می گیرد.

تذکر: در این گونه مسائل برای به دست آوردن k می توان m را برn تقسیم کرد اگر باقی مانده برابر صفر بود ، خارج قسمت همان k مناسب است ، اگر باقی مانده مخالف صفر بود ، k برابر خارج قسمت به اضافه یک خواهد بود.

مثال: اگر 210 عدد طبیعی دلخواه و متمایز را بر 20 تقسیم کنیم ، حداقل چند عدد دارای باقی مانده یکسانی بر 20 هستند؟

پاسخ: طبق اصل لانه کبوتر اگر 210 عدد طبیعی انتخابی را 210 کبوتر و 20 باقی مانده ممکن در تقسیم بر 20 را تعداد لانه ها بگیریم چون 20×10<210  حداقل در یکی از لانه ها دست کم 10+1=11  کبوتر وجود خواهد داشت یا :

مثال: شخصی برای  مهمانی خود 39 نفر را دعوت کرده است. حداقل چند نفر در این مهمانی هستند که روز تولد آنها یک روز هفته باشد:

حل: مهمان ها را کبوتر و روز های هفته را لانه درنظر می گیریم .پس با داشتن 39 کبوتر و 7 لانه داریم:

پس حداقل 6 نفر دارای روز(منظور روز های هفته است و مهم نیست چه روزی) تولد یکسان هستند.

مثال :

یک میلیون درخت کاج در جنگلی روئیده است. می دانیم روی هیچ درخت کاجی بیش از 600000 برگ وجود ندارد. ثابت کنید در این جنگل دو درخت کاج تعداد برگهایشان یکی است.

پاسخ:

یک میلیون کبوتر (درخت کاج) وجود دارد و متاسفانه 600001 لانه که از 0 تا 600000 شماره گذاری شده اند. هر کبوتر (درخت کاج) را در لانه ای قرار می دهیم که شماره اش تعداد برگهای آن درخت است. چون کبوترها بیشتر از لانه ها هستند در لانه ای باید دست کم دو کبوتر (درخت کاج) باشند. اگر در هیچ لانه ای بیش از یکی نباشد، آن وقت بیش از 600001 کبوتر وجود ندارد. اما اینکه دو کبوتر در یک لانه باشد، معنایش این است که تعداد برگهایشان یکی است.

مثال:

اگر s زیر مجموعه اى ٧ عضوى از   { 1,2, 3,…,21} باشد . ثابت كنید دو زیر مجموعه ى متمایز از S مانند B وA موچود است . به طورى كه مجموع اعضاى A با مجموع اعضاى B  برابر است.

پاسخ: حداقل مجموع اعضاى زیرمجموعه هاى مجموعه ى s فوق صفر و حداکثر آن 12+20+…+15=126  است 

یعنى مجموع اعضاى زیر مجموعه هاى S یکی از 127 حالت  { 0,1,2,…,126}  است. چون  s  یک مجموعه 7 عضوی می باشد 2⁷=128   زیر مجموعه دارد که آنها را به عنوان 128   کبوتر و { 0,1,2,..,126}  را به عنوان 127 لانه در نظر می گیریم. 

پس طبق اصل لانه كبوترى یا اصل حجره ها، مجموع اعضاى دوتا از این زیر مجموعه ها باید یكى باشد.

تهیه: مرکز یادگیری سایت تبیان