Güvercin Yuvası İlkesi

Güvercin Yuvası İlkesi (Çekmece Prensibi): Eğer n tane güvercin m tane yuvaya yerleştiriliyorsa ve güvercin sayısı (n) yuva sayısından (m) fazlaysa, en az bir yuvada birden fazla güvercin olmak zorundadır.

Temel Uygulama

Dışarıyla bağlantısı olmayan bir kuş araştırma merkezinde 4 güvercin yuvası ve 5 güvercin varsa, her güvercin bir yuvayı kullanmak zorunda olduğundan (5>4), en az bir yuvada birden fazla (en az 2) güvercin bulunmak zorundadır.

Genel formül: n güvercin m yuvaya yerleştirildiğinde, en az bir yuvada bulunması kesin olan en az güvercin sayısı ⌈n/m⌉ (n/m'nin tam sayıya yukarı yuvarlanmış hâli) formülüyle bulunur. Örneğin 3 yuva, 4 güvercin varsa: 4/3=1,33..., yukarı yuvarlanınca 2; yani en az bir yuvada en az 2 güvercin vardır. 6 yuva, 8 güvercin varsa: 8/6=1,33..., yukarı yuvarlanınca 2. 7 yuva, 10 güvercin varsa: 10/7=1,43..., yukarı yuvarlanınca 2. Yuva sayısının tam katlarından daha fazla güvercin olduğunda (örneğin 2 yuva, 5 güvercin: 5/2=2,5, yukarı yuvarlanınca 3) en az bir yuvada en az 3 güvercin bulunmak zorundadır.

Uygulama Örneği: Aynı Gün Doğma Problemi

Bir yılda en fazla 366 farklı gün (artık yıl dahil) olduğundan, bir gruptaki kişi sayısı 366'yı aştığında güvercin yuvası ilkesi gereği en az iki kişi aynı gün doğmuş olmalıdır. Örneğin 400 kişilik bir grupta, 400 kişi (güvercin) 366 güne (yuva) dağıtıldığında 400/366≈1,09, yukarı yuvarlanınca en az 2 kişi aynı gün doğmuş olmalıdır.

Uygulama Örneği: Geometrik Uzaklık Problemi

Bir kenar uzunluğu 4 birim olan karenin iç bölgesinden alınan 5 noktadan aralarındaki uzaklık kesinlikle 3 birimden küçük olan iki nokta bulunduğunu göstermek için: kare, kenar uzunluğu 2 birim olan 4 eş küçük kareye bölünür. Güvercin yuvası ilkesi gereği (5 nokta, 4 kare), en az bir küçük kare içinde en az 2 nokta bulunmalıdır. Bu küçük karenin köşegen uzunluğu 2√2 birimdir; 2√2≈2,83<3 olduğundan, aynı küçük kare içindeki iki nokta arasındaki uzaklık her zaman 3 birimden küçük olmak zorundadır — bu da istenen sonucu kanıtlar.

Güvercin Yuvası İlkesinin Çözüm Stratejisi

Bu tür problemlerde genel yaklaşım şöyledir: 1. "Güvercinler" (dağıtılacak nesneler/kişiler) ve "yuvalar" (kategoriler/bölgeler) belirlenir. 2. Güvercin sayısının yuva sayısından fazla olduğu doğrulanır (veya bir bölme/gruplama yapılarak bu duruma indirgenir, geometrik problemde olduğu gibi). 3. n/m oranı hesaplanıp yukarı yuvarlanarak, en az bir yuvada kesin olarak bulunması gereken en az eleman sayısı bulunur.

Özet

• Güvercin yuvası ilkesi, n tane nesne m tane kategoriye dağıtıldığında (n>m), en az bir kategoride birden fazla nesne bulunacağını garanti eden basit ama güçlü bir sayma prensibidir; en az eleman sayısı ⌈n/m⌉ formülüyle hesaplanır.
• Bu ilke, doğum günü çakışması gibi olasılıksal görünen ama aslında kesin (garanti edilen) sonuçlar içeren problemleri çözmede kullanılır — 366'dan fazla kişilik bir grupta mutlaka aynı gün doğan en az iki kişi vardır.
• Geometrik problemlerde de uygulanabilir: bir bölgeyi alt bölgelere ayırıp güvercin yuvası ilkesini uygulayarak, belirli sayıda noktanın en az ikisinin aynı alt bölgede olacağı (ve dolayısıyla aralarındaki uzaklığın belirli bir sınırı aşamayacağı) kanıtlanabilir.