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

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

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

اعتقاد هست که نخستین بیان این قضیه به وسیلهٔ دیریکله در سال ۱۸۳۴ تحت نام Schubfachprinzip («اصل کشو» یا «اصل قفسه») مطرح شده‌است. نیز در ایتالیایی، نام اصلی «principio dei cassetti» هم‌چنان استفاده می‌شود؛ در بعضی زبان‌های دیگر (برای مثال، روسی) این اصل با نام اصل دیریکله شناخته می‌شود (نباید با حداقل اصول توابع هارمونیک که نام مشابهی دارد اشتباه گرفته شود).

تجسمی برای نام اصل: کبوترها در لانه‌ها. در این‌جا n = 7 و m = 9 بنابراین می‌توانیم نتیجه بگیریم که حداقل دو لانه کبوتر خالی وجود دارد. (که اگر دقیقاً دو کبوتر در یک لانه قرار گرفته باشند، سه خانهٔ خالی وجود دارد.)