
P51(2023/2024)1
8
Mednarodna matematiˇ cna
olimpijada 2023 na Japonskem
L H
Med 2. in 13. julijem je v Chibi na Japonskem
potekala 64. Mednarodna matematiˇ cna olimpijada.
Slovensko ekipo so na tekmovanju zastopali Erik
ˇ
CervekRoškariˇ c(II.gimnazijaMaribor), LenartDo-
linar (Gimnazija Bežigrad), Katarina Grilj (Srednja
šola Slovenska Bistrica), Kaja Rajter (II. gimnazija
Maribor), Matija Skrt (Gimnazija Nova Gorica) in
Hugo Trebše (Gimnazija Bežigrad). Tekmovalce
sva na olimpijadi spremljala Gregor Dolinar in
Luka Horjak.
MatijaSkrtjeponovilsvojlanskidosežekinznova
osvojil bronasto medaljo. Tokrat se z Japonskega
pravvsinašitekmovalcivraˇ cajospohvalo,kijoprej-
mejo tisti udeleženci, ki v celoti pravilno rešijo vsaj
eno izmed šestih zahtevnih nalog. Slovenija je med
112 sodelujoˇ cimi državami zasedla 64. mesto. Prvo
mesto je že petiˇ c zapored osvojila Kitajska – edina
država, ki si je letos prislužila 6 zlatih medalj, sle-
dile pa so ji ZDA, Južna Koreja in na 4. mestu še
Romunija, ki je bila najuspešnejša med evropskimi
državami.
Na olimpijadi sta tekmovalce ˇ cakala dva tekmo-
valna dneva. Vsak dan so imeli 4 ure in pol ˇ casa za
reševanje treh zahtevnih nalog. Te nekaj mesecev
pred tekmovanjem predlagajo države, ki ne gostijo
tekmovanja, organizator pa je zadolžen za sestavo
komisije, kiizmedtehizberejonajprimernejše, ska-
terimi sestavijo ožji izbor. Letos je 52 držav skupaj
predlagalo 167 nalog, izmed teh jih je v ožji izbor
prišlo 30. Izmed teh nekaj dni pred samim tekmo-
vanjem vodje ekip glasujejo za 6 problemov, ki se
nato pojavijo na tekmovanju. O njihovi težavnosti
priˇ ca dejstvo, da je vseh 42 možnih toˇ ck doseglo le
5 izmed 618 tekmovalcev, povpreˇ cno število toˇ ck pa
je bilo 17,7. Da si bomo te izzive lažje predstavljali,
si oglejmo dve nalogi s tekmovanja in njuni rešitvi.
Nalogi sta predlagali Kolumbija in Nizozemska.
SLIKA1.
Slovenska ekipa na 64. Mednarodni matematiˇ cni olimpijadi
Naloga 1. Doloˇ ci vsa sestavljena naravna števila
n > 1, ki imajo naslednjo lastnost: ˇ ce so d
1
, d
2
, ...,
d
k
vsi pozitivni delitelji števila n, pri ˇ cemer je 1 =
d
1
< d
2
< ··· < d
k
= n, potem d
i
deli d
i+1
+d
i+2
za vsak 16i6k−2.
Rešitev 1. naloge Da razvijemo intuicijo, katera na-
ravna števila sploh rešijo nalogo, si oglejmo nekaj
posebnih primerov. Pogosta strategija je vstavljanje
konkretnih vrednosti, na primern= 12, lahko pa se
tega lotimo splošneje. Oglejmo si najprej števila, ki
imajo zelo malo deliteljev. Ker naloga sprašuje le o
sestavljenih številih, zaˇ cnimo s primerom n = pq,
kjer stap inq praštevili.
ˇ
Ce veljap<q, se lahko hitro prepriˇ camo, da so 1,
p,q inpq kar vsi delitelji številan, poleg tega pa so
še urejeni po velikosti. Tako mora veljati
1|p+q in p|q+pq.
Prva deljivost oˇ citno vedno velja, pri drugi pa nale-
timo na težavo, saj mora veljati p | q. To seveda


