Güvercin Yuvası Prensibi

Birçok problemin çözümünde kullanılan güvercin yuvası prensibi (Çekmece gözü prensibi, Kutu ilkesi, Drichlet İlkesi) ifade olarak çok basittir ancak bir çok sorunun çözümünde çok önemli rol oynamaktadır. Güvercin Yuvası prensibi genel olarak üç farklı şekilde ifade edilir.

  1.  n+1  top n  farklı kutuya dağıtıldığında en az bir kutuda 1 den fazla top bulunur.
  2.  n  tane güvercin k  tane yuvaya nasıl konulursa konulsun en az bir yuvadaki güvercin sayısı \frac{n}{k} dan az değildir.
  3.  mn+1 adet bilye n  farklı kutuya dağıtıldığında en az bir kutuda m den fazla (en az m+1  tane) bilye bulunur.

İspat.  mn+1  adet bilyeyi n  kutuya dağıtalım ve her kutuda en fazla m tane bilye bulunsun. Buna göre toplam bilye sayısı en fazla mn  olur oysa toplam mn+1 adet bilye vardı. Demek ki en az bir kutuda  m den fazla bilye vardır.

Bu temel ilke ilk defa Drichlet (1805-1859) tarafından 1834 yılında “shelf principle” adı ile kullanılmıştır. Bir problemde güvercin yuvası ilkesinin kullanılacağını sezmek oldukça kolaydır. Ancak problemi bu ilkeye uyarlayıp çözüme gitmek zordur.
Örnek 1. 15 kişilik bir insan grubu içinde aynı cinsiyete ait en az 8 kişi vardır.

Örnek 2. 37 kişi arasında aynı ayda doğan en az 4 kişi vardır.

Örnek 3. Bir gruptaki 3655 kişi arasında en az 11 kişinin doğum günleri aynıdır.

Örnek 4. 5 kişilik bir grupta aynı sayıda arkadaşı olan en az 2 kişinin olduğunu gösteriniz.

Çözüm. 5 adet kutu alalım ve kutuları sırası ile 0,1,2,3,4 ile numaralandıralım. Eğer bir kişinin hiç arkadaşı yoksa onu 0 numaralı kutuya, eğer bir kişinin 1 arkadaşı varsa onu 1 numaralı kutuya vb. koyalım. Bu şekilde yerleştirdiğimizde 5. kişi önceden doldurulan bir kutuya konmak zorunda olacaktır.

Örnek 5. 1,2,3,4,…,100 sayılarından en az iki tanesinin ortak böleninin kesinlikle 1 den büyük olması için en az kaç sayı alınmalıdır?

Çözüm. Bu yüz adet sayı arasında 26 adet asal sayı vardır. Bu asal sayıların obebleri 1 dir. Eğer bu 26 sayı ile birlikte 1 i ve ek olarak 1 tane daha sayı alırsak bu sayının 28 sayının içinde obebi 1 den büyük olan iki tane mutlaka olacaktır.

Örnek 6. 1,2,3,…,100 sayıları arasından en az kaç sayı seçelim ki biri diğerini mutlaka bölsün?

Çözüm. Her n doğal sayısı  v tek olacak şekilde mn= 2^u v şeklinde yazılabilir. v sayısı,  {1,3,5,…,99} kümesinin bir elemanıdır. Bu küme 50 elemanlıdır. Demek ki seçilecek 51 sayı nasıl seçilirse seçilsin aynı v sayısını içeren iki tane bulunacaktır. Bunlardan biri diğerini bölecektir.

Not. Genel olarak 2n sayı arasından n+1 tanesi seçildiğinde bu sayılar arasında biri mutlaka diğerini bölen iki sayı mevcuttur.

Örnek 7. Verilen 52 farklı sayı içerisinde toplamları veya farkları 100 ile bölünebilen iki sayının mutlaka bulunacağını gösteriniz.

Çözüm. Bir sayının son iki basamağı 00,01,02,…,98,99 şeklindedir. Demek ki son iki basamak 100 farklı sayıdan biridir. Şimdi en kötü durum olacak şeklide sayıları seçelim. Bunun için 01 ve 99 ; 02 ve 98 ; 00 ve 50 ile biten sayılar aynı anda seçilmemiş olsun. Bunlardan sadece birini seçmiş olalım. Bu durumda tam 50 sayı seçmiş oluruz. Seçeceğimiz 51. ve 52. sayılar önceden seçtiğimiz 50 sayının eşlerinden biri olacaktır. Eğer aynı iki sayı seçilirse bu durumda bu sayıların farkı 100 ile bölünmüş olur.

Örnek8. Rastgele 2000 farklı tamsayı veriliyor. Bu tamsayılar içinde farkları 1999 ile kesinlikle bölünecek şekilde iki tanesinin olduğunu gösteriniz.

