Güvercin Yuvası İlkesi (veya Dirichlet Prensibi), sonlu sayıda nesne ile onları barındıran sonlu sayıda kutu arasındaki ilişkiyi inceleyen basit ama güçlü bir matematiksel mantık prensibidir.
Eğer n tane güvercinimiz ve bu güvercinleri koyabileceğimiz m tane yuva (kutu) varsa ve n > m ise, yani güvercin sayısı yuva sayısından fazlaysa, en az bir yuvaya kesinlikle birden fazla güvercin konmak zorundadır.
Bu durumu genel bir kural olarak şöyle ifade edebiliriz:
Daha karmaşık durumlar için ilkeyi genelleştirebiliriz. Eğer N tane nesnemiz ve k tane kutumuz varsa, en az bir kutuda en az:
\(\lceil \frac{N}{k} \rceil\)
tane nesne bulunur. Burada \(\lceil x \rceil\), x sayısının tavana yuvarlanmış halidir (x'ten büyük veya eşit en küçük tam sayı).
Güvercin Yuvası İlkesi, karmaşık gibi görünen birçok problemin çözümünde, ispatında ve mantık yürütmede şaşırtıcı derecede etkili ve pratik bir araçtır. Matematik, bilgisayar bilimi, olasılık ve istatistik gibi alanlarda sıkça kullanılır. Bir şeyin kesinlikle var olduğunu ispatlamak için ideal bir yöntemdir.
Soru 1: Bir sınıfta 25 öğrenci vardır. Bu öğrencilerden en az kaç tanesi aynı ay içinde doğmuştur?
a) 2 b) 3 c) 4 d) 5 e) 6
Cevap: b) 3
Çözüm: Güvercin yuvası ilkesine göre: 25 öğrenci (güvercin) ve 12 ay (yuva) vardır. \( \lceil \frac{25}{12} \rceil = \lceil 2,083... \rceil = 3 \). Yani en az 3 öğrenci aynı ay içinde doğmuştur.
Soru 2: Bir kutuda 5 farklı renkte (kırmızı, mavi, yeşil, sarı, siyah) toplam 41 tane kalem vardır. Bu kutudan en az kaç kalem alınırsa, kesinlikle aynı renkten 9 kalem elde edilmiş olur?
a) 36 b) 37 c) 40 d) 41 e) 45
Cevap: d) 41
Çözüm: En kötü ihtimalle her renkten 8'er kalem alınabilir. 5 renk x 8 kalem = 40 kalem. Bir sonraki alınan kalem (41.) kesinlikle bir renkten 9. kalem olacaktır.
Soru 3: 1'den 50'ye kadar (1 ve 50 dahil) numaralandırılmış toplar bir torbaya atılıyor. Bu torbadan en az kaç top çekilirse, çekilen topların numaraları toplamının kesinlikle 55'e tam bölüneceğinden emin olunur? Soru 4: Bir veri tabanında her biri 1000 sayfadan oluşan 15 ciltlik bir ansiklopedi vardır. Her sayfada ortalama 300 kelime bulunmaktadır. Bu ansiklopedideki tüm kelimeleri indekslemek isteyen biri, en az kaç kelimenin aynı sayfada geçtiğini garantilemek için güvercin yuvası ilkesini kullanmak isterse hangi sonuca ulaşır?
a) 54 b) 55 c) 56 d) 60 e) 61
Cevap: b) 55
Çözüm: 55'e bölümden kalanlar 0'dan 54'e kadar 55 farklı durumdur (yuva). En kötü ihtimalle her kalandan birer sayı seçersek 55 top seçilir. 56. top çekildiğinde, bu toplamın 55'e bölümünden kalan, öncekilerden biriyle aynı olacak ve bu iki grubun farkı 55'e tam bölünecektir. Ancak soru toplamın kendisinin 55'e bölünmesini istiyor. Bu nedenle, 55 farklı kalanı temsil eden 55 top çekildiğinde, bu 55 topun toplamının 55'e bölümü zaten 0 olabilir veya olmayabilir. Eğer olmazsa, 56. top çekildiğinde kesinlikle bir önceki kalanlardan biri tekrarlanacak ve bu iki durumun toplamları arasındaki fark 55'in katı olacaktır. Fakat soru toplamın kendisinin bölünmesini sorduğu için, 55 farklı kalanı garanti altına alan 55 top çekmek yeterlidir. Çünkü bu 55 topun toplamı 55'e bölünüyorsa istenen sağlanır. Bölünmüyorsa, bu toplamın 55'e bölümünden kalan \( r \) (0
a) En az 2 kelime aynı sayf