P51(2023/2024)1
9
ne velja, saj smo predpostavili, da stap inq razliˇ cni
praštevili.
Majhno število deliteljev dobimo tudi v primeru
p=q oziroman=p
2
, kjer jep praštevilo. Vsi deli-
telji števila n so tako kar 1, p in p
2
. Ni težko videti,
da je v tem primeru pogoj z deljivostjo izpolnjen,
zato kvadrati praštevil izpolnijo dan pogoj.
Napodlagiprimeran=pqsezdi,daimajoiskana
naravna številan najveˇ c enega praštevilskega delite-
lja, oziroma, da so to natanko potence praštevil. Ta
sum lahko dodatno potrdimo z dejstvom, da vse po-
tencepraštevilresizpolnijodanpogoj.
ˇ
Cejen=p
ℓ
,
so namreˇ c vsi delitelji kar 1, p, p
2
, ..., p
ℓ
. Pogoj je
tako ekvivalenten
p
i
|p
i+1
+p
i+2
za vse 06i6ℓ−2, kar seveda drži.
Sedaj predpostavimo, da ima n vsaj dva razliˇ cna
praštevilska delitelja. Naj bosta p,q, kjer je p < q,
njegova najmanjša praštevilska delitelja. Za delitelje
števila n torej velja d
1
= 1, d
2
=p, za d
3
pa imamo
2 možnosti – lahko veljad
3
=q, ali pad
3
=p
2
.
Obravnavajmonajprejprimer,kojed
3
=q. Vtem
primeru mora veljati deljivost
p|q+d
4
.
Za primerno izbiro delitelja d
4
bi ta deljivost lahko
bila izpolnjena. To nam celo zagotavlja Dirichletov
izrek, ki pravi, da za vsaki tuji si naravni števili a in
b obstajaneskonˇ cnomnogoprašteviloblikeak+b.
4
Dovolj je namreˇ c najti praštevilo obliked
4
=kp−q,
kiobstajapoDirichletovemizreku. Izreksicerneza-
gotavlja,dabopritemševednoizpolnjenaurejenost
deliteljev, nam pa pove, da ne bomo prišli do proti-
slovja na elementaren naˇ cin. Z najmanjšimi delitelji
tako ne bomo prišli prav daleˇ c.
Drugiekstremsonajveˇ cjideliteljištevilan. Znano
je, da delitelji naravnih števil nastopajo v parih – ˇ ce
je d delitelj števila n, je to tudi
n
d
. S tem predpisom
se najmanjši delitelji preslikajo v najveˇ cje. Najveˇ cji
delitelji števila n so torej n,
n
p
in
n
q
. Sledi, da mora
veljati
n
q





n
p
+n,
4
Pri tem je številob lahko tudi negativno.
kar je ekvivalentno
n
p
+n
n
q
=
q
p
+q∈N.
To seveda ni mogoˇ ce, saj sta p in q razliˇ cni prašte-
vili.
Preostane nam še primer, ko je d
3
= p
2
. V tem
primeru so najmanjši delitelji števila n po vrsti 1,
p, p
2
, ..., p
ℓ
in q. Tudi tu lahko hitro pridemo do
protislovja, in sicer z zaporednimi delitelji p
ℓ−1
, p
ℓ
in q ali pa
n
q
,
n
p
ℓ
in
n
p
ℓ−1
. Pogoj tako res izpolnijo
natanko potence praštevil.
Naloga 5. Naj bo n naravno število. Japonski triko-
tnik je sestavljen iz 1+2+···+n krogov, ki so raz-
porejeni v obliki enakostraniˇ cnega trikotnika, tako
da je za vsak i = 1,2,...,n v i-ti vrstici natanko i
krogov in je v vsaki vrstici natanko en krog pobar-
van rdeˇ ce. Nindževa pot v japonskem trikotniku je
zaporedjenkrogov,kisezaˇ cnevkroguvnajvišjivr-
stici,natopaseponavljajoˇ cenadaljujeiztrenutnega
kroga v enega izmed krogov, ki sta neposredno pod
njim, in se konˇ ca v najnižji vrstici. V odvisnosti od
n poišˇ ci najveˇ cji k, tako da za vsak japonski triko-
tnik obstaja nindževa pot, ki vsebuje vsaj k rdeˇ cih
krogov.
SLIKA2.
Primer nindževe poti zan=6, ki vsebuje 2 rdeˇ ca kroga
Rešitev 5. naloge Za zaˇ cetek si oglejmo, kaj se zgo-
di za majhne vrednosti številan. Ni težko videti, da
pri n= 1 vedno dobimo nindževo pot dolžine 1, pri
n = 2 pa pot dolžine 2. Podobno za n = 3 dobimo
pot dolžine 2.
Nadaljnje konstrukcije lahko poišˇ cemo rekurziv-
no. Intuitivno bi želeli v zaporednih vrsticah imeti


