Vesti
PETNAJSTO MEDNARODNO TEKMOVANJE
ˇ
STUDENTOV MATEMATIKE
Kot ˇ ze vrsto let se je tudi v letu 2008 ekipa Fakultete za matematiko in
fiziko udeleˇ zila mednarodnega tekmovanja ˇ studentov matematike. Tokrat
so se s ˇ studenti z vsega sveta pomerili
ˇ
Spela
ˇ
Spenko iz drugega letnika,
Sara Kaliˇ snik iz tretjega letnika ter Kris Stopar in Nik Stopar iz ˇ cetrtega
letnika. Prviˇ c je svojega zastopnika na to tekmovanje poslala tudi Univerza
na Primorskem, ˇ studenta prvega letnika Petra Murˇ siˇ ca.
Tekmovanje je tudi letos zraslo, tako po ˇ stevilu sodelujoˇ cih drˇ zav kot
po ˇ stevilu ˇ studentov; kar 283 ˇ studentov je zastopalo 90 razliˇ cnih univerz.
Mnoge univerze pripeljejo dokaj ˇ stevilne ekipe, saj pravila, da vsaka uni-
verza tekmuje s ˇ stirimi ˇ studenti, ˇ ze nekaj let ni veˇ c. Tako je na primer iz
Zagreba priˇ slo kar enajst tekmovalcev. Uveljavlja se tudi rangiranje univerz
glede na najboljˇ se tri doseˇ zke, kar seveda favorizira ekipe z veˇ c ˇ studenti.
Naˇ se ekipe se vsako leto uvrˇ sˇ cajo nekako v zlato sredino. Tudi letos
je bilo tako.
ˇ
Spela
ˇ
Spenko in Nik Stopar sta osvojila tretjo nagrado, Sara
Kaliˇ snikinKrisStoparpapohvalo. PravtakojepohvalodobilPeterMurˇ siˇ c.
72 Obzornik mat. fiz. 56 (2009) 2

Petnajsto mednarodno tekmovanje študentov matematike
Glede na to, da mnoge univerze organizirajo posebne priprave ter izbore
tekmovalcev (mi pa ne), ta uspeh ni zanemarljiv. V posebnem toˇ ckovanju
univerz smo dosegli 34. mesto.
Poleg tekmovanja je velik poudarek na druˇ zenju ˇ studentov. Predsednik
ˇ zirije John E. Jayne je posebej pozval k preseganju dnevnih politiˇ cnih deli-
tev. Kot primer je navedel, da kljub temu da je Francija leta 1066 napadla
Anglijo, vseeno rad pokramlja s kakˇ snim Francozom. Vˇ studentskem domu
jebilovesˇ casˇ zivo,ˇ seposebejpodrugemtekmovalnemdnevu,koje(glasna)
zabavatrajalapoznovnoˇ c. Domaˇ cinisosicerrekli,daimajoodvsehgostov
ˇ se najraje nas matematike, ker jim naredimo najmanj ˇ skode na inventarju.
ˇ
Ce jezaˇ studentedobroposkrbljeno(oziromajimje omogoˇ ceno, da sami
dobro poskrbijo zase), je zgodba pri vodjih ekip deloma drugaˇ cna. Izbiranje
tekmovalnih nalog je zelo mukotrpen proces, pri katerem se pokaˇ zejo tudi
politiˇ cne delitve (na algebraike in analitike).
ˇ
Se slabˇ se je pri ocenjevanju
izdelkov, kjer ni dovolj nadzora nad samim procesom. Predsednik ˇ zirije
je recimo v dveh dneh ocenjevanja v dvorano vstopil le dvakrat, ko nas
je napodil spat in zaklenil vrata. Tega mu sicer nismo zamerili, saj se po
desetih urah ocenjevanja v dvorani brez sveˇ zega zraka pri veˇ c kot 35
◦
C
Obzornik mat. fiz. 56 (2009) 2 73

