Nordisk (oppgave 1, 2, 3 og 4)

[Karl_Erik]

1. En funksjon [tex]f: \mathbb Z _+ \rightarrow \mathbb Z _+[/tex] er voksende (dvs at for [tex]k<l[/tex] er [tex]f(k) \leq f(l)[/tex]) og tilfredsstiller [tex]f(mn)=f(m)f(n)[/tex] for alle positive heltall [tex]m[/tex] og [tex]n[/tex] hvis største felles faktor er én. Vis at [tex]f(8)f(13) \geq (f(10))^2[/tex].

2. Tre sirkler [tex]S_A, S_B[/tex] og [tex]S_C[/tex] har et felles skjæringspunkt O. Det andre skjæringspunktet mellom [tex]S_A[/tex] og [tex]S_B[/tex] er C, og tilsvarende defineres A og B på den opplagte måten. Linja AO skjærer [tex]S_A[/tex] i X, og linjene BO og CO skjærer henholdsvis [tex]S_B[/tex] og [tex]S_C[/tex] i Y og Z (der X, Y og Z alle er ulike O). Vis at [tex]\frac{|AY||BZ||CX|} {|AZ| |BX| |CY|} = 1[/tex].

3. Foran seg har Laura 2010 lamper som er koplet til 2010 knapper. Hun ønsker å finne ut hvilken lampe som er koplet til hver knapp. (Det sto ikke i oppgaveteksten, men jeg ble fortalt at det stemte at hver knapp hang sammen med en og bare én lampe og motsatt, og at Laura og Richard begge var klar over dette.) For å gjøre dette observerer hun hvilke lamper som lyser når Richard trykker på et utvalg av knappene. (Ikke å trykke på noen av knappene er også et mulig utvalg.) Richard trykker alltid på knappene samtidig, så lampene lyser samtidig også.

a) Anta at Richard velger hvilke knapper som skal trykkes på. Hva er største mulige antall kombinasjoner av knapper han kan trykke på før Laura kan finne ut hvilken lampe som er koplet til hver knapp?

b) Anta at Laura velger hvilke knapper som skal trykkes på. Ha er minste mulige antall kombinasjoner av forsøk hun må gjøre for at hun skal kunne finne ut hvilken lampe som er koplet til hver knapp?

4. Et positivt heltall kalles enkelt dersom den vanlige representasjonen av tallet i titallssytemet kun inneholder nuller og ettall. Finn minste positive heltall k slik at det for ethvert positive heltall n finnes enkle tall [tex]a_i[/tex] slik at [tex]n = a_1 \pm a_2 \pm \ldots \pm a_k[/tex].

For deltagerene kan vi jo også gjøre dette til en hvordan-gikk-det-tråd. For min del gikk det ikke så bra som jeg hadde håpet - jeg tror jeg løste oppgave 2 og oppgave 3a), men ellers fikk jeg nok ikke til noe særlig. Hvordan gikk det med dere?

[Bernt Ivar]

Eg trur eg klarte dei 3 første, men kan sjølvsagt ikkje vere heilt sikker.

Eg har jo tradisjon for å gjere det bra i nordisk(dvs. i fjor), så eg satsar på at det gjentar seg.

[DerKleineBollemann]

Svarte på 2 og 3. 3a er eg ganske sikker på og greidde ellers så forsto eg ikkje alle oppgåvene heilt.

Det gjekk greitt med andre ord.

[Charlatan]

Morsomme oppgaver.

1: [tex]f(3)f(8)f(13)=f(312) \geq f(310) = f(31)f(10) \geq f(30)f(10) =f(3)f(10)^2 [/tex]

[Charlatan]

2: med forbehold om feil

inverter om O med en sirkel med radius 1, der vi kar T' denotere inversjonsbildet til T. La MN være en linjestykke før inversjon. Etter inversjon kan det enkelt vises at [tex]|M^{\prime}N^{\prime}| = \frac{|MN|}{|OM||ON|}[/tex] ved å betrakte de formlike trekantene.

Siden sirklene S_A,S_B og S_C alle går gjennom O, er bildet deres tre linjer som krysser hverandre i A', B' og C'. Dessuten avbildes linjene gjennom AX, BY og CZ til seg selv, så X,Y og Z er skjæringspunktene mellom trekanten som dannes av S'_AS'_BS'_C, og OA', OB' og OC'. Dermed har vi av Cevas teorem at
[tex]\frac{|AY||BZ||CX|} {|AZ| |BX| |CY|} = \frac{\frac{|AY|}{|OA||OY|}\frac{|BZ|}{|OB||OZ|}\frac{|CX|}{|OX||OC|}} {\frac{|AZ|}{|OA||OZ|} \frac{|BX|}{|OB||OX|} \frac{|CY|}{|OC||OY|}} = \frac{|A^\prime Y^\prime ||B^\prime Z^\prime ||C^\prime X^\prime |} {|A^\prime Z^\prime | |B^\prime X^\prime | |C^\prime Y^\prime |} =1. [/tex]

post gjerne løsningene deres!