P51(2023/2024)1
10
rdeˇ ce kroge ˇ cim bližje, a ne tako blizu, da bi lahko
nindževa pot vsebovala oba. Tako lahko zaˇ cnemo
z rdeˇ cim krogom skrajno levo, v vsaki naslednji vr-
stici pa pozicijo rdeˇ cega trikotnika poveˇ camo za 2.
Tako dobimo nekakšne »diagonale«, ki jih vidimo na
sliki 3.
SLIKA3.
Japonski trikotnik, ki nam da mejok6

log
2
(n)

+1
Opazimo, da lahko nindževa pot vsebuje kveˇ cje-
mu en rdeˇ c krog z vsake diagonale. Za omejitev šte-
vila k zadošˇ ca, da preštejemo te diagonale. Ni se
težko prepriˇ cati, da i-ta diagonala vsebuje 2
i−1
rde-
ˇ cih krogov (lahko tudi manj, ˇ ce vsebuje rdeˇ c krog v
zadnjivrstici).
ˇ
Cetrikotnikvsebujeℓ diagonal,mora
tako veljati
n62
0
+2
1
+···+2
ℓ−1
=2
ℓ
−1.
Ta neenakost je prviˇ c izpolnjena priℓ=

log
2
(n)

+
1. Tako dobimok6

log
2
(n)

+1.
Sedajmoramodokazatiše,davsakjaponskitriko-
tnik vsebuje nindževo pot z vsaj

log
2
(n)

+1 rde-
ˇ cimi krogi. Zaˇ cnimo tako, da v vsak krog v japon-
skem trikotniku zapišemo število, in sicer najveˇ cje
možno število rdeˇ cih krogov, ki so vsebovani v neki
poti od vrha trikotnika do tega kroga. Primer takega
oštevilˇ cenja lahko vidimo na sliki 4.
Sedajjedovoljpokazati,davzadnjivrsticiobstaja
krogsštevilomvsaj

log
2
(n)

+1. Sevedasejedovolj
omejiti na števila n= 2
m
, saj lahko vsako nindževo
pot razširimo do nindževe poti v veˇ cjem trikotniku.
Oglejmo si števila v dveh zaporednih vrsticah. Da
dobimo števila v novi vrstici, za vsak krog vzamemo
najveˇ cje število v njegovih dveh predhodnikih.
ˇ
Ce je
krog rdeˇ c, na koncu še prištejemo 1. Denimo, da so
v
1
, v
2
, ..., v
i
števila v i-ti vrstici, v
m
pa je najveˇ cje
izmed teh. Sledi, da so števila v vrstici i+ 1 veˇ cja
ali enaka odv
1
, v
2
, ...,v
m−1
,v
m
,v
m
,v
m+1
, ...,v
i
,
1
2 1
2 2 2
2 2 3 2
2 2 3 4 2
3 2 3 4 4 2
SLIKA4.
Oštevilˇ cenje trikotnika
priˇ cemeršenismoupoštevalirdeˇ cegakrogavvrstici
i+1.
Sedaj pridemo do naslednje pomembne ideje –
opazujemo lahko vsoto števil v vrstici. Veˇ cja kot bo
vsota, veˇ cja morajo namreˇ c biti števila v tej vrstici.
Po zgornji opazki je vsota števil v vrstici i+1 veˇ cja
ali enaka
v
1
+v
2
+···+v
i
+v
m
+1.
Sedaj zadošˇ ca dokazati, da je v vrstici n = 2
t
vsota
veˇ cja ali enaka t·n+1. Po Dirichletovem principu
bo namreˇ c sledilo, da obstaja krog s številom vsaj
t+1, kar je ravno naš cilj. To dokažimo z indukcijo.
Baza je seveda izpolnjena, saj je za t = 0 neenakost
trivialno izpolnjena.
Sedaj si oglejmo n = 2
t+1
. Vsota števil v vrstici
n
2
je po indukcijski predpostavki veˇ cja ali enaka t·
2
t
+ 1. V naslednji vrstici se vsota poveˇ ca za vsaj
v
m
+ 1, kjer je v
m
najveˇ cji element vrstice 2
t
. Po
Dirichletovem principu pa velja, da je
v
m
>
t·2
t
+1
2
t
>t,
zato je vsota naslednje vrstice enaka vsaj
t·2
t
+1+(t+1)+1.
Opazimo lahko še, da se najveˇ cji element z vsako
novo vrstico lahko kveˇ cjemu poveˇ ca. Tako je vsota v
zadnji vrstici enaka vsaj
t·2
t
+1+2
t
·(t+1)+2
t
·1=(t+1)·2
t+1
+1,
kar smo želeli dokazati.
×××