Güvercin yuvası ilkesi

İlkenin adının esin kaynağı: Deliklerdeki Güvercinler. Burada n = 7 vem = 9, buradan en az iki güvercin deliği boş kalacağını söyleyebiliriz. (Eğer iki kuş bir deliği paylaşsalardı üç boş delik olacaktı.)

Matematikte Güvercin Yuvası İlkesi (en: Pigeonhole Principle)ya da çekmece ilkesi ya da Dirichlet kutu (çekmece) ilkesi, çok basit bir ilke olmasına karşın bu ilkeyi kullanarak ispatlanabilecek ilişkiler çok ilginç olabilir. Bu ilke tam olarak şunu der: N ve k pozitif tamsayılar ve N > k olmak üzere N nesne k kutuya yerleştirildiğinde öyle bir kutu vardır ki o kutuda birden çok nesne bulunmak zorundadır. Bu doğru olmasaydı, yani her kutuda en fazla birer nesne olsaydı, k kutuda en fazla k nesne olabilecekti.

n ve m gibi iki doğal sayı için n > m durumunda, eğer n parça m güvercin deliğine koyulacaksa bir güvercin deliği birden fazla parça içermek zorundadır. Diğer bir söylem; m deliğe bir deliğe bir güvercin düşecek şekilde en fazla m güvercin yerleştirilebilir, bir tane daha yerleştirilmesi bir deliğin tekrar kullanılması ile olur.

Örnekler

Güvercin Deliği İlkesi sezgisel görülebilir, bu beklenmeyen durumları göstermek için kullanılabilir.Örnek olarak, Londra'da aynı saç teline sahip en azından iki insan olduğunu ispatlamak. Gösterim: Kafada ortalama 150000 saç teli bulunur. Bu kimsenin kafasında 1000000 adet saç teli olamayacağını gösterir (m = 1 milyon delik). Londra'da 1000000'dan fazla insan vardır (n>1 milyon cisim). Eğer her bir güvercin deliğine, kafadaki farklı sayıdaki saç sayısı yerleştirilecek dersek, en azından iki kişinin kafasında aynı sayıda saç teli olduğunu görürüz.

Diğer bir örnek: Bir kutuda 10 siyah 12 mavi çorap olduğunu ve bir çift çoraba ihtiyaç duyulduğunu varsayalım.Her seferinde yalnızca bir tane ve bakmadan çoraplar alınıyorsa, kaç çorap kutudan alınmalıdır? Doğru cevap üçtür. En az bir çift çoraba sahip olmak için (m=2 delik, her delik bir renk), bir deliği bir renk için kullanarak 3 çorap yerleştirilirse (n=3) başarı sağlanır.

Güvercin Deliği İlkesinin Genelleştirilmesi

Bu prensibin genelleştirilmiş hali; eğer n ayrık obje m kaba yerleştirilecekse en az bir kap $\lceil n/m\rceil$ 'den az olmayacak şekilde obje barındırır şeklindedir, $\lceil x\rceil$ tavan fonksiyonudur (en: ceiling function), x'den büyük xe en yakın veya xin kendisi olan tam sayıya eşitler. Olasılıksal genelleştirilmesi; eğer n güvercin rastgele m adet güvercin deliğine $1/m$ olasılıkla koyulursa en az bir güvercin deliği

1-{\frac {m!}{(m-n)!\;m^{n}}}=1-{\frac {(m)_{n}}{m^{n}}}\!

olasılıkla birden fazla güvercin tutacaktır, (m)_n, permutasyon(en:Falling Factorial)'dur. n = 0 ve n = 1 (ve m > 0) için, olasılık sıfırdır, başka bir deyişle, eğer tek bir güvercin varsa bir çekişme olmayacaktır. n > m (güvercin deliklerinden daha çok güvercin) olduğunda çekişme olur, bu durumda bilinen güvercin deliği prensibi ile uyuşur. Ama güvercin sayıları güvercin deliği sayısını aşmazsa (n ≤ m)güvercinleri güvercin deliklerine rastgele yerleştirmenin doğasından genelde bir çakışma meydana gelir. Örneğin, eğer iki güvercin rastgele 4 güvercin deliğine yerleştirilirse, 25% ihtimalle bir güvercin deliği birden fazla güvercin tutar; 5 güvercin ve 10 delik için olasılık 69.76% olur; ve 10 güvercin ve 20 delik için yaklaşık 93.45% olur. Bu problem doğumgünü paradoksu(en: Birthday Paradox)‘nda daha büyük bir uzunlukta olur.

Kaynakça

Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. 4th edn. 1998. ISBN 0-201-19912-2. pp. 244–248.
Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "Pigeonhole principle"3 Ekim 1999 tarihinde Wayback Machine sitesinde arşivlendi.. In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics17 Ocak 1999 tarihinde Wayback Machine sitesinde arşivlendi.. Electronic document, retrieved November 11, 2006.
en: Pigeonhole Principle

Dış bağlantılar

"The strange case of The Pigeon-hole Principle" 5 Temmuz 2008 tarihinde Wayback Machine sitesinde arşivlendi.; Edsger Dijkstra investigates interpretations and reformulations of the principle

Ayrıca bakınız