[Karl_Erik]

Jeg er ikke helt stø på inversjon, så jeg valgte en annen måte å løse oppgave 2. Løsningen din var dog veldig fin. Siden AX og BY skjærer hverandre i O er vinkel AOY lik vinkel BOX. Kall den [tex]\theta[/tex]. Av den utvidede sinussetningen er da [tex]\frac {|AY|} {\sin \theta} = 2R_B[/tex], der [tex]R_B[/tex] er radien i sirkel [tex]\Gamma_B[/tex]. Tilsarende er [tex] \frac {|BX|} {\sin \theta} = 2R_A[/tex]. Altså er [tex]\frac {|AY|} {|BX|} = \frac {R_B} {R_A}[/tex]. Tilsvarende får vi resultater for de andre sidene, og multipliserer vi disse får vi resultatet.

På oppgave 3a) legger vi først merke til at Richard kan trykke inn de [tex]2^{2009}[/tex] kombinasjonene der den første og andre knappen behandles som 'samme knapp' uten at Laura har noen mulighet til å avgjøre hvilken av disse to knappene som hører til hvilken lampe. Anta så at det er mulig for Richard å trykke inn [tex]2^2009+1[/tex] knapper uten at Laura kan avgjøre hvilken lampe som hører til hvilken knapp. Det må da finnes to knapper A og B og to lamper i og j slik at knapp A kan høre til lampe i og knapp B kan høre til lampe j eller motsatt.

Om vi ignorerer knapp A og B finnes det [tex]2^{2008}[/tex]mulige knappekombinasjoner. Siden [tex]\lceil \frac {2^{2009}+1} {2^{2008}}\rceil=3[/tex] finnes det da tre kombinasjoner Richard har trykket inn som ikke er forskjellige på noen annen måte enn i knappene A og B. Siden disse bare kan trykkes inn på fire måter (A, B, A og B eller ingen av delene) må Laura da opplagt kunne finne ut hvilken av knappene A og B som hører til hvilken lampe og motsatt, noe som motsier antagelsen vår. Altså var den feil, og Richard kan høyst trykke inn [tex]2^{2009}[/tex] kombinasjoner før Laura kan avgjøre alle koplingene mellom knapper og lamper.

Oppgave 3b) svarte jeg 1005 på med noe jeg trodde var et bevis, men dette er feil, da svaret i ettertid har vist seg å være 11. Vi ser først at siden [tex]2^{11} > 2010 > 2^{10}[/tex] kan Laura løse korrespondansen ved først å dele intervallet [tex][1, 2048][/tex] i to (vi bruker 2048 for å få penere tall) og trykke inn hele den første halvparten, for deretter å dele disse to delintervallene i to og deretter trykke inn den første halvparten i hver av disse og gjenta prosedyren på den opplagte måten for å finne svaret.

For å vise at 10 kombinasjoner ikke holder legger vi merke til at en lampe er entydig bestemt hvis og bare hvis den kan skrives som 'summen' av inntrykte kombinasjoner. Siden det kun finnes [tex]2^{10}[/tex] 'kombinasjonssummer' og [tex]2^{10}=1024 < 2010[/tex] er dette en umulighet, så minste mulighet for Laura er 10.

[DerKleineBollemann]

Altså var den feil, og Richard kan høyst trykke inn 2^{2009} kombinasjoner før Laura kan avgjøre alle koplingene mellom knapper og lamper.

Eg fekk svaret (2^2009)+1.

[Karl_Erik]

Jeg gjør ofte feil, så det kan jo fint stemme det også.

[Charlatan]

4: Se på tallet [tex]n = 987654321[/tex]. Anta at dette tallet kan skrives som en sum av 8 enkle tall [tex]a_i[/tex] (de kan være både positive og negative), der [tex]a_{ij} \in \{ -1,0,1 \}[/tex] er det j't siste sifferet i [tex]a_i[/tex].
Da er [tex]\sum_{i=1}a_{i1} = 1 \pmod {10}[/tex]. Men eneste mulighet for dette er [tex]\sum_{i=1}a_{i1} = 1[/tex], og dermed er minst ett av sifrene (og dermed tallene) positive.
Videre, siden siden [tex]\sum_{i=1}a_{i1} = 1[/tex], må [tex]\sum_{i=1}a_{i2} = 2 \pmod{10}[/tex]. Eneste muligheter er [tex]\sum_{i=1}a_{i2} = 2[/tex] og [tex]\sum_{i=1}a_{i2} = -8[/tex], men sistnevnte er umulig ettersom minst ett av sifrene er positive. Dermed er [tex]\sum_{i=1}a_{i2} = 2[/tex], så to av sifrene er positive, og vi har at minst to tall er positive. Fortsetter vi slik ender vi opp med at alle tallene er positive, og [tex]\sum_{i=1}a_{i9} = 9 \pmod {10}[/tex]. Men dette er umulig siden sifrene er positive og det bare er 8 av dem.
Vi må altså ha minst 9 tall, og åpenbart kan ethver tall skrives som summen av 9 enkle tall.