Güvercin yuvası ilkesi, matematikte ilk bakışta son derece açık görünen ama yakından incelendiğinde şaşırtıcı sonuçlara ulaşmamızı sağlayan fikirlerden biridir.
lke çok basit bir şey söyler. Güvercinleri yuvalara yerleştirmeye çalışırsanız ve güvercin sayısı yuva sayısından fazlaysa, en az bir yuvada birden fazla güvercin bulunur. Diğer bir deyişle, bir küme diğerinden daha büyükse, büyük kümedeki her nesneyi küçük kümedeki farklı bir nesneyle bire bir eşlemek mümkün değildir. Söylediği şey gerçekten bu kadar açıktır.
Güvercin Yuvası İlkesi Nedir?
Elbette ilke yalnızca güvercinler için geçerli değildir. Bir nesne kümesinin, alabileceği olası değerlerin sayısını aştığını bildiğiniz her durumda devreye girer. Örneğin standart bir iskambil destesinden çekilen beş kartın en az ikisinin aynı renkten olacağını bu ilke sayesinde bilirsiniz. Ya da müzikli sandalye oyununda bir sandalye kaldırıldığında, mutlaka bir kişinin ayakta kalacağını yine aynı mantıkla öngörebilirsiniz.
Güvercin yuvası ilkesi, ilk bakışta sezgisel olmayan bazı sonuçları da kolayca açıklar. Bunlardan biri şudur. Mesela Londra’da kafasındaki saç teli sayısı aynı olan en az iki kişi mutlaka vardır. Elbette Londra’ya gidip herkesi tek tek durdurarak saç sayısını hesaplamak mümkündür, ancak buna gerek yoktur. Güvercin yuvası ilkesi bu noktada devreye girer.
Güvercin Yuvası İlkesi Şaşırtıcı Sonuçlar Elde Etmemizi Sağlar
Londra’nın nüfusu yaklaşık dokuz milyondur. Ortalama bir insanın kafasında yaklaşık 100.000 saç teli bulunur. Bu durumda milyonlarca Londralı “güvercinleri”, 1 ile, örneğin, 200.000 arasındaki olası saç teli sayıları ise “yuvaları” temsil eder. Bu kadar çok insan varken, herkesin farklı bir saç sayısına sahip olması için yeterince seçenek yoktur. Birkaç uç örnek dışında, insanların büyük çoğunluğu bu aralıkta yer alır.
Bir kişinin tek bir saç teline, bir başkasının ikiye, bir başkasının üçe ve bu şekilde 200.000’e kadar artan sayılara sahip olduğunu varsaysak bile, yine de en az iki kişinin saç teli sayısının aynı olması kaçınılmazdır. Basit görünen bu ilke, tam da bu nedenle güçlü sonuçlar üretir.
Güvercin yuvası ilkesi, beklenmedik yerlerde karşımıza çıkar. Örneğin, herhangi bir toplantıda, odadaki insanlardan en az ikisinin, orada bulunan aynı sayıda kişiyi tanıdığından emin olabilirsiniz. Bu durumda güvercinler davete katılan kişiler, yuvalar ise her birinin odadaki tanıdık sayılarıdır.
Toplantıda 100 kişi olduğunu varsayalım; bu akıl yürütme kişi sayısı ne olursa olsun geçerlidir. Önce, odada hiç kimseyi tanımayan en az bir kişi olduğunu düşünelim. Eğer odada hiç kimseyi tanımayan bir kişi daha varsa, bu iki kişi aynı sayıda tanıdığı olan kişilerdir (0 kişi). Bu durumda aradığımız sonuca ulaşmış oluruz
Eğer kimseyi tanımayan yalnızca bir kişi varsa, geriye 99 kişi kalır. Bu 99 kişi artık 0 tanıdık sayısına sahip olamaz. O hâlde tanıdıkları kişi sayısı 1 ile 98 arasındadır. Ama burada bir sorun var. 99 kişi var, ama yalnızca 98 farklı sayı mümkün. Bu durumda en az iki kişi aynı sayıda insanı tanımak zorundadır.
Şimdi de hiç kimsenin yalnız olmadığı durumu ele alalım. Bu durumda her bir kişi odadaki en az 1, en fazla 99 kişiyi tanır. . Yani 100 kişi ve yalnızca 99 olası tanıdık sayısı vardır. Güvercin yuvası ilkesi burada da geçerlidir ve yine en az iki kişinin aynı sayıda arkadaşa sahip olması gerekir.
Güvercin Yuvası İlkesi Ne İşe Yarar?
Bu örnekler ilk bakışta “ilginç ama işe yaramaz” gibi görünür. Ancak güvercin yuvası ilkesi, oldukça pratik sonuçlar da üretir. Bunlardan biri, veri sıkıştırma algoritmalarının neden her zaman kayıpsız olamayacağını göstermesidir.
Bazı dosyaların boyutunu gerçekten küçültebilen bir sıkıştırma algoritmamız olduğunu varsayalım. Bu algoritmanın küçültebildiği en küçük dosyayı düşünelim; bundan daha küçük dosyaların boyutunu artık azaltamıyor olsun. Bu dosya sıkıştırıldığında, daha küçük ve belirli bir boyuta sahip bir dosya elde edilir.
Bu elde edilen boyuta zaten sahip olan başka dosyalar da vardır. Diyelim ki bu boyutta N tane farklı dosya var. Bu dosyaları sıkıştırma algoritmasından geçirdiğimizde, boyutları değişmez; çünkü algoritma onları daha fazla küçültemez.
Bu durumda elimizde ilginç bir tablo ortaya çıkar. Başlangıçta daha büyük olan bir dosya sıkıştırıldığında bu küçük boyuta iner. Aynı boyuta sahip olan N dosya da sıkıştırma sonrası yine bu boyutta kalır. Yani toplamda N + 1 farklı dosya, sıkıştırma sonucunda yalnızca N olası çıktıya karşılık gelir.
Burada güvercin yuvası ilkesi devreye girer. N + 1 farklı dosyayı yalnızca N farklı çıktı içine yerleştirmek zorunda kaldığınızda, en az iki dosyanın aynı sıkıştırılmış dosyaya dönüşmesi kaçınılmazdır.
Bu da şu anlama gelir: Sıkıştırılmış dosyayı geri açmaya çalıştığınızda, hangi dosyadan geldiğini kesin olarak bilemezsiniz. İşte bu belirsizlik, veri kaybının ta kendisidir. Bu nedenle en az bir dosyayı gerçekten küçültebilen her sıkıştırma algoritması, kaçınılmaz olarak bazı bilgileri kaybetmek zorundadır.
Sonuç Olarak
Güvercin yuvası ilkesinin daha genel bir biçimini bilgisayar bilimci Edsger Dijkstra formüle etmiştir. Dijkstra’nın ifadesine göre, herhangi bir kutudaki en yüksek güvercin sayısı, kutuların tamamındaki ortalama güvercin sayısından en az bu kadar olmak zorundadır.
Bunu somut bir örnekle düşünelim. Diyelim ki 100 güvercini 10 yuvaya yerleştiriyoruz. Bu durumda her yuvaya düşen ortalama güvercin sayısı 10’dur. Elbette bazı yuvalarda daha az, bazılarında daha çok güvercin olabilir. Ancak ilkenin söylediği şudur: En az bir yuvada mutlaka 10 ya da daha fazla güvercin bulunur. Çünkü eğer bütün yuvalarda 10’dan az güvercin olsaydı, toplam güvercin sayısı 100’e ulaşamazdı.
Basit görünen bu mantık, yalnızca sezgiyi doğrulamakla kalmaz; aynı zamanda ortalama değerlerin mutlaka bir yerde somut olarak karşılık bulduğunu da garanti eder.
Kaynaklar ve ileri okumalar:
- How a Problem About Pigeons Powers Complexity Theory. Yayınlanma tarihi: Kaynak iste: Quanta Magazine. Bağlantı: How a Problem About Pigeons Powers Complexity Theory
- Rittaud, B., Heeffer, A. The Pigeonhole Principle, Two Centuries Before Dirichlet. Math Intelligencer 36, 27–29 (2014). https://doi.org/10.1007/s00283-013-9389-1
- The World’s Simplest Theorem Shows That 8,000 People Globally. Have the Same Number of Hairs on Their Head. Yayınlanma tarihi: 20 mart 2023; bağlantı: The World’s Simplest Theorem Shows That 8,000 People Globally. Have the Same Number of Hairs on Their Head
Size Bir Mesajımız Var!
Matematiksel, matematiğe karşı duyulan önyargıyı azaltmak ve ilgiyi arttırmak amacıyla kurulmuş bir platformdur. Sitemizde, öncelikli olarak matematik ile ilgili yazılar yer almaktadır. Ancak bilimin bütünsel yapısı itibari ile diğer bilim dalları ile ilgili konular da ilerleyen yıllarda sitemize dahil edilmiştir. Bu sitenin tek kazancı sizlere göstermek zorunda kaldığımız reklamlardır. Yüksek okunurluk düzeyine sahip bir web sitesi barındırmak ne yazık ki günümüzde oldukça masraflıdır. Bu konuda bizi anlayacağınızı umuyoruz. Ayrıca yazımızı paylaşarak da büyümemize destek olabilirsiniz. Matematik ile kalalım, bilim ile kalalım.
Matematiksel
