MATEMATIKA
Dirichletov princip in paradoks rojstnega dneva
Primož Moravec
-> Dirichletov princip ni nic drugega kot enostavno dejstvo, ki ga lahko formuliramo na naslednji način: Cev n škatel razporedimo n + 1 žogic, sta v eni škatli vsaj dve žogici. Na prvi pogled nič posebnega, toda to načelo je v matematiki zelo uporabno. Prvič se je pojavilo v literaturi z delom Dirichleta (1805-1859) v teoriji števil, zato tudi nosi njegovo ime. Prispevek o Dirichletovem principu je že izšel v Preseku [1] pred 30-imi leti.
Tudi v tem clanku bomo prikazali nekaj primerov uporabe Dirichletovega principa, na koncu pa bomo problem razporejanja žogic v škatle pogledali še z drugega, verjetnostnega zornega kota.
Oglejmo si nekaj osnovnih primerov. Recimo, da imamo skupino 367 ljudi. Potem med njimi obstajata vsaj dve osebi, ki praznujeta rojstni dan na isti dan. Podoben sklep pokaže, da med poljubnimi štirimi naravnimi števili obstajata dve, ki imata isti ostanek pri deljenju s 3. Poleg tega očitno velja nekoliko splošnejša razlicica Dirichletovega principa, ki se glasi: Cev n škatel razporedimo kn + 1 žogic, je v vsaj eni škatli vec kot k žogic.
Lotimo se še malo zahtevnejših primerov.
Problem 1: V sobi je 2017 oseb. Pokaži, da obstajata vsaj dve osebi, ki imata enako število znancev v sobi.
Rešitev. Imejmo 2017 škatel, oznacenih s števili od 0 do 2016, in osebo spravimo v škatlo n, ce ima v sobi natanko n znancev. Ce je kakšna oseba v škatli številka 0, potem ni nikogar v škatli številka 2016, in
©
©	©	©
©	©	©
®	©	©
SLIKA 1.
Deset žogic in devet škatel
obratno. Torej imamo v resnici na voljo 2016 škatel, kamor razporejamo 2017 oseb. Sedaj lahko neposredno uporabimo Dirichletov princip in sklepamo, da sta v eni od škatel vsaj dve osebi, to pa je ravno rešitev našega problema.
Problem 2: Med n celimi števili vedno obstaja pod-množica teh števil, katere vsota je deljiva z n.
Rešitev. Naj bodo x1,x2,... ,xn cela števila. Oglejmo si vsote
■ 51 = X1,
s2 = X1 + x2,
Sn = x1 + x2 +
xn
10
PRESEK 45 (2017/2018) 1
MATEMATIKA
Ce je že ena od teh vsot deljiva z n, potem je naloga rešena. V nasprotnem primeru vse vsote pri deljenju z n dajo neniceln ostanek. Teh vsot je n, na voljo pa imamo le n - 1 nenicelnih ostankov. Po Dirichleto-vem principu obstajata dve vsoti, recimo sm in sm+k, ki pri deljenju z n dasta enak ostanek. Potem pa je vsota
" sm+k - sm = xm+1 + xm+2 + • • • + xm+k
deljiva z n.
Naslednje dejstvo je mogoče izpeljati s pomočjo Evklidovega algoritma, tu pa pokažimo, kako do njega pridemo z Dirichletovim principom. Spomnimo se, da pravimo, da sta naravni števili m in n tuji, ce je 1 najvecje naravno število, ki hkrati deli m in n.
Rešitev. Naj bosta A in B takšni tocki, za kateri je razdalja |AB| najvecja možna. Ce je |AB| < 1, je naloga že rešena; krog s središcem v A in polmerom 1 vsebuje v svoji notranjosti vseh 2017 danih tock. Predpostavimo torej, da je |AB| > 1. Ce je X katerakoli od danih tock, ki je razlicna od A in B, potem velja |AX | < 1 ali |BX | < 1. V tem primeru vsaka od danih tock pade v notranjost kroga s središcem v A in polmerom 1 ali v notranjost kroga s središcem B in polmerom 1. V jeziku škatel, v dve škatli razporejamo 2017 = 1008 • 2 + 1 žogic. Zato ena od škatel (torej eden od krogov) vsebuje vec kot 1008 žogic (torej tock).
Bralca vabimo k rešitvi naslednjih nalog:
Problem 3: Naj bosta m in n tuji naravni števili. Potem obstajata naravni števili x in y, da je nx -my = 1.
Rešitev. Oglejmo si števila n, 2n,...,(m - 1)n in njihove ostanke pri deljenju z m. Ker nobeno od navedenih števil ni deljivo z m, se ostanek 0 ne pojavi. Ali se lahko zgodi, da se tudi ostanek 1 ne pojavi? Ce bi se to zgodilo, bi imeli na voljo m - 2 vrednosti za ostanke in bi po Dirichletovem principu v zgornjem zaporedju števil obstajali dve razlicni števili. Ozna-cimo ju z an in bn kjer je a > b, ki bi pri deljenju z m dali enak ostanek. V tem primeru bi bilo število an - bn = (a - b)n deljivo z m, to pa ni mogoce, saj sta m in n tuji števili in a - b < m. Sklepamo torej, da obstaja tako naravno število x G {1, 2,...,m - 1}, da je ostanek nx pri deljenju z m enak 1, kar lahko zapišemo tudi kot nx = my + 1 za neki y G N.
Hitro lahko preverimo, da velja tudi obrat trditve v zgornjem primeru; ce za naravni števili m in n obstajata taki naravni števili x in y, daje nx-my = 1, potem sta m in n tuji števili. Ce je namrec najvecji skupni delitelj števil m in n enak d, potem lahko zapišemo m = dm1 in n = dn1 za neki naravni števili m1 in n1. Dobimo d(n1x-m1y) = 1, od koder takoj sledi d = 1.
Problem 4: V ravnini je 2017 razlicnih tock, za katere velja, da v poljubni trojici tock obstajata dve, ki sta oddaljeni za manj kot 1. Pokaži, da obstaja krog s polmerom 1, znotraj katerega je vsaj 1009 tock.
V	kocki z robom dolžine 5 na slepo izberemo 124 tock. Pokaži, da znotraj te kocke obstaja kocka z robom dolžine 1, ki ne vsebuje nobene od izbranih tock.
V	sobi je 2017 oseb, vsak se rokuje z vsakim. Potem sta v vsakem trenutku v sobi vsaj dve osebi, ki sta se do tega casa rokovali z enakim številom oseb.
V	konveksnem šestkotniku vedno obstaja diagonala, ki odreže trikotnik, katerega plošcina ne presega ene šestine plošcine šestkotnika. Naj bosta a in b tuji naravni števili. Potem v decimalnem zapisu ulomka a/b perioda de-cimalk ne presega b - 1.
Oglejmo si sedaj primer, ko razporejamo m žogic v n škatel. Ce je m < n, se prav lahko zgodi, da nobena od škatel ne vsebuje vec kot ene žogice. Lahko pa govorimo o verjetnosti, da vsaj ena od škatel vsebuje vsaj dve žogici. Formalne definicije verjetnosti tu ne bomo navedli, bodimo malce površni. Predstavljajmo si, da žogice na slepo mecemo v škatle, za nas pa bo zanimiv dogodek, da po koncu razporejanja vsaj ena škatla vsebuje vsaj dve žogici. Ce z x oznacimo število nacinov, na katere lahko m žogic razporedimo v n predalov, z y pa število tistih razporejanj, ki dajo ugoden rezultat, torej, da vsaj ena škatla vsebuje vsaj dve žogici, potem razmerju
P =
y
x

