İsterseniz burdan Github linkine de gidebilirsiniz.

Güvercin Yuvası Prensibi

Eğer 4 güvercininiz ve onları yerleştirebileceğiniz 3 yuvanız varsa en az ikisi yuva arkadaşı olmak zorundadır.

Genel bir ifadeyle: Eğer k deliğe koymak için k + 1 tane objeniz varsa, o zaman en azından bir tane deliğin içinde 2 veya daha fazla obje olması zorunludur.

alt text

Güvercin yuvası prensibinin hikayesi

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, bir ağaçta olabilecek maksimum yaprak sayısı mı?"

Babası da "ağaç sayısı" demiş.

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.

Güvercin yuvası prensibi hem matematiksel teorem ispatlarında hem de güvercin yerleştirmek gibi matematik ile direkt bağlantısı olmadığını sandığımız bir çok yerde karşımıza çıkmaktadır. Şimdi ise başka bir güvercin yuvası problemine bakalım.

Soru

1 den 12 ye kadar sayılar bir çemberin üzerine diziliyor. Bu işlem hangi sıralamayla yapılırsa yapılsın toplamları 20 veya daha fazla olan komşu 3 sayının muhakkak bulunacağını gösterme deneyini kodda gösterelim.

Çözüm

Sayılar saat yönünde a1,a2,...,a12 olsun.

b1=a1+a2+a3

b2=a2+a3+a4

.

.

b12=a12+a1+a2

olsun. bi'lerin toplamı 3(1+2+..+12)=234 yani bu sayılardan biri 234/12=~20 ' den büyüktür.

Kodda göstermek gerekirse ;

In [1]:

toplam =0 
for x in range(1, 12):
    if(x+1 == 12):
        toplam = toplam + x + 12 + 1
        print(x, 12, 1," toplam =",x + 12 + 1, "\n")
        toplam = toplam + 12 + 1 + 2
        print(x+1, 1, 2," toplam =",12 + 1 + 2, "\n")
    else:
        toplam = toplam + 3*x + 3
        print(x, x+1, x+2," toplam =",3*x + 3, "\n")

1 2 3  toplam = 6 

2 3 4  toplam = 9 

3 4 5  toplam = 12 

4 5 6  toplam = 15 

5 6 7  toplam = 18 

6 7 8  toplam = 21 

7 8 9  toplam = 24 

8 9 10  toplam = 27 

9 10 11  toplam = 30 

10 11 12  toplam = 33 

11 12 1  toplam = 24 

12 1 2  toplam = 15

Eleman sayısı ve grup sayısını belirleyelim.

Eleman sayısının grup sayısına bölümünün bir üst sayıya yuvarlanması bize en az bir 3'lünün toplamının büyük olabileceği değeri verecektir.

In [4]:

import math
Eleman_sayisi= toplam
Grup_sayisi=12
en_az= math.ceil(Eleman_sayisi/Grup_sayisi)
print("toplam =",toplam)

print("toplam / 12 =~",en_az)

toplam = 234
toplam / 12 =~ 20

20'den büyük olan en az bir 3'lü grup vardır.