i i \Sega" | 2022/3/23 | 11:33 | page 32 | #1 i i i i i i VESTI Osemindvajseto mednarodno tekmovanje studentov matematike Zaradi razmer je bilo tekmovanje, ki je v preteklosti pogosto potekalo v Blagoevgradu v Bolgariji, lani izvedeno po vsem svetu. Med 2. in 8. avgu- stom so studenti iz celega sveta tekmovali, vsak v svoji dr zavi, nekateri kar doma. Iz Slovenije sta se tekmovanja udele zili dve ekipi. Fakulteto za ma- tematiko in ziko Univerze v Ljubljani so zastopali Luka Horjak iz prvega letnika, Matev z Mi s ci c iz drugega letnika, Andra z Maier in Zan Bajuk iz tretjega letnika ter Daniel Vitas in Tja z Silov sek, ki matematiko studirata cetrto leto. Fakulteto za matematiko, naravoslovje in informacijske tehno- logije Univerze na Primorskem pa so zastopali studenti Dorotea Red zepi in Lazar Markovi c iz prvega letnika, Ajla Sehovi c, Milan Milivoj cevi c in Todor Anti c iz drugega letnika in Besfort Shala, cetrto leto studija. Pravila tek- movanja namre c dolo cajo, da lahko tekmujejo vsi, ki niso starej si od 23 let ter so vklju ceni v studij najve c stiri leta. Prilagojena izvedba je dovoljevala nadzor bodisi zi cno v predavalnici bodisi prek ustreznega nadzornega ra- cunalni skega sistema. Na FMF smo se odlo cili za zi cno prisotnost, tako da je vseh sest tekmovalcev pisalo v predavalnici, na Famnitu pa so studentom omogo cili, da so pisali doma, nadzor pa je bil prek Zooma. Vodji ekip sva bila Gregor Sega in Slobodan Filipovski. V dvodnevnem re sevanju osmih nalog se je pomerilo 589 studentov, kar je najve c do sedaj. Razvr s ceni so bili v 113 ekip, med katerimi je bila najbolj Slika 1. Studenti Fakultete za matematiko in ziko prvi dan tekmovanja. 32 Obzornik mat. fiz.69 (2021) 1 i i \Sega" | 2022/3/23 | 11:33 | page 33 | #2 i i i i i i Osemindvajseto mednarodno tekmovanje študentov matematike Slika 2. Studenti FMF na za cetku drugega tekmovalnega dne. stevilna ekipa studentov brez ekipe. Obi cajno namre c univerzitetno ekipo sestavlja od tri do sest studentov, se pa na tekmovanje lahko prijavi vsak student, tudi ce njegova univerza ne sodeluje. Letos je bilo takih studen- tov kar precej, skoraj sto, in ker mora tudi za njih kdo poskrbeti (nadzor, prito zbe), so bili organizirani v ekipo. V ekipni razvrstitvi so univerze ran- girane po formuli »vsota najbolj sih treh tekmovalcev plus povpre cje vseh «. Kot zanimivost, ekipa studentov brez ekipe je imela tudi (vsaj) tri zelo do- bre tekmovalce, tako da je po omenjeni formuli, kljub kar nekaj studentom z ni clo (in pravzaprav stevilnim, ki so povpre cje zni zevali), dosegla celo trinajsto mesto. Letos so na si tekmovalci dosegli izjemen uspeh. Luka Horjak in Daniel Vitas sta dobila prvo nagrado, vsi drugi tekmovalci s FMF, torej Matev z Mi s ci c, Andra z Maier, Tja z Silov sek in Zan Bajuk ter Besfort Shala so dobili drugo nagrado, Todor Anti c in Dorotea Red zepi pa pohvalo. Ekipno smo dosegli devetnajsto (ekipa Fakultete za matematiko in ziko) ter stiriinosemdeseto mesto (ekipa Famnit). Ker tekmovanje ni potekalo na eni lokaciji, je ves spremljevalni dru zabni program odpadel. Tekmovanje na ta na cin izgubi precej svojega zna caja, po drugi strani pa je tudi vpliv mote cih elementov zmanj san. V dneh, ko so studenti re sevali naloge, se je temperatura v Blagoevgradu dvignila do 38 °C, kar v kombinaciji z neklimatiziranimi prostori lahko pomeni te zavo. Tudi dejstvo, da so ekipe za cenjale pisati ob razli cnih urah, ni bil problem, vsaj zaznaven ne. Na splo sno je bila letos odgovornost studentov na visokem nivoju, kar dokazuje ni c diskvaliciranih (lani jih je bilo nekaj, ob podobnem Obzornik mat. fiz.69 (2021) 1 33 i i \Sega" | 2022/3/23 | 11:33 | page 34 | #3 i i i i i i Vesti Slika 3. Studenti FMF med drugim tekmovalnim dnem. re zimu). Je pa bivanje v razli cnih casovnih pasovih bilo problem za komisijo, ko se je bilo treba uskladiti za ocene z ocenjevalcema z drugih strani planeta { vedno jih je kar nekaj spalo (tako smo morda dobili se prakti cen dokaz, da Zemlja res ni plo s cata). Otvoritvena slovesnost ter kon cna podelitev nagrad sta potekali po sple- tu, posnetka lahko najdete na strani tekmovanja (www.imc-math.org.uk) oziroma na YouTubu. To pa je bilo tudi vse, kar se ti ce dru zabnega zi- vljenja. Namesto da bi studenti v pri cakovanju rezultatov spoznavali druge tekmovalce, igrali nogomet, dru zabne igre, morda sli na bazen ali plezali po okoli skih hrib ckih (kar obi cajno po cnejo v Blagoevgradu), so na rezultate cakali doma. In tokrat so morali cakati kar dolgo, saj so bili tudi clani ko- misije doma in vpeti v normalen ritem zivljenja, namesto da bi cele dneve in no ci posvetili hitremu ocenjevanju izdelkov. Prav tako se nismo mogli izogniti za to leto obi cajnim dogodkom. Ena ekipa, ki je imela nadzor na daljavo, je pisanje tik pred za cetkom premaknila z dopoldneva na popoldan, ker je pri enem od tekmovalcev pri slo do pretrganja elektri cnega kabla. Eden izmed ocenjevalcev je kar naenkrat postal neodziven, naknadno smo ugoto- vili, da zaradi mo cne reakcije po cepljenju. In seveda, sredi ocenjevanja so izdelki postali nedostopni, ker smo presegli dovoljen dnevni promet podat- kov na stre zniku, kar je onemogo cilo oddajo prek obrazca tudi nekaterim studentom (med drugim tudi prej omenjeni ekipi). Oglejmo si se stiri naloge s tekmovanja ter nekaj njihovih re sitev. Pripo- ro cam, da posku sate naloge najprej re siti sami, nato pa pogledate namige in re sitve. 34 Obzornik mat. fiz.69 (2021) 1 i i \Sega" | 2022/3/23 | 11:33 | page 35 | #4 i i i i i i Osemindvajseto mednarodno tekmovanje študentov matematike Slika 4. Ekipa Fakultete za matematiko in ziko po zaklju cku drugega tekmovalnega dne. Pogosto so naloge sestavljene zelo dobro, tako da preverjajo razumevanje snovi in koncepte re sevanja matemati cnih nalog, oziroma ze razumevanje, kaj navodilo naloge sploh pomeni. Taka je bila tudi najla zja naloga obeh dni. Naloga 1. Naj bo A realna n n matrika, za katero velja A 3 = 0. (a) Doka zite, da ena cbo X +AX +XA 2 =A re si enoli cna realna n n matrika X. (b) Izrazite X z A. Re sitev. Navajeni smo, da se enoli cnost dokazuje na na cin, da predpo- stavimo dve re sitvi ter poka zemo, da sta enaki. V tem primeru naj torej poleg matrike X ena cbo re si tudi matrika Y . No, ta pot nas ne privede skoraj nikamor. Tako se za cnemo igrati in osnovno ena cbo mno zimo z raz- li cnimi potencami matrike A, v casih z leve, v casih z desne. Tako dobimo recimo A 2 (X +AX +XA 2 )A 2 =A 2 XA 2 +A 3 XA 2 +A 2 XA 4 =A 2 XA 2 : Upo stevamo seveda, da je A 3 = 0 in zato tudi A 4 =A 5 = 0. Zato je desna stran ena cbe enaka A 2 A A 2 = A 5 = 0, torej smo dobili A 2 XA 2 = 0. Obzornik mat. fiz.69 (2021) 1 35 i i \Sega" | 2022/3/23 | 11:33 | page 36 | #5 i i i i i i Vesti Podobno dobimo A 2 X =A 2 (X +AX +XA 2 ) =A 3 = 0 AXA =A(X +AX +XA 2 )A =A 3 = 0 XA 2 = (X +AX +XA 2 )A 2 =A 3 = 0 AX =A(X +AX +XA 2 ) =A 2 : Sledi X =A AX XA 2 =A A 2 : Videti je, kot da smo re sili to cko (b) naloge, saj imamo X izra zen z A. Vsaj tako je menilo kar precej studentov. Pravzaprav pa smo re sili to cko (a), namre c, predpostavili smo, da obstaja X, ki re si ena cbo, in ugotovili, da bi moral biti oblike X = A A 2 . Ce torej re sitev obstaja, je ena sama. Za to cko (b) moramo le se preveriti, da tako izbran X res ustreza ena cbi, kar enostavno vidimo, saj je res (A A 2 ) +A(A A 2 ) + (A A 2 )A 2 =A: Druga re sitev. Sicer podobna, a le malo druga cna re sitev, najprej pre- oblikuje osnovno ena cbo: X =A AX XA 2 : Sedaj tako izra zen X vstavimo v desno stran ena cbe, upo stevamo A 3 = 0 in nadaljujemo: X =A AX XA 2 =A A(A AX XA 2 ) (A AX XA 2 )A 2 =A (A 2 A 2 X AXA 2 ) (A 3 AXA 2 XA 4 ) =A A 2 +A 2 X + 2AXA 2 =A A 2 +A 2 (A AX XA 2 ) + 2A(A AX XA 2 )A 2 =A A 2 + (A 3 A 3 X A 2 XA 2 ) + 2(A 4 A 2 XA 2 AXA 4 ) =A A 2 3A 2 XA 2 =A A 2 3A 2 (A AX XA 2 )A 2 =A A 2 3(A 5 A 3 XA 2 A 2 XA 4 ) =A A 2 : 36 Obzornik mat. fiz.69 (2021) 1 i i \Sega" | 2022/3/23 | 11:33 | page 37 | #6 i i i i i i Osemindvajseto mednarodno tekmovanje študentov matematike Tudi v tem primeru moramo preveriti, da je tako izra zen X res re sitev osnovne ena cbe. Tretja re sitev. Opazimo, da velja (I A +A 2 ) (I +A) =I. Ce osnovno ena cbo pomno zimo z ( I A +A 2 ) z leve, dobimo X + (I A +A 2 )XA 2 = (I A +A 2 )A =A A 2 : (1) Od tod (z mno zenjem z A 2 z desne) dobimo XA 2 = 0, kar ena cbo (1) spremeni v X =A A 2 . Spet moramo preveriti, da je to res re sitev. Kombinatorika in verjetnost sta eni izmed podro cij, iz katerih so lahko naloge na tem tekmovanju, vendar pa se redko pojavijo. Tokrat je bila v re sevanje ponujena naslednja verjetnostna naloga. Naloga 2. Naj bosta n in k naravni stevili in naj bo a poljubno nenega- tivno celo stevilo. Naklju cno izberemo k-elementno podmno zico X mno zice f1; 2;:::;k +ag tako, da je vsaka k-elementna podmno zica izbrana enako verjetno (torej jo izberemo enakomerno), in podobno (spet enakomerno), neodvisno od izbrane podmno zice X, naklju cno izberemo n-elementno pod- mno zico Y mno zice f1;:::;k +n +ag. Doka zite, da je verjetnost P min(Y )> max(X) neodvisna od izbrane vrednosti parametra a. Re sitev. Najprej opazimo, da je stevilo vseh mo znih izbir podmno zic (X;Y ) enako k+a k k+n+a n . Ce zelimo, da je min( Y )> max(X), izberemon+k stevil izmed n+k+a, k manj sih stevil razglasimo za mno zico X inn ve cjih za Y . Torej je ugodnih izbir za podmno zici X in Y n+k+a n+k . Tako je iskana verjetnost enaka n+k+a n+k k+a k n+k+a n = 1 n+k n (preverimo tako, da binomske koeciente razpi semo in pokraj samo dobljene ulomke). Tako izra cunana verjetnost je neodvisna od a. Druga re sitev. Ce se nekaj da re siti enostavno, se zagotovo da tudi zakomplicirati. Tako je veliko studentov razmi sljalo zaporedno: najprej izberemo stevila v X, kakorkoli ze, nato pa stevila v Y izbiramo izmed tistih, ki so ve cja od najve cjega v X. Torej moramo lo citi primere, koliko je najve cje stevilo v mno zici X. Ce je to stevilo m, potem za X (poleg njega) Obzornik mat. fiz.69 (2021) 1 37 i i \Sega" | 2022/3/23 | 11:33 | page 38 | #7 i i i i i i Vesti izberemo se k 1 stevil izmed stevil od 1 do m 1, za Y pa izberemo n stevil izmed m + 1;m + 2;:::;k +n +a. Torej imamo m 1 k 1 k+n+a m n ugodnih izbir za X in Y , pri katerih je najve cje stevilo v X enako m. Da dobimo vse mo zne ugodne izbire, samo se se stejemo po m: k+a X m=k m 1 k 1 k +n +a m n : Kombinatori cno ze znamo se steti to vsoto, saj pre stevamo vse n +k velike podmno zice mno zice z k +n +a elementi (pri cemer v vsoti lo cimo, katero vrednost zavzame k-to stevilo). Vendar bi v tem primeru razmislek naredili kot v prvi re sitvi. Alternativa je, da se vsote lotimo ra cunsko. Tako sedaj sledijo trije na cini, kako se steti to vsoto. Vse tri so uporabili studenti. Vsi trije so napa cni. Pozoren bralec bo napake zagotovo odkril sam. Prvi na cin. Seveda lahko preverimo, kaj se zgodi pri a = 0. Vsota je enaka le enemu clenu, torej k+a X m=k m 1 k 1 k +n +a m n = k 1 k 1 k +n k n = 1; kar pomeni, da je P min(Y )> max(X) = 1 k+0 k n+k+0 n = 1 n+k n Ker v rezultatu ne nastopa a, je iskana verjetnost neodvisna od a. Drugi na cin. Ce nekaj velja za vse a, je mo zno poskusiti tudi indukcijo. Poskusov na to temo je bilo veliko. Vsem je skupno to, da izraz za a + 1 preoblikujejo (recimo, uporabijo Pascalovo enakost za binomski koecient), nato pa bodisi nekaj spregledajo bodisi nekaj opazijo, kar ne dr zi in kar jih pripelje do zelenega rezultata. Podrobnosti spustimo, podoben sistem re sevanja si oglejmo v naslednjem na cinu. Tretji na cin. Ta je se posebej inovativen. Najprej naredimo malce dru- ga cen razmislek, kako izberemo obe ugodni mno zici. Izbrali bomo k stevil izmed prvihm tern stevil izmed zadnjih k +n+a m, torej je treba se steti k+a X m=k m k k +n +a m n : Stevilni se spomnimo enakosti r X k=0 m k n r k = n +m r ; 38 Obzornik mat. fiz.69 (2021) 1 i i \Sega" | 2022/3/23 | 11:33 | page 39 | #8 i i i i i i Osemindvajseto mednarodno tekmovanje študentov matematike ki je (pri verjetnosti) povezana s hipergeometrijsko porazdelitvijo, ima pa tudi posebno ime: Vandermondeova enakost (uporabljene crke so nerodne, vendar je to to cno oblika, kot je na Wikipediji). Namesto n raje pi simo t m in se stevajmo po j, da dobimo r X j=0 m j t m r j = t r ; sedaj pa lahko preimenujemo spremenljivke in dobimo (m!k +j, r!a, t!k +n +a, se vedno se stevamo po j): a X j=0 k +j j k +n +a (k +j) a j = k +n +a a ; torej smo dobili vsoto a X j=0 k +j j n +a j a j = k +n +a a : Za novo spremenljivko m =j +k dobimo k+a X m=k m m k n +a m +k a m +k = k +n +a a : Oziroma k+a X m=k m k n +a m +k n = k +n +a a : Spet smo pravilno re sili nalogo: ko pokraj samo vse clene, je kon cni rezultat neodvisen od a. Zanimivo, kako se pogosto dve napaki ravno pokraj sata, da dobimo pravi rezultat. Se cetrti na cin. S tem je bilo sploh veliko problemov pri ocenjevanju. Namre c, zelo veliko studentov je zapisalo, da je k+a X m=k m 1 k 1 k +n +a m n = k +n +a a po znani formuli. Kateri, niso zapisali. Komisija se je strinjala, da so verje- tno nekateri studenti res ze sli sali za ustrezno enakost (predlo zen je bil celo Obzornik mat. fiz.69 (2021) 1 39 i i \Sega" | 2022/3/23 | 11:33 | page 40 | #9 i i i i i i Vesti u cbenik kombinatorike, kjer je ustrezna ena cba dokazana na sedmi strani, pred Vandermondovo). Kako lo citi med tistimi, ki to enakost poznajo, in ti- stimi, ki je ne, je ostalo neodgovorjeno vpra sanje. Tako pri vsej objektivnosti ocenjevanja s tremi ocenjevalci vsakega izdelka se vedno ostaja subjektivni del. Naslednja naloga i s ce dobra zaporedja. Naloga 3. Re cemo, da je pozitivno realno stevilo d dobro, ce obstaja zaporedje a 1 ;a 2 ;a 3 ;:::2 (0;d), tako da za vsak n to cke a 1 ;:::;a n razdelijo interval [0;d] na podintervale dol zine najve c 1 =n. Dolo cite sup n d d je dobro o : Re sitev. Naj bo d ? = supfd j d je dobrog. Pokazali bomo, da je d ? = ln(2) : = 0;693 (kar je recimo ve c kot 1 2 , kar je kot zgornjo mejo na slo kar nekaj tekmovalcev). (a) d ? ln 2: Naj bo d dobro stevilo in naj bo a 1 ;a 2 ;::: ustrezno zaporedje za to stevilo. Vemo, da vsako kon cno zaporedje a 1 ;:::;a n razdeli interval [0;d] na n + 1 delov z dol zino najve c 1 =n. Naj bodo 0 ‘ 1 ‘ 2 ‘ n+1 dol zine teh intervalov. Za vsak k = 1;:::;n velja, da ko dodamo naslednjih k clenov zaporedja, torej a n+1 ;:::;a n+k , vsaj n + 1 k intervalov ostane nespremenjenih in imajo torej nespremenjene dol zine. Torej mora veljati ‘ n+1 k 1 n+k , zato pa je d =‘ 1 + +‘ n+1 1 2n + 1 2n 1 + + 1 n : (2) Ko po sljemo n!1, desna stran konvergira k ln(2), od koder dobimo zeleno neenakost d ln(2). (b) d ? ln 2: Najti moramo zaporedje a i , ki ustreza pogoju o delitvi intervala (0;d) in za katerega je supa i = ln 2. Opazimo ln 2 = ln 2n lnn = n X i=1 (ln(n +i) ln(n +i 1)) = n X i=1 ln 1 + 1 n +i 1 : 40 Obzornik mat. fiz.69 (2021) 1 i i \Sega" | 2022/3/23 | 11:33 | page 41 | #10 i i i i i i Osemindvajseto mednarodno tekmovanje študentov matematike Ideja je, da clene vsote ena cimo z dol zinami intervalov, ki jih dobimo, ce v interval (0; ln 2) dodamo n 1 to ck. Seveda velja tudi, da je najve cja dol zina enaka ln(1 + 1 =n), kar je manj od 1=n. Ko v interval dodamo se eno to cko, razbijemo najdalj si interval na dva manj sa kosa, tako da v vsoti clen ln(1 + 1 =n) nadomestimo z vsoto ln(1 + 1=(2n)) in ln(1 + 1=(2n + 1)), saj je ln 1 + 1 2n + ln 1 + 1 2n + 1 = ln 1 + 1 n : Tako dobimo postopek dodajanja to ck. Za n = 2 dobimo prvo to cko, a 1 = ln 3 2 in interval (0; ln 2) razpade na dva intervala, (0; ln 3 2 ) in (ln 3 2 ; ln 2). Vzamemo ve cjega, vanj dodamo to cko tako, da se interval dol zine ln 3 2 razbije na dva kosa, dolga ln 5 4 in ln 6 5 , torej je a 2 = ln 5 4 . Nato inter- val dol zine ln 4 3 razbijemo na dva z dol zinama ln 7 6 in ln 8 7 , tako je recimo a 3 = ln 3 2 + ln 7 6 = ln 7 4 . Na isti na cin dobimo a 4 = ln 9 8 , a 5 = ln 11 8 , a 6 = ln 13 8 , a 7 = ln 15 8 , a 8 = ln 17 16 ;::: . Za konec pa najlep sa naloga. Zakaj najlep sa? Recimo, ker je kratka, z enostavno formulacijo, ki jo lahko razume tudi marsikateri nematematik: Naloga 4. Koliko najve c enotskih vektorjev lahko izberemo v R n , da bosta med poljubnimi tremi izmed njih vsaj dva pravokotna? Kot informacija: z nalogo je povezan Paul Erd} os. Namigi. Re sitev je seveda 2 n. Izberemo lahko dve razli cni ortonormirani bazi, vsaka iman vektorjev, in ko izberemo tri, sta zagotovo dva iz iste baze in torej pravokotna. Naloga je torej pokazati, da ne moremo imeti 2n + 1 takih vektorjev. Ko pogledamo Gramovo matriko teh vektorjev, ugotovimo, da je z njo nekaj narobe. Kaj to cno, lahko poskusite premisliti sami. Se informacija: na tekmovanju je bil dose zen povpre cen rezultat pri prvi nalogi 6,5, pri drugi 4,7, pri tretji 1,1 in pri cetrti 0,04 to cke, od 10 mo znih. Zmagovalec je imel 70 to ck od 80 mo znih, pri cetrti nalogi je dobil 0 to ck. Kogar zanima uradna re sitev zadnje naloge ali pa bi se rad poskusil v re sevanju se kak sne naloge s tekmovanja, si jih lahko ogleda na prej omenjeni internetni strani tekmovanja www.imc-math.org.uk. 28. tekmovanje je bilo kar se ti ce tekmovalnega uspeha za na se studente res popolno, kot je 28 popolno stevilo. Vseeno na podoben uspeh upamo prej kot cez 468 let. Gregor Sega Obzornik mat. fiz.69 (2021) 1 III