Igår skedde en viktig etapp i att utse Sveriges vassaste (i matematik) gymnasieelever. Det var det nordiska matematiktvälingen NMC (Nordic Mathematical Contest). Ungefär 20 personer från varje land i Norden får delta i tävlingen, men det är inte så mycket kamp mellan länder, som kamp inom länder. Löser man flest problem i sitt eget land, har man stor chans att komma vidare till den internationella matematikolympiaden (som i sin tur är lika mycket en persontävling som landtävling).
Här är årest problem. Hur många kan du lösa? (Jag har löst tvåan än så länge).
Ledtråd till trean:
Säg att du vid ett skede har talen a,b,c,d,e och att du byter ut, säg, a och b mot a+b samt ab. Låt S_k = a + b + c + d + e. Då får du den nya summan S_k+1 = (a + b) + ab + c + d + e = S_k + p_k+1 där p_k+1 = ab. Analysera p_k-termerna.
På 4an får jag att det räcker med 38 matcher.
16 + 8 + 4 + 2 + 1 = 31 matcher för att bestämma vinnaren. Under loppet har vinnaren mött 5 personer och silvermedaljören borde enbart åkt ut genom att ha mött vinnaren så det betyder att han finns bland dessa 5 personer. Så vi kör en omgång (2) med dem (fast låter en spelare vila tills sista matchen), vilket ger 2 + 1 + 1 = 4 matcher. Bronsmedaljören i sin tur borde endast ha åkt ut genom att ha förlorat mot guldmedaljören eller silvermedaljören. Hade han åkt ut genom att förlorat mot guldmedaljören så skulle han varit med i omgång (2) och därmed åkt ut genom silvermedaljören. Så vi räknar antalet personer silvermedaljören har mött (*minus guldmedaljören) vilket blir <= 4 + 1 + 1 + 1 = 7 personer. Vi kan avgöra den starkaste av dessa med 3 matcher och summan av allting blir således 31 + 4 + 3 = 38 matcher.
Hur avgör du den starkaste av 7 personer med 3 matcher?
Oj, och där var felet! Tack!