Güvercin Deliği İlkesi



 N ve k pozitif tamsayılar ve N > k olmak üzere 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.

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

Güvercin Deliği İlkesi Örneği:

SORU: “S={1,2,3,4,5,6,7,8,9} kümesinin 6 elamanlı her hangi bir altkümesinde toplamı 10 olan iki sayı vardır” ifadesini gösteriniz.
İspat:
Bu sorunun cevabında he zaman toplamı 10 olan en az bir ikili alınması gerektiğini göstermemiz gerekmektedir. Öncelikle S kümesinde toplamları 10 olan ikili grupları sıralayalım.
1+9=10; 2+8=10; 3+7=10; 4+6=10; ve geriye yalnızca “5” sayısı kalmaktadır. Sonuç olarak 10 toplamasını sağlayan 4 ikili ve ayrı kalan “5” ile 5 grup oluşur.
            Delik: Sayıların seçilebileceği grup sayısı burada 5’tir.

            Güvercin: Seçilecek elaman sayısı burada 6’dır.

Bu durumda 5 gruptan 6 sayı almamız gerekmektedir. Güvercin Deliği ilkesine göre en az bir gruptan iki elaman almamız gerekir. Bu da, her zaman toplamı 10 olan en az bir ikili seçilecek demektir.

Güvercin Deliği İlkesi Örneği:

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.

Kaynak:
1. http://tr.wikipedia.org/wiki/G%C3%BCvercin_deli%C4%9Fi_ilkesi
2. http://eng.harran.edu.tr/~nbesli/GDI.htm

Google Plus İle Paylaş
    Blogger Comment
    Facebook Comment

0 yorum:

Yorum Gönder



Faydalı Semboller: 
÷ × ½ √ ∞ = ≠ ≤ ≥ ≅ ≈ ~ ⇒ ±  ∈  Δ θ ∴ ∑ ∫ • π -¹ ² ³ ° ( ) [ ] a b ∠   ∟ ´ ´´     || Δ |x-y{ } ∩ ∪ ⊆ ⊂ ⊄ ⊇ ⊃ ⊅ ⊖ |A| Ø  1