ISSN 0351-6652 Letnik 29 (2001/2002) Številka 1 Strani 4-11
Jože Grasselli: PREDALČNO NAČELO
Ključne besede: matematika, teorija števil, porazdelitve, deljivost. Elektronska verzija: http://www.presek.si/29/1467-Grasselli.pdf
© 2001 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
PREDALČNO NAČELO
Jakob ima v dveh žepih vsega tri jabolka. Ob tem edinem podatku lahko samo ugibamo, koliko jabolk je v posameznem od obeh Jakobovih žepov. Nekaj trdnega pa vendarle lahko izjavimo. Zapišimo vse načine, kako se dajo porazdeliti tri jabolka na dva žepa. Dobimo preglednico:
število jabolk v prvem žepu	število jabolk v drugem žepu
3	0
2	1
1	2
0	3
V prvih dveh primerih sta v prvem žepu vsaj dve jabolki; v zadnjih dveh primerih velja isto za drugi žep. Zato drži; Jakob ima v enem od obeh žepov najmanj dve jabolki; ne vemo pa, ali gre za prvi ali drugi žep.
Iz obravnavanega zgleda povzamemo predalčno načelo: če so v dveh predalih (žepih) tri reči (jabolka), vsebuje eden od obeh predalov (žepov) vsaj dve reči (jabolki).
Imejmo sedaj namesto dveh žepov n predalov in namesto treh jabolk n + 1 reči. Splošno predalčno načelo pravi: Če je v n predalih n + 1 ali več reči, vsebuje vsaj en predal najmanj dve od teh reči.
Načelo je jasno; ako bi bila v vsakem predalu le ena reč, bi bilo v n predalih le h ne pa. n + 1 ali več reči. Spet pa ne verno, v katerem od n predalov sta vsaj dve reči.
Predalčno načelo se v matematiki večkrat uporablja. Tu bomo z njim izpeljali nekaj trditev.
A. Naj bo naravno število a tuje praštevilu p\ obstaja potenca ak, 1 < k < p - 1. ki pušča pri delitvi s p ostanek 1.
Če katerokoli celo število delimo s p, dobimo za. ostanek eno od števil 0.1, 2,... ,p— 1; ostanek 0 se pojavi le, če je število a deljivo s p; če dajeta števili pri delitvi s p isti ostanek, je njuna razlika deljiva s p. Ker je a tuj p, je vsaka, od potenc
a,a2,a3,...,ap	(1)
tuja p in ni deljiva s p. Zato se ostanki, ko delimo potence (1) s p, nahajajo med števili 1, 2,. . . ,p— 1. Števil (veci) v (1) je p, možnih ostankov
(predalov) p — 1. Po predalčnem načelu sta med potencami (1) potenci aJ, a' z eksponentoma
1 < s< i	(2)
ki pri delitvi s p puščata enak ostanek. Njuna razlika
a1 ~ a* = a* (a'"8 - l)
je zato deljiva s p. Ker je p tuj os, mora deliti ai-iI — 1. To pomeni, da pri celem številu m velja
ai-s - 1 = mp.
Eksponent t — s = k je zaradi (2} naravno število in največ p — L Zadnja enakost se zapiše tudi
ak = mp + 1
in trditev A je dognana. Zgled.
Naj bo a — 8, p = 13. S potenciranjem ugotovimo, da tri od potenc 8J', 1 < j < 13
dajejo pri delitvi a 13 ostanek 1. To so
84 = 4 096 = 315-13 + 1
88 - 16 776 216 - 1 290 555 13+ 1	(3)
812 = 68 719476 736 = 5 286113 595- 13 + 1
Pri a = 14, p = 17 od potenc
14j , 1 < j < 17
šele predzadnja daje pri delitvi s 17 ostanek 1; je namreč
1416 = 2 197 953 337809371 136 = 128114 224 080 655 • 17 + 1. (4)
Opomba.
Trditev A se da takole dopolniti: Najmanjši naraven k, pri katerem daje potenca ak pri delitvi s p ostanek 1, je delitelj števila p — 1, vsi drugi takšni k so večkratniki tega delitelja. Dokaz izpuščamo, ponazoritev dopolnitve je vidna v (3) in (4).
B.	Naravni števili a, n naj bosta večji od 1 in o tuj številu 10. Obstaja potenca ak, ki ima za zadnjo števko 1, pred njo pa n — 1 št-evk enakih 0.
Ravnamo podobno kot pri A. Zaradi tujosti števil a in 10 se delitev potenc
a, a2, a3,..., a10	(5)
z 10* nikoli ne izide; za ostanke so tako možnosti 1,2,3,..., 10" — 1. Potenc {5} je 10", možnih ostankov 10" — 1; po predalčnem načelu dajeta vsaj dve potenci iz (5) pri delitvi z 10" isti ostanek, npr. potenci a",a1, s < t. Razlika
a' ~as = aa{at~s -l)
je potem deljiva z 10". Faktor a3 je tuj 10", zato 10" deli faktor ak — 1, kjer je k = t — s naravno število. Zato je ak — 1 = v • 10" pri naravnem številu v. Od tod je
ak = v ■ 10" + 1 = vO ... 01 in tu pred 1 nastopa n — 1 ničel. Trditev B je dobljena. Zgled.
Vzemimo a = 3, n = 2. Z računanjem zaporednih potenc 3,32,33,. • • najdemo, da je
320 = 3 486 784 401
najmanjša potenca števila 3, ki se končuje na 01. Na 001 se končuje šele 3100
Opomba.
Najmanjši eksponent k za katerega drži trditev B, je delitelj števila 4 10"_1. Dokaz spet izpuščamo, ponazoritev nudi zadnji zgled.
Naj bo a naravno število. Naravno število c, ki se začenja z nekajkrat zapored zapisanim a in se končuje z nekaj ničlami, zapišemo
c = a... ttO... 0.	(6)
Ce je a = 37, je npr. c = 37 373 700; tu se 37 ponovi trikrat, na koncu sta dve števki 0.
C.	Naj bosta u, b naravni števili; obstaja število, ki ima obliko (6) in je deljivo z b.
Glejmo 6 + 1 števil
a, aa, aaa,..., aaa... a ,	(7)
ki nastanejo, ko zapišemo a enkrat, dvakrat, b+ 1-krat zapored. Ko števila iz seznama (7) delimo z b, so mogoči ostanki 0,1,2,. ..,6 — 1. Števil (7) je b + 1, za ostanek je b možnosti; po predalčnem načelu sta v (7) najmanj dve števili y, x, ki dajeta isti ostanek pri delitvi z b; ker sta y, x različna, naj bo y > x, Razlika y — x je zato naravno število deljivo z t»; razlika ima tudi obliko (6), saj se y končuje z Trditev C je dobljena.
Zgled.
Po iščimo pri a — 17 najmanjše število z zapisom (6), ki je deljivo z b = 84. Iskano število se končuje na n ničel in ga zato zapišemo
17... 17-10" .	(8)
Ker je 84 = 4 • 21, mora biti število (8) deljivo s 4 in z 21. Prvi faktor v (8) je lih in torej tuj 4; zato mora 4 deliti drugi faktor 10". Najmanjši eksponent ?i, pri katerem to velja, je 2. Ker je 21 tuj 10" , mora deliti prvi faktor v (8); s preizkusom preverimo, da 17 in 1 717 nista deljiva z 21, pač pa 21 deli 171 717. Iskano število je
17171 700 = 84-204 425.
Če številu 17171 700 pritaknemo nekaj ničel ali spredaj pripišemo nekajkrat skupino števk 171 717, so dobljena števila še zmeraj deljiva s 84. Števil oblike (6), deljivih s 84, je tako neskončno mnogo.
Č. Če izmed zaporednih naravnih števil,
1,2,3,... ,2« — 1,2n, n>2	(9)
izberemo n + 1 števil, sta med njimi vsaj dve zaporedni.
Iz zaporedja (9) izbrana števila
«i < a? < ■ ■ ■ < a„ < o« n sestavljajo množico M; seveda je
Števila množice M razdelimo na dva razreda. Število x iz M je v prvem razredu M i, če je vsaj eno od števil x-l,i+lvAi, inv drugem razredu Mi, če nobeno od števil x — 1, x + 1 ni v M. Jasno je. da vsako število iz M pade ravno v enega od obeh razredov Mi, Mt- Ker je n > 2, je n + 1 > 3; tako so v dveh razredih vsaj tri števila. Zato po predalčnem načelu vsaj eden od razredov Mi, M2 vsebuje vsaj dve števili zaporedja (9). Pokažimo, daje to razred M\. Razred A'l> bi lahko zajel največ vsa liha števila
1,3,5,.. ,,2n~ 1 ah pa največ vsa soda števila
2,4,6,... ,2n.
Obakrat je to največ n števil in je potem v Mi vsaj eno število x. Če pa je x v Mi, je z njim v Mi vsaj eno od števil x — 1, x + 1; če Jb to X — 1, sta x — 1., X zaporedni naravni števili; za x + 1 sta x, x + 1 zaporedna. Trditev Č je dobljena.
Opomba.
Zaporedni naravni števili sta zmeraj tuji. Ugotovitev Č torej pove, da sta med n + 1 števili, vzetimi iz zaporedja (9), vsaj dve tuji števili.
Zgled.
Pri n — 2 premore množica (9) števila
1,2,3,4.
Množico M sestavljajo tri izmed teh štirih števil; vse možnosti za M so tako
1.2.3
1.2.4 1,3,4 2, 3,4
V drugem primeru je le en par zaporednih naravnih števil, namreč 1, 2; tudi v tretjem primeru je en sam tak par 3, 4: v prvem primeru sta para dva, namreč 1, 2 in 2, 3; prav tako sta v zadnjem primeru dva para 2, 3 in 3, 4. Ko n narašča, se število možnosti za M hitro veča. Pri = 6 vsebuje množica (9) števila
1,2,3,4,5,6,7,8,9,10,11,12
in izmed njih je možno izbrati 7 števil na 792 različnih načinov. Toliko je sedaj možnosti za M: neposredno preveriti trditev C tu ni prav lahko.
Znameniti matematik Paul Erdoa (1913 199G) je mladim nadebudnim matematikom rad zastavljal nalogo, naj dokažejo trditev:
D. Če izmed števil
1,2,3,...,2n	(10)
izberemo n + 1 števil, sta med njimi vsaj dve takšni, da manjše deli večje.
Vsako izmed n + 1 izbranih števil se da pisati v obliki
2kz,	(11)
kjer je k nič ali naravno število, z pa liho naravno število. (Npr. 240 = = 24 - 15, 35 = 2° ■ 35.) Med števili v (10) je n lihih
1,3,5,..., 2n - 1.
Za z v izrazitvi (11) je tako največ n možnosti. Izbrani števili damo v isti razred, če imata v zapisu (11) enak Ker je izbranih števil n + 1, možnosti za z pa kvečjemu n, imata od izbranih števil vsaj dve enak 2 in padeta v isti razred. To sta npr. števili x, y; ker sta različni, smemo vzeti x < y. Torej je
x — 2sz , y = 2lz pri 0 < s < t. Ker je | — 2i_J1, z: deli y. Trditev D je dognana. Zgled.
Za n = 3 sestavljajo množico (10) števila
1,2,3,4,5,6.
Izmed njih je mogoče izbrati štiri različna števila na 15 načinov. Med izbranimi četvericami so npr.
2.3.4.5
3.4.5.6 2,3,5,6
V prvi četverici le 2 deli 4, v drogi le 3 deli 6; v teh dveh četvericah sta v vsaki le dve takšni števili, da manjše deli večje. V tretji četverici 2 deli 6 in 3 deli 6; tu imamo dva para števil, ko manjše deli večje.
E. Množica A/, ki jo sestavlja n -f 1 različnih naravnih števil, manjših od 2rj. vsebuje vsaj eno število, ki je vsota dveh (različnih) števil iz M.
V množici M je n + 1 naravnih števil
cti < CL2 < .. . < an < ,	(12)
ki so pod 2n; zato je
1 < «i, an+1 < 2n - 1.	(13)
Zaradi (12) so razlike
0-2 - «1 , «3 - Ol 7 - - - > «n+l - «1	(14)
različna naravna števila in naraščajo; po (13) je zadnja, največja diferenca pod 2ji,- V množicah (12) in (14) je skupaj 2n 4- 1 naravnih števil, ki so vsa pod 2n; to pomeni, da so zanje možne le vrednosti 1.2,..., 2n — l. Ker je števil 2n + 1, razpoložljivih vrednosti zanje pa 2n — 1, imata po predalčnem načelu vsaj dve števili, npr. u, v, isto vrednost it — v. V (12) so sama različna števila, prav tako v (14); od enakih števil u, v mora zato eno biti v množici (12), drugo v množici (14). Je npr. u = a;, v = aj — aj.; zaradi u = v je aj = a, + Oi in števila a i, a,;, aj so iz M. Trditev E je dobljena.
ZgJed.
Pri n = 4 so pod 8 naravna števila 1,2,3,4,5,6,7; izmed njih je mogoče 5 števil izbrati na 21 načinov; toliko je možnosti za M. Ena od možnosti za M, tj, (12), je
3<4<5<6<7.
Tu je 3 + 4 = 7 in nobeno drugo od števil 4,5, 6, 7 iz M ni vsota dveh različnih števil iz M. Ce se za, M vzame števila
1<2<3<5<6,
je 1 + 2 = 3, 1 + 5 = 6, 2 + 3 = 5 in tri števila, iz M so vsote dveh različnih števil iz M.
Včasih srečamo predalčno načelo v se bolj splošni obliki:
Če je kn + 1 reči razporejenih v n predalov, vsebnje vsaj en predal najmanj k + 1 teh reči.
Tudi to je jasno. Ko bi vsak od n predalov vseboval največ k reči, bi bilo v vseh predalih največ kn Teči; ne gre, saj je reči kn + 1.
F. Na gredo, ki ima obliko kvadrata s stranico 1 m. je posejal vrtnar 301 seme. Na gredi se najde krog s polmerom 8 cm. v katerega so padla vsaj štiri semena. (Seme vzamemo kot točko.)
Kvadratno gredo razdelimo z vzporednicami stranicam na 100 enakih kvadratkov, stranica vsakega meri 1 dm. Ker je 301 = 3 ■ 100 + 1, je k = = 3, n — 100. Po predalčnem načelu obstaja vsaj en kvadratek ki vsebuje najmanj A; + l = 3 + 1 = 4 semena. V krogu, ki je temu kvadratku očrtan, ta semena še tem bolj gotovo ležijo. Premer kroga 2r je enak diagonali kvadratka; torej je 2r — \/2 dm in
r = — dm = 0,707... dm < 8 cm . 2
Trditev F je dognana.
Kdaj pa kdaj naletimo tudi na tole obliko predalčnega načela:
Če je v n predalih manj kot n reči. je vsaj en predal brez teh reči.
C. V pravokotni gozdni parceli, dolgi 30 km in široki 20 km, se zadržuje 49 medvedov, njihov stalež se s časom ue spreminja. V vsakem trenutku je na parceli pravokotno območje površine 12 kun'2, na katerem ni nobenega medveda.
Težišče vsakega medveda projiciramo pravokotno na parcelo in dobimo s tem na njej 4i) točk. Parcela meri €¡00 km2; razdelimo jo z vzporednicami stranicam na 50 pravokotnih parcelic dolžine 6 km in širine 2 km; torej meri parcelica 12 km2. Ker je parcelic 50, medvedov pa 4!J, vsaj na eni od parcelic ni nobenega medveda. (S tem pa še ne vemo, katera od parcelic je v izbranem trenutku "varna").
Jože Grasselli