Çözüm. Bir tamsayı 1999 ile bölündüğünde 0,1,2,3,…,1998 kalanlarından biri elde edilir. 0,1,2,3,…,1998 şeklinde numaralandırılmış 1999 tane kutu alalım. Verilen 2000 sayıyı sırası ile hangi kalanı veriyorsa o numaralı kutuya koyalım. Ancak 1999 farklı kalan ve 2000 farklı sayı olacağından dolayı aynı kalanı veren iki sayı aynı kutuya konmuış olur. Bu iki sayının farkı 1999 ile tam bölünür.

Örnek 9. Kenar uzunluğu 1 birim olan bir karesel alan üzerinde alınan beş farklı noktadan en az ikisi arasındaki uzaklığın \frac{\sqrt{2}}{2}   den küçük veya eşit olduğunu gösteriniz.

Çözüm. Verilen noktalar P_{1} P_{2} P_{3} P_{4} ve P_{5} ile gösterelim. Bu noktaları mümkün olduğunca birbirlerinden uzağa yerleştirelim. Bunun için P_{1} P_{2} P_{3} P_{4} noktalarını karenin dört köşesine koyalım. Ancak P_{5} nasıl yerleştirilse yerleştirilsin karenin köşelerine eşit uzaklıkta yani \frac{\sqrt{2}}{2} birim uzaklıkta ya da bir köşeye \frac{\sqrt{2}}{2} birimden daha yakındır.

Örnek10. Kenar uzunluğu 1 birim olan bir kare içinde 201 nokta işaretleniyor. Yarıçapı \frac{1}{14} olan bir çemberin bu noktalardan en az üçünü kesinlikle çevreleyeceğini ispatlayınız.

Çözüm. Kareyi kenar uzunlukları \frac{1}{10} olan 100 adet kareye bölelim. Güvercin yuvası prensibine göre içinde 3 nokta olan en az bir kare vardır. Bu kareyi çevreleyen çemberin yarıçapı \frac{\sqrt{2}}{20} dir. \frac{\sqrt{2}}{20} < \frac{1}{14} olduğundan merkezi bu üç noktayı içeren karenin merkezi olan \frac{1}{14} yarıçaplı bir çember bu kare içindeki üç noktayı çevreler.

Aşağıdaki problemleri de birer alıştırma olarak verelim:

Örnek 11. Bir sınıfta 33 öğrenci vardır, bunların yaşları toplamı 430 dur. Bu sınıfta yaşları toplamı 260  tan büyük 20 öğrenci bulunduğunu gösteriniz.

Örnek 12. Bir okuldaki 12 sınıftan toplam 65 öğrenci alınmak istendiğinden en az iki sınıftan aynı sayıda öğrenci alınması gerektiğini kanıtlayınız.

Örnek 13. Bir kutuda sarı ve lacivert renkte toplam 50 bilye bulunmaktadır. Herhangi 22 bilyeden en az biri sarı, herhangi 30 bilyeden en az biri laciverttir. Buna göre kutudaki sarı ve lacivert bilye sayılarını bulunuz.

Örnek 14. Bir düzlemde herhangi ikisi paralel olmayan 11 doğru verilmiştir. Bunlardan aralarındaki açı 17° den küçük olan iki doğrunun bulunduğunu gösteriniz.

Örnek 15. Düzlem üzerinde herhangi üçü doğrusal olmayan 4 nokta alınıyor. Bu noktalarla bütün açıları bütün açıları 45° den büyük olan bir üçgen oluşturulamayacağını gösteriniz.

Örnek 16. 40 tan büyük olmayan pozitif tamsayılardan, hiçbiri diğerinin 2 katı olmayacak şekilde en fazla kaç sayı seçilebilir?

Örnek 17.  mn+1 farklı reel sayıdan oluşan a_{1}, a_{2}, ..., a_{mn+1} dizisinde artan sırada m+1 eleman veya azalan sırada n+1  tane eleman olduğunu gösteriniz. (Erdös ve Szekeres)

Örnek 18.  {1,2,3,…,13} kümesinin elemanları hiçbir kümede iki elemanın toplamı üçüncü bir elemana eşit olmayacak ve bir elemanın 2 katı başka bir elemana eşit olmayacak şekilde 3 alt kümeye ayrılabilir mi? Neden?

Örnek 19. Bir kümede herhangi iki elemanın toplamı başka bir elemana eşit değilse ve hiçbir elemanın iki katı bu kümenin başka bir elemanına eşit değilse bu kümeye serbest toplamlı küme denir. Buna göre { 1,2,3,…, \frac{3^n-1}{2} } kümesinin daima n serbest toplamlı alt kümeye bölünebileceğini gösteriniz.

Örnek 20. {1,2,3,…, 2n+1 } kümesinin maksimum sayıda eleman içeren serbest toplamlı bir alt kümesini oluşturunuz.

 

 

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

AlphaOmega Captcha Classica  –  Enter Security Code