Vesti
prileˇ ze polurni sprehod po speˇ cem Blagoevgradu. Zaradi slabih razmer se
veliko vodij ekip temu delu odreˇ ce, kar nujno pomeni veˇ c zabave za tiste,
ki imajo dovolj ˇ cuta dolˇ znosti. Pisec teh vrstic je tako v dveh dneh imel
ˇ cast oceniti in skoordinirati ocene okoli 200 izdelkov. Presenetljivo (ali pa
morda tudi ne) so na koncu rezultati kar objektivni, vsaj tako je sploˇ sno
subjektivno mnenje udeleˇ zencev.
ˇ
Se nekaj besed o Blagoevgradu, kjer so tekmovanje gostili ˇ ze ˇ cetrtiˇ c.
Mesto je zagotovo eno lepˇ se urejenih v Bolgariji, za kar je delno zasluˇ zna
Ameriˇ ska univerza, ki ima tam sedeˇ z (v stavbi, kjer je pred leti imela se-
deˇ z komunistiˇ cna partija). Prav tako se pozna pritok evropskih sredstev,
najbolj oˇ citno na pred kratkim zgrajenih avtocestah. Kljub evropeizaciji se
ˇ zivljenjski utrip na sploˇ sno ni kaj dosti spremenil, nekateri bi ob tem verje-
tno omenjali polotok, na katerem leˇ zi Bolgarija in njene sosednje drˇ zave.
Leta 2009 bo tekmovanje v Budimpeˇ sti. Organizatorjem iz Minska, ki
je bil prvi kandidat, namreˇ c ni uspelo zagotoviti namestitve s tekoˇ co vodo.
Oblika tekmovanja je enaka vse od zaˇ cetka.
ˇ
Studenti dva dni po pet ur
reˇ sujejo po ˇ sest nalog. Vsak dan je prva naloga lahka in bi jo morali reˇ siti
res skoraj vsi, naslednje tri naj bi bile srednje teˇ zavnosti, zadnji dve pa sta
74 Obzornik mat. fiz. 56 (2009) 2

Petnajsto mednarodno tekmovanje študentov matematike
ponavadizeloteˇ zki. Letoskomisijiniuspelodobroocenititeˇ zavnostinalog,
ˇ studenti so imeli namreˇ c prvi dan obˇ cutek, kot da reˇ sujejo le pete in ˇ seste
naloge. Tako so bili rezultatiprvega dne skoraj katastrofalni– morda je kdo
pomislil, da bi test morali ponavljati. Drugi dan se je stanje normaliziralo.
Oglejmo si nekaj nalog skupaj z njihovimi reˇ sitvami. Naloge so oznaˇ cene
po dnevih in zaporednih ˇ stevilih. Tako je II.3. tretja naloga drugega dne
(in je bila verjetno najlaˇ zja med vsemi), II.1. je prva naloga drugega dne in
je prav tako lahka (a morda malce teˇ zja od prve predstavljene), I.6. pa je
zadnja naloga prvega dne in je teˇ zka. Tokrat je sicer kot najteˇ zja obveljala
naloga I.5., kjer je bil povpreˇ cen rezultat 0,2 toˇ cke od 20 moˇ znih. Vsi trije
zmagovalci so popolnoma reˇ sili 11 nalog, pri tej pa vsi dobili niˇ clo.
II.3. Naj bo n naravno ˇ stevilo. Dokaˇ zite, da je ˇ stevilo
X
0≤k<n/2

n
2k+1

5
k
deljivo z 2
n−1
.
Reˇ sitev.
ˇ
Ce srednjeˇ solec vidi nalogo z okvirnim besedilom
”
dokaˇ zite, da za
vsak n velja ...“, verjetno pomisli na indukcijo. V tem primeru to ni prava
pot. Bolje se je spomniti binomskega izreka
(a+b)
n
=
n
X
k=0

n
k

a
k
b
n−k
.
Kerpavizrazuvnalogimanjkajolihiˇ cleni,sejihmoramoznebiti. Zapiˇ semo
ˇ se
(−a+b)
n
=
n
X
k=0

n
k

(−1)
k
a
k
b
n−k
ter izraza odˇ stejemo, da dobimo
(a+b)
n
−(−a+b)
n
= 2
X
0≤k<n/2

n
2k+1

a
2k+1
b
n−2k−1
.
Da bi desna stran postala izraz iz naloge, ustrezno izberemo a in b.
(
√
5+1)
n
−(−
√
5+1)
n
= 2
√
5
X
0≤k<n/2

n
2k+1

5
k
Obzornik mat. fiz. 56 (2009) 2 75

Vesti
oziroma
X
0≤k<n/2

n
2k+1

