İ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 oldukça ilginç ve birbirinden farklı uygulamaları vardır. Prensibin tanımında bahsi geçen güvercinler ve güvercin yuvaları birer metafor olup, 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.
SORU:
Bir okuldaki öğrenciler arasından, doğum günleri (1) haftanın aynı günü, (2) ayın aynı günü, (3) yılın aynı ayı, (4) yılın aynı günü olan en az iki öğrenci mutlaka içerecek şekilde seçmemiz gereken en az öğrenci sayısı kaçtır?
Çözümü Göster
Birinci soruda öğrenciler kutulara dağılacak nesnelere (güvercinlere), haftanın günleri de kutulara (güvercin yuvalarına) karşılık gelmektedir. Bir hafta \( 7 \) gün olduğu için, doğum günü haftanın aynı günü olan en az iki öğrenci içerdiğinden emin olacağımız en az öğrenci sayısı \( 7 + 1 = 8 \) olur.
İkinci soruda öğrenciler nesnelere, ayın günleri de kutulara karşılık gelmektedir. 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 içerdiğinden emin olacağımız en az öğrenci sayısı \( 31 + 1 = 32 \) olur.
Üçüncü soruda öğrenciler nesnelere, yılın ayları da kutulara karşılık gelmektedir. Bir yılda \( 12 \) ay olduğu için, doğum günü yılın aynı ayı olan en az iki öğrenci içerdiğinden emin olacağımız en az öğrenci sayısı \( 12 + 1 = 13 \) olur.
Dördüncü soruda öğrenciler nesnelere, yılın günleri de kutulara karşılık gelmektedir. Bir yılda (29 Şubat dahil) \( 366 \) gün olduğu için, doğum günü yılın aynı günü olan en az iki öğrenci içerdiğinden emin olacağımız en az öğrenci sayısı \( 366 + 1 = 367 \) olur.
SORU:
Birbirinden farklı desende 5 çift çorabın bulunduğu bir çekmeceden karanlık bir odada en az kaç tek çorap seçmeliyiz ki, mutlaka birbirinin eşi iki tek çorap seçmiş olalım?
Çözümü Göster
Bu soruda çorapların tekleri kutulara dağılacak nesnelere, diğer eşiyle eşleşmesi gereken çorap çiftleri de kutulara karşılık gelmektedir. Toplam \( 5 \) çift çorap olduğu için, birbirinin eşi olan en az iki çorap teki seçtiğimizden emin olacağımız en az tek çorap sayısı \( 5 + 1 = 6 \) olur.
Buna göre, \( 5 \) tek çorap seçtiğimizde tüm çoraplar farklı desenlerin teki olabilecektir, ama bu noktada tüm kutular dolu olacağı için seçeceğimiz \( 6 \). çorap teki mutlaka bir kutudaki çorapla eşleşecektir.
SORU:
Standart bir iskambil destesinde (1) aynı simge (maça, sinek vb), (2) aynı sayı (2, 5, vale, as vb), (3) aynı renkte (siyah, kırmızı) en az iki kart çektiğimizden emin olmak için çekmemiz gereken en az kart sayısı kaçtır?
Çözümü Göster
Birinci soruda kartlar nesnelere, kartların simgeleri de kutulara karşılık gelmektedir. \( 4 \) farklı simge olduğu için, aynı simgede en az iki kart çektiğimizden emin olacağımız en az kart sayısı \( 4 + 1 = 5 \) olur.
İkinci soruda kartlar nesnelere, kartların sayıları da kutulara karşılık gelmektedir. \( 13 \) farklı sayı olduğu için, aynı sayıda en az iki kart çektiğimizden emin olacağımız en az kart sayısı \( 13 + 1 = 14 \) olur.
İkinci soruda kartlar nesnelere, kartların renkleri de kutulara karşılık gelmektedir. \( 2 \) farklı renk olduğu için, aynı renkte en az iki kart çektiğimizden emin olacağımız en az kart sayısı \( 2 + 1 = 3 \) olur.
SORU:
Bir şehirdeki kişiler içinde doğumgünleri yılın aynı gününün aynı saatinin aynı dakikası olan en az iki kişi olabilmesi için şehir nüfusu en az kaç kişi olmalıdır?
Çözümü Göster
Bu soruda şehirde yaşayan kişiler nesnelere, yılın farklı günlerinin farklı saatlerinin farklı dakikaları da kutulara karşılık gelmektedir. Bir 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, aynı dakikada doğan en az iki kişi olduğundan emin olacağımız en az kişi sayısı \( 527.040 + 1 = 527.041 \) olur.
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 \( f \) fonksiyonu birebir olamaz.
\( m \lt n \) ise \( 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{\dfrac{m}{n}} \) ya da daha fazla nesne içermek zorundadır.
Aynı durumda, kutulardan en az biri \( k = \floor{\dfrac{m}{n}} \) ya da daha az nesne içermek zorundadır.
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ını aşağıdaki formülle bulabiliriz.
\( m = (k - 1) \cdot n + 1 \)
Bu genelleştirilmiş prensipte \( k = 2 \) koyduğumuzda temel prensibi elde ederiz.
Yukarıdaki formülde geçen \( \ceiling{x} \) ifadesi tavan fonksiyonuna, \( \floor{x} \) ifadesi taban fonksiyonuna karşılık gelmektedir. Bu fonksiyonlarla ilgili daha fazla bilgi için Özel Fonksiyonlar sayfasını ziyaret edebilirsiniz.
SORU:
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?
Çözümü Göster
Bu soruda dersler nesnelere, derslerin her hafta verileceği ders saatleri de kutulara karşılık gelmektedir. 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ğıtırsak, kutulardan en az biri \( \ceiling{\dfrac{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.
SORU:
Bir torbada 10 adet kırmızı, 10 adet yeşil ve 10 adet mavi bilye vardır. Torbadan rastgele seçeceğimiz bilyeler içinde aynı renkte 5 bilye olduğundan emin olabilmek için en az kaç bilye seçmeliyiz?
Çözümü Göster
Bu soruda bilyeler nesnelere, renkler de kutulara karşılık gelmektedir. Soruda bulmak istediğimiz, herhangi bir kutuda en az 5 nesne olduğundan emin olabilmek için seçmemiz gereken en az nesne sayısıdır.
Soruda verilen bilgileri formülde yerine koyarak en az bilye sayısını bulabiliriz.
\( m = (k - 1) \cdot n + 1 \)
\( m = (5 - 1) \cdot 3 + 1 = 13 \)
Buna göre, en az \( 13 \) bilye seçtiğimizde, bir renkte en az 5 bilye seçtiğimizden emin olabiliriz.
SORU:
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.)
Çözümü Göster
Bu soruda kişiler nesnelere, iller de kutulara karşılık gelmektedir. Soruda bulmak istediğimiz, herhangi bir kutuda en az 3 nesne olduğundan emin olabilmek için ihtiyaç duyacağımız toplam nesne sayısıdır.
Soruda verilen bilgileri formülde yerine koyarak en az kişi sayısını bulabiliriz.
\( m = (k - 1) \cdot n + 1 \)
\( m = (3 - 1) \cdot 81 + 1 = 163 \)
Buna göre, en az \( 163 \) kişi seçtiğimizde ve il kutularına dağıttığımızda, bir kutunun en az 3 kişi içerdiğinden emin olabiliriz.
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ğunu varsayarsak temel prensibi elde ederiz.
\( 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 \)
SORU:
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 talepte bulunduğunda bir deneme sınavı organize edilmektedir. Buna göre, yeni bir deneme sınavı organize etmek için alınması gereken en az talep sayısı kaçtır?
Çözümü Göster
Bu soruda deneme sınav talepleri kutulara dağılacak 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ı bulabiliriz.
\( m = q_1 + q_2 + \cdots + q_n - n + 1 \)
\( m = 15 + 12 + 10 + 8 - 4 + 1 = 42 \)
Buna göre, en az \( 42 \) talep alındığında yeni bir deneme sınavı organize edilecektir.