Her birinde en az bir güvercin olacak şekilde, 3 güvercini 2 yuvaya nasıl yerleştirebilirsiniz? Tabi ki de birinde 2 birinde 1 güvercin olması gerekir çünkü her birinde en az bir güvercin olacak kaidesi var. Veya her birinde en az bir karpuz olacak şekilde 2 koltuğa 3 karpuzu nasıl dizebiliriz? Dizemeyiz, bir koltuğa iki karpuz sığmaz o yüzden üçüncü bir koltuğa ihtiyacımız var(!). İşte bu Güvercin Yuvası İlkesidir.
Ama bu kadar basit olduğuna bakmayın olimpiyatlarda, istatistikte, olasılıkta hiç tahmin edemeyeceğiniz ve karmaşık bir şekilde kullanılır
Peki, hikayesi ne?
Yine bir Gauss hikayesi. Hani şu ilk “n doğal sayının” toplam formülünü bulan adam. Hocası buna ceza vermiş demiş 100’e kadar olan tam sayıları toplamını söyle demiş o da bu formülü bulmuş. He o çocuk işte, bu çocuk hakkında böyle çok hikaye var. Bunun gibi de güvercin yuvası ilkesinin diğer adıyla Dirichlet İlkesinin çıkış noktası burası:
Bir gün, ileride çok dünya çapında çok ünlü bir matematikçi olacak olan küçük Gauss babasıyla ormanda gezerken babasına sormuş:
-Baba bu ormanda yaprak sayısı birbirine eşit iki ağacın olması için herhangi bir koşul söyleyebilir misin?
Baba Gauss da bir koşul düşünemez ve bunun üzerine yanıtı küçük Gauss vermiş:
-Eğer ormandaki ağaç sayısı, bu ormanda en çok yaprağı olan ağacın yaprak sayısından en az iki fazlaysa en az iki ağacın yaprak sayısı aynıdır.
Ne demek bu dediğinizi duyar gibiyim ifade biraz karışık gözüküyor fakat üstüne biraz düşünürsek aslında çok mantıklı olduğunu görürüz. Neden olduğunu anlayalım şimdi: En kötü ihtimali düşünelim. Her ağacın yaprak sayısının farklı olduğunu düşünelim yani.
Diyelim ki ormanda en çok yaprağı olan ağacın 100 yaprağı var. Ve ormanda bunun iki fazlası olan 102 tane ağaç var.1. Ağacın 0 tane, 2.nin 1 tane,…, 100.nün 99 tane, 101.nin 100 tane vardır. Geldik 102. ağaca. Bu ağacın yaprak sayısı 100’den fazla olamaz çünkü en çok yaprağı olan ağacın 100 yaprağı var demiştik o zaman yaprak sayısı 0 ile 100 arasında olmalıdır. Fakat zaten 0 ile 100 arasındaki yaprak sayısı dolduğundan mecburi olarak 102. ağacın yaprak sayısı önceki ağaçların birinin yaprak sayısıyla eşit olacaktır. İspatladık. Ayrıca bunu en kötü ihtimal olarak düşündük. Fakat iyimser ihtimallerle 10-20 tane ağacın da yapraklarının aynı olmasını sağlayabilirdik.
Bir başka bilgi de yukarıdaki hikaye ile ilgilidir. Bu hikayenin doğruluğunu veya yanlışlığını ispatlayan herhangi bir kanıt yok. Fakat öyle ya da böyle güvercin yuvası ilkesini anlatmak için çok iyi bir düşünce deneyi.
Güvercin yuvası ilkesi ile alakalı başka problemler
Güvercin Yuvası İlkesi veya teoremi sandığımız kadar basit değildir. Sezgisel gözükebilir ama bir o kadar soyuttur (Mesela daha ileri bir seviyesi olan Genel Güvercin İlkesi). Mesela:
İlk önce birkaç örnek yapalım:
1)İstanbul’da yaşayan iki kel olmayan insanın kafalarındaki saç miktarı aynıdır.
İnsan kafası birkaç yüz bin saça ev sahipliği yapabilir fakat en fazla 500.000 tane saça ev sahipliği yapabilir. Fakat İstanbul’da yaşayan 15 milyon insan vardır. 500.00 tane yuva, 15 milyon tane güvercin olarak düşünürsek önerme kanıtlanır.
2)Verilmiş üç ardışık tam sayıdan ikisinin toplamı mutlaka çifttir.
Çünkü Ardışık üç sayı ya Tek, Çift, Tek şeklinde ya da Çift, Tek, Çift şeklinde ilerler. İlk durumda tek+çift=tek ve tek+tek=çift olacağından birinci durum için ispatlanır, ikinci durum ise çift+tek=tek ve tek+tek=çift olur. İspatlamış olduk.
3)52’lik bir kart destesinden 5 tane kartı rastgele şekilde alırsanız en az iki kartın grubu (Karo, kalp, sinek vb. ve bunlardan 4 tane vardır) aynı olur. Çünkü en kötü ihtimali düşürsek 4 kart da farklı grup gelir. Fakat 5. karttaki grup zaten ilk 4 kardın herhangi birinde çıktığından en az iki kartın grubu aynı olur. İspatlandı
4)Biraz çitayı arttıralım: Bir okulda 510 çocuk var. Her çocuğun en az 10 bilyesi var. Ama hiçbir çocuğun 30’dan fazla bilgesi yok. En az 25 çocuğun aynı sayıda bilyesi olduğunu gösterin.
Çözüm:Bu problem belli daha karmaşık fakat gene de çözülebilir. Şimdi yine en kötü ihtimal, düşünelim ki böyle en az (İyimser bir şekilde düşünürsek “en az”‘ı bulamayız) kaç çocuğun aynı sayıda bilyesi olduğunu gösterelim. Bilye grupları kuralım. 1. Bilye grubunun 10, 2.nin 11, 3.nün 12,….., 21.nin 30 bilyesi var. Her birine 510/21’den 24 çocuk düşüyor fakat 6 tane çocuk artıyor. Yani herhangi bir gruba üye olmuyorlar Fakat bu çocukların da etkinliğe katılmaları gerek yoksa asosyal bir şekilde yetişirler. Çocuklar da mecburen bir gruba gireceklerinden en az 25 çocuğun bilye sayıları aynı olur.
Buradan sonrası artık meraklılara:
1)Kenar uzunluğu 2 birim olan eşkenar bir üçgenin içine herhangi ikisi arasındaki mesafe 1’den büyük olacak biçimde dört nokta yerleştirilebileceğini kanıtlayın.
2)a ve b aralarında asal iki pozitif doğal sayıysa “ax-by=1” eşitliğini sağlayan x ve y tamsayıları vardır, kanıtlayın.
Daha fazla örneği Sayma, Ali Nesin, Nesin Yayınevi, kitabından bulabilirsiniz.
Güvercin Yuvası İlkesine son bir bakış
Güvercin Yuvası İlkesi sadece matematikte problem çözme de kullanılmıyor. Mesela bilgisayar biliminde çok fazla küme ve öge kullanıldığı için bunların birbiriyle çelişip çelişmediğini tespit etmek için güvercin yuvası ilkesi kullanılıyor (fakat da güçlüsü). Aynı zaman da bilimde de kullanılmış oluyor. Mesela kuantum kuramı.
Son Söz
Bu yazımda güvercin yuvası ilkesini basit bir şekilde, örneklerle anlatmaya çalıştım. Umarım anlayabilmişsinizdir. Lütfen bir eksiğimiz, hatamız varsa bunu bize bildirin ki daha iyi bir blog yazarı olup amacımıza ulaşmamızda daha etkili olalım. Gitmeden şuraya Gauss’un bir sözünü koyalım: “Benim kadar sürekli ve yoğun bir şekilde matematik üzerinde düşünen herkes, benim buluşlarımı ortaya koyabilir.” Hoşça kalın.
Kaynakça:
1)Sayma Kombinasyon Hesapları, Ali Nesin, Nesin Yayınevi, 1. Bölüm.
2)https://mindyourdecisions.com/blog/2008/11/25/16-fun-applications-of-the-pigeonhole-principle/