10	PRESEK 45 (2017/2018) 1

MATEMATIKA
—^ pravimo verjetnost dogodka, da vsaj ena škatla vsebuje vsaj dve žogici. Število p torej pove razmerje med številom »dobrih razporejanj« in številom vseh razporejanj žogic v škatle. Dirichletov princip pravi nic drugega kot to, da ce razporejamo vsaj n + 1 žogic v n škatel, potem je p = 1. V teoriji verjetnosti pravimo, da je dogodek »v vsaj eni škatli sta vsaj dve žogici« gotovi dogodek.
Poskusimo izračunati verjetnost p v splošnem. Najprej si oglejmo, na koliko nacinov lahko razporedimo m žogic v n škatel. Pri tem predpostavimo, da je m < n. Mislimo si, da žogice zaporedoma me-cemo v škatle brez omejitev. Za prvo žogico imamo n možnih izbir škatle, za drugo prav tako itd. Za razporeditev m žogic v n škatel imamo torej na voljo x = nm razporejanj. Izracunajmo še y, pri ce-mer si pomagajmo z manjšim trikom. Oglejmo si namrec število % - y. To je ravno število vseh možnih razporejanj žogic v škatle, pri katerih na koncu vsaka škatla vsebuje kvečjemu eno žogico. V tem primeru imamo za prvo žogico n možnih izbir škatle. Za drugo žogico velja, da je ne smemo dati tja, kjer je že prva, torej imamo na voljo še n - 1 ška-tel. Podobno imamo za tretjo žogico n - 2 možnih izbir škatle. Na koncu imamo za m-to žogico natanko n - m + 1 možnih izbir škatle. Zato je % - y = n(n - 1)(n - 2) ■ ■ ■ (n - m + 1), torej dobimo
p=
nm - n(n - 1)(n - 2) ■ ■ ■ (n - m + 1)
n"
1
n(n - 1)(n - 2) ■ ■ ■ (n - m + 1)
nm
p=1-
365 ■ 364 ■ ■ ■(366 - n) 365n	'
Na sliki 2 je graficno prikazano, kako se p obnaša v odvisnosti od n.
p
1.0 -
0.6
0.4

