Güvercin Yuvası Prensibi
İlk bakışta ayrı bir başlık olmasına gerek olmadığını düşündürtecek kadar basit bir prensip olan Güvercin Yuvası Prensibi'nin pek çok farklı ve oldukça ilginç uygulamaları vardır. Prensibin farklı uygulamalarında güvercinler farklı nesnelere, güvercin yuvaları da bu nesnelerin dağıtılacağı kutulara karşılık gelmektedir. Bu prensibin bir diğer adı çekmece prensibidir.
Temel Prensip
Bu prensibin en basit uygulaması, kutulardan en az birindeki nesne sayısının iki ya da daha fazla olduğu durumdur.
\( m \gt n \) olmak üzere,
\( m \) nesnenin \( n \) kutuya dağıtıldığı durumda, kutulardan en az biri iki ya da daha fazla nesne içermek zorundadır.
Bu prensibin diğer bazı uyarlamaları aşağıdaki gibidir.
- \( m \lt n \) olduğu durumda, kutulardan en az biri boş kalmak zorundadır.
- \( m = n \) olduğu durumda, kutulardan hiçbiri boş değilse tüm kutularda birer nesne olmak zorundadır.
- \( m = n \) olduğu durumda, kutulardan hiçbirinde birden fazla nesne yoksa tüm kutularda birer nesne olmak zorundadır.
Bir okuldaki öğrenciler arasından, doğum günleri aşağıdaki şekilde olan en az iki öğrenci seçildiğinden emin olmak için seçilmesi gereken en az öğrenci sayısı kaçtır?
(a) haftanın aynı günü
(b) ayın aynı günü
(c) yılın aynı ayı
(d) yılın aynı günü
(a) seçeneği:
Bu soruda öğrenciler kutulara dağılacak nesnelere (güvercinlere), haftanın günleri de kutulara (güvercin yuvalarına) karşılık gelir.
Bir hafta 7 gün olduğu için, doğum günü haftanın aynı günü olan en az iki öğrenci seçildiğinden emin olmak için seçilmesi gereken en az öğrenci sayısı \( 7 + 1 = 8 \) olur.
(b) seçeneği:
Bu soruda öğrenciler yine nesnelere, ayın günleri de kutulara karşılık gelir.
Bir ayda en fazla 31 gün olduğu için, doğum günü ayın aynı günü olan en az iki öğrenci seçildiğinden emin olmak için seçilmesi gereken en az öğrenci sayısı \( 31 + 1 = 32 \) olur.
(c) seçeneği:
Bu soruda öğrenciler yine nesnelere, yılın ayları da kutulara karşılık gelir.
Bir yılda 12 ay olduğu için, doğum günü yılın aynı ayı olan en az iki öğrenci seçildiğinden emin olmak için seçilmesi gereken en az öğrenci sayısı \( 12 + 1 = 13 \) olur.
(d) seçeneği:
Bu soruda öğrenciler yine nesnelere, yılın günleri de kutulara karşılık gelir.
Bir yılda (29 Şubat dahil) en fazla 366 gün olduğu için, doğum günü yılın aynı günü olan en az iki öğrenci seçildiğinden emin olmak için seçilmesi gereken en az öğrenci sayısı \( 366 + 1 = 367 \) olur.
Standart bir iskambil destesinden aşağıdaki şekilde en az iki kart çekildiğinden emin olmak için çekilmesi gereken en az kart sayısı kaçtır?
(a) aynı simgede (maça, sinek vb)
(b) aynı sayıda (2, 5, vale, as vb)
(c) aynı renkte (siyah, kırmızı)
(a) seçeneği:
Bu soruda kartlar nesnelere (güvercinlere), kartların simgeleri de kutulara (güvercin yuvalarına) karşılık gelir.
4 farklı simge olduğu için (kupa, karo, maça, sinek), aynı simgede en az iki kart çekildiğinden emin olmak için çekilmesi gereken en az kart sayısı \( 4 + 1 = 5 \) olur.
(b) seçeneği:
Bu soruda kartlar yine nesnelere, kartların sayıları da kutulara karşılık gelir.
13 farklı sayı olduğu için (1, 2, ..., 10, vale, kız, papaz), aynı sayıda en az iki kart çekildiğinden emin olmak için çekilmesi gereken en az kart sayısı \( 13 + 1 = 14 \) olur.
(c) seçeneği:
Bu soruda kartlar yine nesnelere, kartların renkleri de kutulara karşılık gelir.
2 farklı renk olduğu için (kırmızı, siyah), aynı renkte en az iki kart çekildiğinden emin olmak için çekilmesi gereken en az kart sayısı \( 2 + 1 = 3 \) olur.
Birbirinden farklı desende 5 çift çorabın bulunduğu bir çekmeceden karanlık bir odada en az kaç tek çorap seçilmeli ki, mutlaka birbirinin eşi iki tek çorap seçilmiş olsun?
Bu soruda çorapların tekleri nesnelere, her çorap deseni de kutulara karşılık gelir.
Toplam 5 çift çorap olduğu için, birbirinin eşi olan en az iki çorap teki seçildiğinden emin olmak için seçilmesi gereken en az tek çorap sayısı \( 5 + 1 = 6 \) olur.
Buna göre, 5 tek çorap seçildiğinde tüm çoraplar farklı desenlere (kutulara) ait olabilir, ama bu noktada tüm kutular dolu olacağı için seçilecek 6. çorap teki mutlaka bir kutudaki çorapla eşleşecektir.
Bir şehirde yaşayan kişiler içinde, doğumgünleri yılın aynı gününün aynı saatinin aynı dakikası olan en az iki kişinin mutlaka olması için şehrin nüfusu en az kaç kişi olmalıdır?
Bu soruda şehirde yaşayan kişiler nesnelere, yılın farklı günlerinin farklı saatlerinin farklı dakikaları da kutulara karşılık gelir.
Bir (artık) yılda 366 gün, bir günde 24 saat ve bir saatte 60 dakika olduğu için, bir yıl içinde farklı \( 366 \cdot 24 \cdot 60 = 527.040 \) dakika vardır. Buna göre, şehirde aynı dakikada doğmuş olan en az iki kişi olduğundan emin olmak en az kişi sayısı \( 527.040 + 1 = 527.041 \) olur.
3 mavi, 4 kırmızı ve 7 sarı bilyenin bulunduğu bir torbadan her renkte en az bir bilyenin çekildiğinden emin olmak için en az kaç bilye çekilmelidir?
Bu soruda bilyeler nesnelere, farklı renkler de kutulara karşılık gelir.
Her renkte en az bir bilyenin çekildiğinden emin olmak için, en kötü senaryo olan torbada en az sayıda bulunan mavi bilyelerin en sona kaldığı senaryo dikkate alınır.
Bu durumda ilk 11 çekilişte 4 kırmızı ve 7 sarı bilyenin çekildiği varsayılır. Bu noktada torbada sadece mavi bilye kalacağı için 1 bilye daha çekildiğinde her renkten bir bilye çekildiğinden emin olunabilir.
Buna göre çekilmesi gereken en az bilye sayısı \( 4 + 7 + 1 = 12 \) olur.
Bir sepetteki 35 mavi, 21 mor, 17 sarı, 7 yeşil ve 3 kırmızı mandal arasından birer birer mandal alınıyor.
Aynı renkte 20 mandal alındığından emin olmak için sepetten en az kaç mandal alınmalıdır?
Aynı renkte 20 mandal alındığından emin olmak için, öncesinde 20 ve üzerinde sayıda mandal içeren renklerden (mavi ve mor) 19'ar mandal, 20'den az sayıda mandal içeren renklerin ise tümünün seçildiği en kötü senaryonun gerçekleşeceği varsayılır.
Buna göre en kötü senaryoda önce 19 mavi, 19 mor, 17 sarı, 7 yeşil ve 3 kırmızı mandal sepetten alınır.
Bu noktada sepette sadece mavi ve mor mandallar kalacağı için, ilk alınacak mandalla birlikte aynı renkte 20 mandal alındığından emin olunabilir.
Buna göre, alınması gereken en az mandal sayısı \( 19 + 19 + 17 + 7 + 3 + 1 = 66 \) olur.
\( n \) kişinin bulunduğu bir toplulukta en az iki kişinin aynı sayıda arkadaşa sahip olduğunu güvercin yuvası prensibini kullanarak gösteriniz.
Bu gruptaki \( n \) kişinin arkadaş sayılarına sırasıyla \( k_1, k_2, \ldots, k_n \) diyelim.
Bir kişi en az sıfır, en fazla kendisi dışındaki kişilerle, yani \( n - 1 \) kişi ile arkadaş olabilir.
\( 1 \le i \le n \) olmak üzere,
\( 0 \le k_i \le n - 1 \)
A kişisi B kişisi ile arkadaş ise B kişisi de A kişisi ile arkadaştır.
Buna göre, eğer grupta en az bir kişinin \( n - 1 \) arkadaşı varsa (yani herkesi tanıyorsa) grupta kimsenin 0 arkadaşı olamaz, dolayısıyla bu durumda \( k_i \) değerleri 0 olamaz ve \( n - 1 \) farklı değer alabilir.
\( 1 \le k_i \le n - 1 \)
Eğer grupta hiçbir kişinin \( n - 1 \) arkadaşı yoksa (yani herkesi tanıyan bir kişi yoksa) \( k_i \) değerleri \( n - 1 \) olamaz ve yine \( n - 1 \) farklı değer alabilir.
\( 0 \le k_i \le n - 2 \)
Buna göre \( k_i \) değerleri her iki durumda da \( n - 1 \) farklı değer alabilir.
\( n \) kişiye ait \( k_i \) arkadaş sayılarını her bir farklı değere ait \( n - 1 \) kutuya dağıttığımızı düşünelim.
Nesne sayısı \( = n \)
Kutu sayısı \( = n - 1 \)
Güvercin yuvası prensibine göre, bu dağıtım sonucunda en az bir kutuya birden fazla nesne gireceği için en az 2 kişinin aynı sayıda arkadaşı olur.
Bir çiftlikteki kümeste \( x \) tane tavuk, \( y \) tane ördek vardır. Bir gün kümesteki hayvanlardan 11'inin kaçtığını öğrenen çiftlik sahibi, kümese bakmadan kaçan hayvanlardan en az ikisinin ördek olduğunu doğru şekilde tahmin ediyor.
Buna göre kümesteki tavuk ve ördek sayıları için aşağıdaki \( ( x, y ) \) ikililerinden hangileri doğru olabilir?
I. \( (12, 10) \)
II. \( (10, 11) \)
III. \( (9, 8) \)
IV. \( (8, 7) \)
Çiftlik sahibi kaçan hayvanlardan en az 2'sinin ördek olduğunu kümese bakmadan tahmin edebiliyorsa kümesteki toplam tavuk sayısı en fazla 9 olmalıdır. Bu durumda kaçan 11 hayvandan en az ikisinin ördek olduğundan emin olunabilir.
Buna göre III. ve IV. öncüller doğru olabilir.
Kenar uzunluğu 1 birim olan bir düzgün altıgenin içinden seçilecek 7 farklı noktadan en az ikisi arasındaki uzaklığın her zaman 1'den küçük ya da 1'e eşit olduğunu gösteriniz.
Altıgenin karşı köşeleri arasındaki köşegenleri çizelim.
Bu şekilde altıgen kenar uzunlukları 1 birim olan 6 eşkenar üçgene ayrılmış olur.
Seçeceğimiz 7 noktayı farklı nesneler, noktaların içinde bulundukları eşkenar üçgenleri de kutular olarak düşünelim.
7 nokta ve 6 kutu söz konusu olduğu için, güvercin yuvası prensibine göre noktaların en az ikisi aynı eşkenar üçgenin içinde ya da kenarları üzerinde olmak zorundadır.
Kenar uzunluğu 1 birim olan bir eşkenar üçgenin içinde ya da kenarları üzerindeki iki nokta arasındaki mesafe her zaman 1'den küçük ya da 1'e eşit olduğu için, 7 noktanın en az ikisi arasındaki uzaklık her zaman 1'den küçük ya da 1'e eşit olur.
Fonksiyon Uygulamaları
Bu prensibin fonksiyonlar üzerindeki bazı uygulamaları aşağıdaki gibidir.
\( A \) ve \( B \) sonlu kümeler,
\( f: A \to B \) olmak üzere,
\( s(A) = m, \quad s(B) = n \),
\( m \gt n \) ise değer kümesinde tanım kümesinin her elemanı ile birebir eşlenecek yeterli eleman bulunmadığı için \( f \) fonksiyonu birebir olamaz.
\( m \lt n \) ise tanım kümesinde değer kümesinin her elemanı ile eşlenecek yeterli eleman bulunmadığı için \( f \) fonksiyonu örten olamaz.
\( m = n \) ve \( f \) örten bir fonksiyon ise \( f \) aynı zamanda birebirdir.
\( m = n \) ve \( f \) birebir bir fonksiyon ise \( f \) aynı zamanda örtendir.
Genelleştirilmiş Prensip - I
Bu prensibin bir diğer uygulaması, kutulardan en az birindeki nesne sayısının \( k \) ya da daha fazla olduğu durumdur.
\( m \gt n \) olmak üzere,
\( m \) nesnenin \( n \) kutuya dağıtıldığı durumda, kutulardan en az biri \( k = \ceiling{\frac{m}{n}} \) ya da daha fazla nesne içermek zorundadır.
Aynı durumda, kutulardan en az biri \( k = \floor{\frac{m}{n}} \) ya da daha az nesne içermek zorundadır.
Yukarıdaki formüldeki \( \ceiling{x} \) ifadesi tavan fonksiyonu, \( \floor{x} \) ifadesi taban fonksiyonudur. Bu fonksiyonlarla ilgili daha fazla bilgi için özel fonksiyonlar sayfasını ziyaret edebilirsiniz.
Bu prensibin bir diğer uygulaması olarak, en az bir kutuda \( k \) ya da daha fazla nesne olması isteniyorsa olması gereken en az toplam nesne sayısı aşağıdaki formülle bulunabilir.
\( m = (k - 1)n + 1 \)
Bu genelleştirilmiş prensipte \( k = 2 \) konduğunda temel prensip elde edilir.
Bir üniversitenin ders takvimine göre bir hafta içinde 35 farklı ders saati vardır. Her hafta 720 farklı ders verildiğine göre, üniversitenin ihtiyaç duyacağı en az derslik sayısı kaçtır?
Bu soruda dersler nesnelere, derslerin her hafta verileceği ders saatleri de kutulara karşılık gelir.
Herhangi bir kutuya dağıtılan ders sayısı, üniversitenin o saatte ihtiyaç duyacağı derslik sayısını verecektir ve üniversitenin en fazla sayıda nesne içeren kutudaki nesne sayısı kadar dersliğe ihtiyacı olacaktır.
720 nesneyi 35 farklı kutuya dağıttığımızda kutulardan en az biri \( \ceiling{\frac{720}{35}} = \ceiling{20,57...} = 21 \) ya da daha fazla nesne içermek zorundadır, dolayısıyla üniversitenin ihtiyaç duyacağı en az derslik sayısı 21 olur.
Bir torbada 10 adet kırmızı, 10 adet yeşil ve 10 adet mavi bilye vardır. Torbadan rastgele seçilen bilyeler içinde aynı renkte 5 bilye olduğundan emin olmak için en az kaç bilye seçilmelidir?
Bu soruda bilyeler nesnelere, farklı renkler de kutulara karşılık gelir. Soruda istenen herhangi bir kutuda en az 5 nesne olduğundan emin olmak için seçilmesi gereken en az nesne sayısıdır.
Soruda verilen bilgileri formülde yerine koyarak en az bilye sayısını bulalım.
\( m = (k - 1)n + 1 \)
\( m = (5 - 1)3 + 1 = 13 \)
Buna göre, en az 13 bilye seçildiğinde bir renkte en az 5 bilye seçildiğinden emin olunabilir.
Sadece Türkiye'de doğmuş kişilerden oluşan bir grupta, aynı ilde doğmuş en az 3 kişilik bir ekip oluşturabilmek için en az kaç kişi seçilmelidir? (toplam il sayısı 81'dir.)
Bu soruda kişiler nesnelere, iller de kutulara karşılık gelr. Soruda istenen herhangi bir kutuda en az 3 nesne olduğundan emin olmak için ihtiyaç duyulan toplam nesne sayısıdır.
Soruda verilen bilgileri formülde yerine koyarak en az kişi sayısını bulalım.
\( m = (k - 1)n + 1 \)
\( m = (3 - 1)81 + 1 = 163 \)
Buna göre, en az 163 kişi seçildiğinde ve il kutularına dağıtıldığında, bir kutunun en az 3 kişi içerdiğinden emin olunabilir.
Genelleştirilmiş Prensip - II
Bu prensibin bir diğer uygulaması, kutulardan en az birindeki nesne sayısının her kutu için farklı olduğu durumdur.
\( q_1, q_2, \ldots, q_n \in \mathbb{Z^+} \) olmak üzere,
\( m = q_1 + q_2 + \ldots + q_n - n + 1 \)
nesnenin \( n \) kutuya dağıtıldığı durumda, ya \( 1 \). kutu en az \( q_1 \) nesne, ya \( 2 \). kutu en az \( q_2 \) nesne, \( \ldots \), ya da \( n \). kutu en az \( q_n \) nesne içermek zorundadır.
Bu genel prensipte tüm kutulardaki nesnelerin eşit ve 2 olduğu varsayılırsa temel prensip elde edilir.
\( q_1 = q_2 = \ldots = q_n = 2 \) olmak üzere,
Dağıtılacak nesne sayısı: \( m = 2n - n + 1 = n + 1 \)
Kutu sayısı: \( n \)
Bir lisede 9. sınıflardan 15 öğrenci, 10. sınıflardan 12 öğrenci, 11. sınıflardan 10 öğrenci ve 12. sınıflardan 8 öğrenci talep formu doldurup talep kutusuna bıraktığında o sınıf için bir deneme sınavı organize edilmektedir.
Buna göre, talep kutusunda en az kaç talep formu varsa formları açmadan bir deneme sınavı organize edileceğinden emin olunabilir?
Bu soruda talep formları nesnelere, sınıflar da (9, 10 vb) kutulara karşılık gelmektedir.
Soruda verilen bilgileri formülde yerine koyarak en az talep sayısını bulalım.
\( m = q_1 + q_2 + \cdots + q_n - n + 1 \)
\( m = 15 + 12 + 10 + 8 - 4 + 1 = 42 \)
Buna göre, talep kutusunda en az 42 talep formu varsa yeni bir deneme sınavı organize edileceğinden emin olunabilir.