5
k
=
(1+
√
5)
n
−(1−
√
5)
n
2
√
5
.
Dobljeniizraznasmoraspomnitinasploˇ sniˇ clenFibonaccijevegazaporedja.
Velja namreˇ c, da ima rekurzivno podano zaporedje F
n
= F
n−1
+ F
n−2
z
zaˇ cetnima ˇ clenoma F
1
=F
2
= 1 sploˇ sni ˇ clen enak
F
n
=

1+
√
5
2

n
−

1−
√
5
2

n
√
5
.
Tako velja
X
0≤k<n/2

n
2k+1

5
k
= 2
n−1
F
n
in naloga je reˇ sena.
II.1. Dokaˇ zite, da ˇ ce za celi pozitivni ˇ stevili k in n polinom x
2k
−x
k
+1
deli polinom x
2n
+ x
n
+ 1, tudi polinom x
2k
+ x
k
+ 1 deli polinom
x
2n
+x
n
+1.
Reˇ sitev. Ker vsak polinom lahko zapiˇ semo kot produkt linearnih polinomov
(nekateri med njimi so seveda lahko kompleksni), polinom h deli polinom
g, ˇ ce je vsaka kompleksna niˇ cla polinoma h hkrati tudi niˇ cla polinoma g.
Tako naloga pravzaprav zahteva, da doloˇ cimo (nekatere) niˇ cle navedenih
polinomov. Oznaˇ cimo f(x) = x
2n
+x
n
+1, g(x) = x
2k
−x
k
+1 in h(x) =
x
2k
+x
k
+1. Dokazati moramo, da ˇ ce je vsaka niˇ cla polinoma g tudi niˇ cla
f, so potem tudi niˇ cle h niˇ cle f. Poti do reˇ sitve je seveda veˇ c. Predstavimo
zanimivo reˇ sitev, ki uporabi le eno niˇ clo polinoma g(x). Lahko bi tudi
okarakterizirali vse niˇ cle vseh treh polinomov in jih primerjali med seboj ali
pa poiskali vse pare celihˇ stevil k in n, za katere g deli f, ter tiste pare k in
n, za katere h deli f, ter spet izvedli primerjavo. A dela bi bilo tako veˇ c.
Ker imajo opazovani polinomi precej kompleksnih niˇ cel, bo potrebnega
nekaj raˇ cunanja s kompleksnimi ˇ stevili. Izkaˇ ze se, da je za zaˇ cetek dovolj
poiskati eno niˇ clo polinoma g(x). Opazimo, da je g(x)(x
k
+1) = x
3k
+1.
Niˇ cle polinoma g(x) so torej reˇ sitve enaˇ cbe x
3k
+1 = 0, ki niso hkrati tudi
reˇ sitvex
k
+1 = 0. Recimo,x
1
= cos
π
3k
+isin
π
3k
jeenaizmedniˇ celpolinoma
g(x). Naj bo α =
nπ
3k
. Ker g(x) deli f(x), je x
1
niˇ cla polinoma f(x). Tako
velja
0 =x
2n
1
+x
n
1
+1 = (cos(2α)+isin(2α))+(cosα+isinα)+1.
76 Obzornik mat. fiz. 56 (2009) 2

Petnajsto mednarodno tekmovanje študentov matematike
Kerjecos(2α) = cos
2
α−sin
2
α,sin(2α) = 2sinαcosαin1 = cos
2
α+sin
2
α,
lahko zgornji izraz razstavimo:
(cos
2
α − sin
2
α+2isinαcosα)+(cosα+isinα)+cos
2
α+sin
2
α =
= 2cos
2
α+2isinαcosα+(cosα+isinα) =
= (2cosα+1)(cosα+isinα).
Ker drugi faktor ne more biti enak 0, sledi, da je 2cos(α)+1 = 0. Zaklju-
ˇ cimo, da je α =±
2π
3
+2πc za neko celo ˇ stevilo c.
Izberimo sedaj eno izmed niˇ cel polinoma h(x) in jo oznaˇ cimo z x
0
. Po-
dobno kot za polinomg za h velja, da je h(x)(x
k
−1) =x
3k
−1, kar pomeni,
da je x
0
= cos
2πs
3k
+isin
2πs
3k
za s = 3t±1, t∈Z. Izraˇ cunajmo sedaj f(x
0
).
Velja
f(x
0
) = x
2n
0
+x
n
0
+1 = cos(4sα)+isin(4sα)+cos(2sα)+isin(2sα)+1 =
= cos
2
(2sα)−sin
2
(2sα)+2isin(2sα)cos(2sα)+
+cos(2sα)+isin(2sα)+cos
2
(2sα)+sin
2
(2sα) =
= 2cos
2
(2sα)+cos(2sα)+2isin(2sα)cos(2sα)+isin(2sα) =
= (2cos(2sα)+1)(cos(2sα)+isin(2sα)).
Sedaj doloˇ cimo vrednost prvega faktorja:
2cos(2sα)+1 = 2cos