Opazimo, da formula velja tudi za primer, ko je m > n. V tem primeru je namrec števec drugega ulomka v zgornjem izrazu enak 0 in je p = 1, kar je ravno Dirichletov princip.
Recimo, da imamo skupino n ljudi in gledamo njihove rojstne dneve. Zaradi enostavnosti predpostavimo, daje vsak od 365 dni neprestopnega leta enako verjeten kot rojstni dan, 29. februarja pa ne štejemo. Verjetnost, da imata vsaj dve osebi rojstni dan na isti dan, je
SLIKA 2.
Verjetnost, da imata med n ljudmi vsaj dve osebi rojstni dan na isti dan
Rezultat je nekoliko presenetljiv. Za n = 23 dobimo p = 0,507, kar lahko interpretiramo kot dejstvo, da v skupini 23 ljudi obstaja 50 odstotna možnost, da imata vsaj dva rojstni dan na isti dan. Ko je v skupini 60 ljudi, je ta možnost že 99,4 odstotna. To je v nasprotju z intuicijo, saj je ljudi le 60, možnih rojstnih dni pa 365, zato bi pricakovali, da je možnost, da imata vsaj dva med njimi rojstni dan na isti dan, bistveno manjša. Temu navideznemu protislovju pravimo paradoks rojstnega dneva, pojav pa se s pridom uporablja v kriptografiji pri nakljucnem razvozlavanju šifriranih sporocil.
Bralec se lahko za konec pozabava z naslednjim problemom. Recimo, da ljudje vstopajo v sobo eden za drugim. Za katero osebo po vrsti bo najvecja verjetnost, da je prvi od ljudi, ki so vstopili, in ima rojstni dan na isti dan kot nekdo, ki je že v sobi?
Literatura
[1] Dragoljub M. Miloševic, prevod Peter Šemrl, Dirichletov princip, Presek 14 (1986/1987), 2, 110-111.
_ XXX
n
20
40
60
80
100
10
PRESEK 45 (2017/2018) 1