güvercin yuvası prensibi

• + kürsünün saygıdeğer üyeleri. üç senedir üzerinde çalıştığım büyük teoremimi açıklıyorum..
  - buyrun..
  (tebeşiri alır, tahtaya komplike denklemler yazması beklenmektedir, ancak o sadece iki güvercin bir yuva çizer)
  + varsayalım ki n adet yuvamız var..
  - evet
  + (n+1) adet de güvercinimiz..
  - hmm?
  + şimdi bunlar girmeye çalışsa ya giremezler ya da en azından bi yuvada iki güvercin olur..
  - evet.. ee?
  + ..
  - ..
  + bu kadar..
  - ..
  + ..
  - .. lan üç senedir yatıyon bi bok yapmadan di mi hayvanoğluhayvan... çkşarı...
  + of ya
• meşhur hikaye şöyledir:
  
  gauss 6 yaşındayken babası ile çok büyük bir ormana gezmeye gitmiş. bunlar ormanda yürürken gauss babasına sormuş : "bu ormandaki ağaç sayısı mı daha çok, bi ağaçta olabilecek maksimum yaprak sayısı mı?" babası da "ağaç sayısı" demiş. küçük gauss da babasına demiş ki : "o zaman bu ormanda birbiriyle aynı sayıda yaprağı olan iki ağaç vardır". babası da "peki" demiş tabi..
  
  bugün biz bu prensibi, güvercin yuvası prensibi olarak biliyoruz, peki uygulamasına güzel bir örnek verelim:
  
  hiç sıkıştırılamayacak dosyalar vardır. neden mi: n bit boyunda olabilecek 2^n tane değişik dosya vardır, ama n bitten kısa olan 2^n-1, tane değişik dosya vardır.
• konuyla ilgili bir ornek vermek gerekirse
  
  100 kisilik bir grubun 50 evli ciftten olustugunu varsayalim. bu grup icinden en az kac kisi secmeliyiz ki secilenlerden en az ikisi evli bir cift olsun?
  
  eger 50 kisi secersek en kotu ihtimalle hepsi erkek veya kiz olabilir. isimize yaramadi. hala evli bir cifti bulmus degiliz.
  
  ancak, 51 kisi secersek en kotu ihtimalle 50 kadin ve 1 erkek ya da 50 erkek ve 1 kadin secmis oluruz. bu sayede, en kotu ihtimalle en az ikisi birbiriyle evli olan bir cift secmis oluruz.
• ilk duyulduğunda "ee yani?" dedirtecek basitlikte olsa da, çok beklenmedik problemleri çok beklenmedik biçimde basitleştirebildiği için sevilir ve sayılır.
  
  ----- örnek -----
  
  iki boyutlu düzlemi sadece iki renk kullanarak (mesela kırmızı-mavi) boyadığımızı varsayalım. nasıl boyayacağımıza dair hiçbir kural veya kısıtlama yok: düzlemin ortasına bir çizgi çekip bir tarafını mavi bir tarafını kırmızı boyayabiliriz, yahut düzlemi satranç tahtası gibi kırmızı mavi karelerle doldurabiliriz, yahut en az bir koordinatı rasyonel olan noktaları mavi, diğer noktaları kırmızı boyayabiliriz, artık canımız nasıl isterse. düzlemdeki her bir nokta ya kırmızı ya mavi boyandığı sürece, nasıl boyadığımızın hiçbir önemi yok.
  
  ben iddia ediyorum ki: her bir d>0 sayısı için, aralarındaki mesafe tam olarak d'ye eşit olan aynı renkten iki nokta vardır.
  
  şimdi bu iddia epey kuvvetli bir iddia. düzlem ne kadar karmaşık veya basit boyanmış olursa olsun, ve seçilen d mesafesi ne kadar küçük veya büyük olursa olsun, birbirinden d uzaklıkta duran aynı renkten iki nokta bulunabileceğini söylüyor. bu iddianın neden doğru olduğu, nasıl kanıtlanabileceği hiç bariz değil. oturup kanıtlamaya çalıştığınızda (ki bi beş dakika çalışın bence), eğer doğru yaklaşımı bilmiyorsanız, içinden çıkılmaz karmaşıklıkta bir problem gibi gelebilir.
  
  lakin güvercin yuvası prensibi bize inanılmaz basitlikte bir kanıt sunuyor: düzlemin herhangi bir yerine kenarları d uzunluğunda bir eşkenar üçgen çizilir. üçgenin üç köşesi var, her bir köşe ya kırmızı ya mavi boyanmış, ve köşeler birbirine d uzaklıkta. elimizde üç köşe ve iki renk olduğuna göre, en az iki köşe aynı renkte olmak zorunda. işte birbirine d uzaklıkta duran aynı renkten iki nokta bulduk.
  
  ----- örnek -----
  
  velhasıl prensibi kıymetli kılan şey, çok şaşırtıcı bir şey söylemesi değil, cok şaşırtıcı uygulamaları olması.
• türkçesi "garip kuşun yuvasını allah yapar"
• konuyla ilgili atasozu icin
  (bkz: bir koltuğa iki karpuz sığmaz)
  
  ayrica
  diger dusunce deneyleri icin
  (bkz: #92649934)
• sinyal derslerinde kullanilan fourier serisinin ıraksak olup olmadığını öğrenmek icin kullanabileceğiniz özel koşullara verilen isimlere de dirichlet koşulları adı verilir.
  
  bu koşullar kesinlikle integre edilebilir fonksiyonlardan oluşur..
• genelde çoğu amerikan kitabında çekmece örneği ile açıklanır. bir çekmecede kırmızı, mavi, yeşil renklerde çoraplar vardır. en az kaç çorap çekerek kesinlikle aynı renk 1 çift çoraba sahip olursunuz? temel prensip abs(a)>abs(b) olduğundan bakmadan 4 çorap alırsanız bunlardan en az 2'si mutlaka aynı renkte olacaktır. en temel örneklerinden biri de budur.
  
  şurada da matematik dünyası dergisinde yayımlanmış olan bir haluk oral makalesi bulunuyor :
  
  http://www.matematikdunyasi.org/…guvercinyuvasi.pdf
  
  ali nesin'in matematik ve doğa isimli kitabında da benzer bir popüler matematik yazısı bulunmakta. matematikle sihirbazlığın ortak noktası.
• bir gün içerisinde new york da basında aynı sayıda saç olan en az 2 kişi vardır. işte size pigeon hole principle. (bkz: güvercin yuvası prensibi)
• konu ile alakalı örnek bir soru :
  
  bir bilgisayar programı birbirinden farklı 3 rakamdan oluşan kodları rastgele ekrana basmaktadır. ( örnek : 315, 291, 012, 102, ... ). bu programın en az 6 kez aynı kodu ekrana basması için en çok kaç kod basmış olması gerekmektedir?
  
  (tübitak 9. ulusal bilgisayar olimpiyadı, birinci aşama sınavı)
  
  edit : soruda abs(a)>abs(b) kuralı değil "generalized pigeonhole principle" kullanılıyor.