2s

±
2π
3
+2πc

+1 = 2cos
4sπ
3
+1 =
= 2cos
4(3t±1)π
3
+1 = 2cos
4π
3
+1 = 2

−
1
2

+1 = 0.
Tako je f(x
0
) = 0 oziroma vsaka niˇ cla polinoma h(x) je hkrati tudi niˇ cla
polinoma f(x), to pa smo ˇ zeleli dokazati.
Mimogrede, obratnatrditevnevelja, sajlahkovzamemon =k inpotem
hdelif, g pane. Trditevneveljaniti,ˇ ceseomejimonak <n, sajjerecimo
x
10
+x
5
+1 =

x
2
+x+1


x
8
−x
7
+x
5
−x
4
+x
3
−x+1


.
I.6. Za permutacijoσˇ stevil 1, 2, ..., n definiramoD(σ) =
n
P
k=1
|σ(k)−k|. S
Q(n,d) oznaˇ cimoˇ stevilo permutacij σ ˇ stevil od 1 do n, za katere velja
D(σ) =d. Dokaˇ zite, da je za d≥ 2n ˇ stevilo Q(n,d) sodo.
Obzornik mat. fiz. 56 (2009) 2 77

Vesti
Reˇ sitev. Kotsespodobizareˇ sitevteˇ zkenaloge,zaˇ cnemozobjekti,kinaprvi
pogled nimajo zveze z nalogo. Tokrat je to determinanta, ki jo oznaˇ cimo z
Δ(x) =









1 x ··· x
n−1
x 1 ··· x
n−2
.
.
.
.
.
.
.
.
.
.
.
.
x
n−1
x
n−2
... 1









.
Naij-temmestuvmatrikijeelementx
|i−j|
. Koraˇ cunamoΔ(x)podefiniciji
determinante, dobimo
Δ(x) =
X
σ∈Sn
(−1)
sgn(σ)
x
D(σ)
, (1)
kjerjeS
n
mnoˇ zicavsehpermutacijnelementov,sgn(σ)papredznakpermu-
tacije.
ˇ
Clen x
D(σ)
dobimo kot produkt
n
Q
k=1
x
|σ(k)−k|
in s tem vidimo zvezo
med Δ in D.
Recimo, da je Q(n,d) sodo ˇ stevilo. To pomeni, da v vsoti (1) ˇ clen
x
d
nastopa sodokrat, nekajkrat pomnoˇ zen s +1 in nekajkrat z −1. Vsota
koeficientovjevvsakemprimerusoda. Podobnorazmislimo, daˇ cejeˇ stevilo
Q(n,d)liho,jetudikoeficientprix
d
vΔ(x)lih. Takomoramozadokonˇ canje
naloge dokazati, da je za d≥ 2n koeficient pri x
d
v Δ(x) sod.
Izraˇ cunajmo Δ(x). V ta namen vsaki (razen prvi) vrstici matrike odˇ ste-
jemo x-krat prejˇ snjo vrstico. Tako dobimo matriko, ki ima pod diagonalo
same niˇ cle:
Δ(x) =











1 x ··· x
n−2
x
n−1
0 1−x
2
··· x
n−3
−x
n−1
x
n−2
−x
n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 ... 1−x
2
x−x
3
0 0 ··· 0 1−x
2











=

1−x
2


n−1
.
Koeficienti pri x
d
so za d ≥ 2n− 1 enaki 0 in so sodi, torej je sodo tudi
ˇ stevilo Q(n,d).
Lepota tega tekmovanjaje tudi v tem, daˇ studentivedno najdejo kakˇ sno
alternativno reˇ sitev. Tudi v tem primeru je bilo tako, a uradna reˇ sitev,
predstavljena tu, je nekajkrat krajˇ sa od ˇ ciste kombinatoriˇ cne reˇ sitve.
Kot zanimivost naj navedem ˇ se najteˇ zjo nalogo skupaj z njeno
”
reˇ si-
tvijo“.
78 Obzornik mat. fiz. 56 (2009) 2