[Matematik] Güvercin DeliÄŸi Ä°lkesi – Çekmece Ä°lkesi – Pigeonhole Principle | Güvercin Yuvası Prensibi – Deliklerdeki Güvercinler – Güvercin D..

Güvercin Deliği İlkesi

Matematikte Güvercin Deliği İ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 zorudadı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.

İ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ı.)

Örnekler

Güvercin Deliği İlkesi sezgisel görülebilir, bu beklenmeyen durumları göstermek için kullanılabilir. Örnek olarak, Lonra’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 ‘den az olmayacak ÅŸekilde obje barındırır ÅŸeklindedir, tavan fonksiyonudur (en: ceiling function), x’den büyük x’e en yakın veya x’in 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 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(])‘nda daha büyük bir uzunlukta olur.

Bakınız, Carl Friedrich Gauss

Çekmece ya da Güvercin Yuvası İlkesi

Boğaziçi Üniversitesi Matematik Bölümü Öğretim Üyesi.

Kaynak: Kadim Dostlar ™ Forum

Bu içerik 26.03.2009 tarihinde Hale tarafından, Matematik ve Geometri Konu Anlatımları bölümünde paylaşılmıştır ve 902 kez okunmuştur. Bu içeriğin devamında incelemek isteyebileceğiniz 1 adet mesaj daha bulunmaktadır.

[Matematik] Güvercin Deliği İlkesi - Çekmece İlkesi - Pigeonhole Principle | Güvercin Yuvası Prensibi - Deliklerdeki Güvercinler - Güvercin Deliği İlkesinin Genelleştirilmesi - Örnekler orjinal içeriğine ulaşmak için tıklayın ...