IMO 2019

[Markus]

Finn alle funksjoner $f:\mathbb{Z}\to \mathbb{Z}$ slik at for alle $a,b\in \mathbb{Z}$ er $f(2a)+2f(b)=f(f(a+b))$

[Gustav]

Finn alle funksjoner $f:\mathbb{Z}\to \mathbb{Z}$ slik at for alle $a,b\in \mathbb{Z}$ er $f(2a)+2f(b)=f(f(a+b))$

Bytter vi om på $a$ og $b$ ser vi at $f(2a)+2f(b)=f(2b)+2f(a)$, dvs. at $f(2a)-2f(a)=k$ for en konstant $k$. $a=0$ gir da $f(0)=2f(0)+k$, så $k=-f(0)$ og vi har dermed at $f(2a)=2f(a)-f(0)$. Innsatt i opprinnelig ligning fås $2f(a)-f(0)+2f(b)=f(f(a+b))$. $b=0$ i denne gir $2f(a)+f(0)=f(f(a))$. La $a\to a+b$, så $f(f(a+b))=2f(a+b)+f(0)$. Innsatt i opprinnelig ligning fås følgende Cauchy-funksjonalligning: $f(a)+f(b)=f(a+b)+f(0)$ (som er ekvivalent med Cauchy ved å la $g(x)=f(x)-f(0)$), hvis eneste løsninger er på formen $f(x)=cx+f(0)$ for heltallig $c$. Settes dette inn i opprinnelig ligning finner man at $c=2$ eller $c=f(0)=0$, så de eneste løsningene er $f(x)=2x+f(0)$ for vilkårlig valgt heltall $f(0)$, eller $f(x)$ identisk lik $0$.

Edit: Andre løsninger er velkomne!

Oppfølger (IMO dag 2 problem 4): Finn alle par $(k,n)$ av positive heltall slik at $$k!=(2^n-1)(2^n-2)(2^n-2^2)...(2^n-2^{n-1})$$.

[Markus]

Finn alle funksjoner $f:\mathbb{Z}\to \mathbb{Z}$ slik at for alle $a,b\in \mathbb{Z}$ er $f(2a)+2f(b)=f(f(a+b))$

Bytter vi om på $a$ og $b$ ser vi at $f(2a)+2f(b)=f(2b)+2f(a)$, dvs. at $f(2a)-2f(a)=k$ for en konstant $k$. $a=0$ gir da $f(0)=2f(0)+k$, så $k=-f(0)$ og vi har dermed at $f(2a)=2f(a)-f(0)$. Innsatt i opprinnelig ligning fås $2f(a)-f(0)+2f(b)=f(f(a+b))$. $b=0$ i denne gir $2f(a)+f(0)=f(f(a))$. La $a\to a+b$, så $f(f(a+b))=2f(a+b)+f(0)$. Innsatt i opprinnelig ligning fås følgende Cauchy-funksjonalligning: $f(a)+f(b)=f(a+b)+f(0)$ (som er ekvivalent med Cauchy ved å la $g(x)=f(x)-f(0)$), hvis eneste løsninger er på formen $f(x)=cx+f(0)$ for heltallig $c$. Settes dette inn i opprinnelig ligning finner man at $c=2$ eller $c=f(0)=0$, så de eneste løsningene er $f(x)=2x+f(0)$ for vilkårlig valgt heltall $f(0)$, eller $f(x)$ identisk lik $0$.

Edit: Andre løsninger er velkomne!

Oppfølger (IMO dag 2 problem 4): Finn alle par $(k,n)$ av positive heltall slik at $$k!=(2^n-1)(2^n-2)...(2^n-2^{n-1})$$.

Yes, fin løsning, gjorde essensielt sett det samme! I oppfølgeren, er det meningen at $k!=(2^n-1)(2^n-2)(2^n-4)\cdots (2^n-2^{n-1})$ eller $k!=(2^n-1)(2^n-2)(2^n-3)\cdots (2^n-2^{n-1})$?

[Gustav]

I oppfølgeren, er det meningen at $k!=(2^n-1)(2^n-2)(2^n-4)\cdots (2^n-2^{n-1})$ eller $k!=(2^n-1)(2^n-2)(2^n-3)\cdots (2^n-2^{n-1})$?

Godt poeng, det skal være $k!=(2^n-1)(2^n-2)(2^n-4)\cdots (2^n-2^{n-1})$

[Markus]

Godt poeng, det skal være $k!=(2^n-1)(2^n-2)(2^n-4)\cdots (2^n-2^{n-1})$

Dette var et veldig kult problem!

Lemma: $n!>(n/3{)}^n$ for $n\in {\mathbb{N}}_{\ge 1}$.
Bevis. Med Maclaurinrekken til $e^x$ får vi $e^x=\sum _{n=0}^{\mathrm{\infty }}\frac{x^n}{n!}>\frac{x^n}{n!}$ når $x$ er positiv. Sett $x=n$, så får vi at $e^n>\frac{n^n}{n!}⟹n!>{\left(\frac{n}{e}\right)}^n>{\left(\frac{n}{3}\right)}^n◼$

Anta at $k!=(2^n-1)(2^n-2)(2^n-4)\cdots (2^n-2^{n-1})$. Vi starter med å trekke ut toer-faktorene fra produktet på høyresiden $$\begin{array}{rl}k!& =(2^n-1)\cdot 2(2^{n-1}-1)\cdot 2^2(2^{n-2}-1)\cdots 2^{n-3}(2^3-1)\cdot 2^{n-2}(2^2-1)\cdot 2^{n-1}(2^1-1)\\ & =2^{1+2+\cdots +(n-1)}(2^{n-1}-1)(2^{n-2}-1)\cdots 7\cdot 3\cdot 1=2^{\frac{(n-1)n}{2}}(2^{n-1}-1)(2^{n-2}-1)\cdots 7\cdot 3\end{array}$$ Hvis $p$ er et primtall defineres ${\nu }_p(n)$ til å være eksponenten til den største potensen av $p$ som deler $n$. For at likningen vår skal ha en løsning må dermed ${\nu }_2(k!)=\frac{(n-1)n}{2}$ siden $2^{\frac{(n-1)n}{2}}$ er en faktor på høyresiden. Legendres formel sier oss at ${\nu }_p(k!)=\sum _{j=1}^{\mathrm{\infty }}\lfloor \frac{k}{p^j}\rfloor$ der $\lfloor \cdot \rfloor$ er gulvfunksjonen. Nå er $$\begin{array}{rl}{\nu }_2(k!)& =\sum _{j=1}^{\mathrm{\infty }}\lfloor \frac{k}{2^j}\rfloor <\sum _{j=1}^{\mathrm{\infty }}\frac{k}{2^j}=k\sum _{j=1}^{\mathrm{\infty }}\frac{1}{2^j}\\ & =k\cdot (\frac{1}{1-\frac{1}{2}}-1)=k(\text{uendelig geometrisk rekke})\end{array}$$ Dermed er $k!>\left(\frac{(n-1)n}{2}\right)$. Vi finner ganske lett en øvre grense for $k!$ også; $$k!=(2^n-1)(2^n-2)(2^n-4)\cdots (2^n-2^{n-1})<2^n\cdot 2^n\cdots 2^n=(2^n{)}^n=2^{n^2}$$ Nå prøver vi å kombinere disse to grensene for å få en ulikhet i $n$. For $n\ge 8$ er åpenbart $\frac{n(n-1)}{6}>8$ og $\frac{3}{2}(n-1)>n$ så $${\left(\frac{(n-1)n}{6}\right)}^{\frac{n-1}{2}}>8^{\frac{(n-1)}{2}}=2^{\frac{3}{2}(n-1)}>2^n$$ Dermed får vi med lemmaet vårt og denne ulikheten at $$\left(\frac{n(n-1)}{2}\right)!>{\left(\frac{n(n-1)}{6}\right)}^{\frac{n(n-1)}{2}}>2^{n^2}>k!$$ som er en selvmotsigelse mot at $k!>\left(\frac{(n-1)n}{2}\right)!$ for $n\ge 8$. Dermed holder det å sjekke om den diofantiske likningen har løsning for $n\le 7$ og vi ser da at $(1,1)$ og $(3,2)$ er de eneste løsningene

[Solar Plexsus]

Alternativ løsning Vi har gitt to naturlige tall $k$ og $n$ som tilfredsstiller den diofantiske likningen

$(1)k!=\prod _{i=0}^{n-1}(2^n-2^i)$.

For $k\le 3$ har vi likningen (1) løsningene $(k,n)=(1,1)$ og $(k,n)=(3,2)$.

Anta at $k\ge 4$, hvilket betyr at $n\ge 3$.

Ved hjelp av Legendres fakultetsformel kan vi bevise at for alle primtall $p\le k$ er

$(2){\nu }_p(k!)=\frac{k-k_T}{p-1}$,

hvor $k_T$ er tverrsummen av $k$ representert i $p$-tallsystemet.

Ved å sette $p=2$ i (2), får vi

$(3){\nu }_2(k!)=k-k_T$.

Likningen (1) er ekvivalent med

$(4)k!=2^{\frac{n(n-1)}{2}}\prod _{i=1}^n(2^i-1)$,

som kombinert med (3) gir oss

$(5)k-k_T=2^{\frac{n(n-1)}{2}}$.

Ifølge (5) er $k>2^3$ (siden $n\ge 3$), som igjen innebærer at det finnes et heltall $m\ge 4$ slik at

$(6)2^{m-1}\le k<2^m$.

Herav følger at

$2^{m-1}-m<k-k_T<2^m$,

som (siden $2^{m-2}\le 2^{m-1}-m$) betyr at

$(7)2^{m-2}<k-k_T<2^m$.

Ved å kombinere (5) og (7) får vi at

$(8)m-1=\frac{n(n-1)}{2}$.

Ifølge (6) og (8) finnes det et rasjonelt tall $c\in [1,2)$ slik at

$(9)k=c\cdot 2^{\frac{n(n-1)}{2}}$.

Ved å anvende det faktum at $k!>(\frac{k}{e}{)}^k$ og implikasjonen $k!<2^{n^2}$ (følger av (4)) finner vi at

$2^{n^2}>k!>(\frac{k}{e}{)}^k=(\frac{c}{e}\cdot 2^{\frac{n(n-1)}{2}}{)}^k$,

i.e.

$2^{\frac{n^2}{k}}>\frac{c}{e}\cdot 2^{\frac{n(n-1)}{2}}$,

som gir (ettersom $c>1$)

$2^{1,5}>e>\frac{e}{c}>2^{\frac{n(n-1)}{2}-\frac{n^2}{k}}$,

hvilket impliserer

$(10)n(n-1)-\frac{2n^2}{k}<3$.

Ved å kombinere ulikheten (10) med det faktum at $k>8$, får vi at

$n(n-1)-\frac{2n^2}{8}<3$.

i.e.

$n(3n-4)<12$,

hvilket er umulig siden $n\ge 3$. Denne motsigelsen fullfører beviset.

[Gustav]

Ser rett ut begge løsningene. Veldig bra Er Legendres formel noe som er kjent for alle IMO-deltagerne, eller er dette noe som de må utlede selv?

Oppfølger: Bank of Bath utsteder mynter med bokstaven $H$ på den ene siden, og $T$ på den
andre. Nils plasserer $n$ slike mynter på rad, fra venstre til høyre. Han utfører gjentatte ganger
følgende trekk: dersom det er nøyaktig $k>0$ mynter som viser $H$, snur han mynt nummer $k$ fra
venstre; ellers viser alle mynter $T$, og han stopper. For eksempel vil i tilfellet $n=3$ prosessen som
starter med konfigurasjonen $THT$ være $THT\to HHT\to HTT\to TTT$, som stopper opp etter tre
trekk.
(a) Vis at uansett startkonfigurasjon kommer Nils til å stoppe etter et endelig antall trekk.
(b) For enhver startkonfigurasjon $C$ lar vi $L(C)$ betegne antall trekk før Nils stopper. For eksempel
er $L(THT)=3$ og $L(TTT)=0$. Bestem gjennomsnittet av tallene $L(C)$ tilhørende de $2^n$
mulige startkonfigurasjonene $C$.

[Markus]

Ser rett ut begge løsningene. Veldig bra Er Legendres formel noe som er kjent for alle IMO-deltagerne, eller er dette noe som de må utlede selv?

Av det jeg har sett og hørt virker Legendres formel som et standardtriks å kunne, men i følge noen av disse er jo også loven om kvadratisk resiprositet og det å arbeide i syklotomiske kropper som $\mathbb{Q}({\zeta }_p)$ noe man som matematikkolympiader bør vite om og kunne (nå skal det jo sies at dette kan være nyttig for å løse diofantiske likninger, det var jo det Kummer utviklet det for til å starte med), så hva som er standard eller ikke er vanskelig å vite. Nå er Legendres formel noe som er mye mer elementært enn de andre to eksemplene, og det er veldig lett å vise, så jeg tipper en gjennomsnittig IMO-deltager vet om formelen.

Hvordan løste du oppgaven Gustav?

[mingjun]

En overraskende løsning til Bank of Bath som Magnus Hellebust Haaland (deltaker NOR1) fant under konkurransen:

[+] Skjult tekst

Vi løser $b)$, ettersom $a)$ følger trivielt fra konklusjonen i $b)$.

For hver mynt som viser $T$, gi den antall poeng lik antall $H$-mynter den har til høyre for seg selv. Vi skal vise at for alle trekk $T\to H$ og $H\to T$, forandrer summen av alle poengene $S$ seg med henholdsvis $-1$ og $0$. Dette gir dermed at antall trekk en konfigurasjon trenger for å stoppe (altså bli en rekke $T$-er) er lik $$2S+\text{antall }H\text{ i starten}.$$
For $T\to H$, la den omgjorte mynten være på posisjon $k$, og anta at det er $l$ $H$ til høyre for pos. $k$. Siden det er $k$ $H$-mynter til sammen må det dermed være $k-l$ $H$-mynter til venstre for pos. $k$, og følgelig er det $k-1-(k-l)=l-1$ $T$-mynter til venstre for pos. $k$. Alle $T$-mynter til venstre for pos. $k$ vil få et poeng fra trekket, mens den omgjorte mynten vil miste $l$ poeng. Dermed er forandringen i $S$ lik $l-1-l=-1$. Det er mulig å sjekke $H\to T$ med samme framgangsmåte.

Nå trenger man kun å finne gjennomsnittet på antall poeng og antall $H$ i starten. Med lineariteten til forventningverdi får man $$\mathbb{E}[2S+\text{Antall H}]=2\left(\sum _{i=1}^n\mathbb{E}\left[\text{antall poeng mynt }i\text{ skaffer ved å være H}\right]\right)+\mathbb{E}\left[\text{Antall H}\right]=2\sum _{i=1}^n\frac{i-1}{2}\cdot \frac{1}{2}+\frac{n}{2}=\frac{n^2+n}{4}.$$

[Gustav]

En overraskende løsning til Bank of Bath som Magnus Hellebust Haaland (deltaker NOR1) fant under konkurransen:

[+] Skjult tekst

Vi løser $b)$, ettersom $a)$ følger trivielt fra konklusjonen i $b)$.

For hver mynt som viser $T$, gi den antall poeng lik antall $H$-mynter den har til høyre for seg selv. Vi skal vise at for alle trekk $T\to H$ og $H\to T$, forandrer summen av alle poengene $S$ seg med henholdsvis $-1$ og $0$. Dette gir dermed at antall trekk en konfigurasjon trenger for å stoppe (altså bli en rekke $T$-er) er lik $$2S+\text{antall }H\text{ i starten}.$$
For $T\to H$, la den omgjorte mynten være på posisjon $k$, og anta at det er $l$ $H$ til høyre for pos. $k$. Siden det er $k$ $H$-mynter til sammen må det dermed være $k-l$ $H$-mynter til venstre for pos. $k$, og følgelig er det $k-1-(k-l)=l-1$ $T$-mynter til venstre for pos. $k$. Alle $T$-mynter til venstre for pos. $k$ vil få et poeng fra trekket, mens den omgjorte mynten vil miste $l$ poeng. Dermed er forandringen i $S$ lik $l-1-l=-1$. Det er mulig å sjekke $H\to T$ med samme framgangsmåte.

Nå trenger man kun å finne gjennomsnittet på antall poeng og antall $H$ i starten. Med lineariteten til forventningverdi får man $$\mathbb{E}[2S+\text{Antall H}]=2\left(\sum _{i=1}^n\mathbb{E}\left[\text{antall poeng mynt i skaffer ved å være H}\right]\right)+\mathbb{E}\left[\text{Antall H}\right]=2\sum _{i=1}^n\frac{i-1}{2}\cdot \frac{1}{2}+\frac{n}{2}=\frac{n^2+n}{4}.$$

Kult! Gratulerer med bronsen, veldig imponerende! (for de med adressaabonnement: https://www.adressa.no/pluss/nyheter/20 ... 547199.ece )

[mingjun]

Kult! Gratulerer med bronsen, veldig imponerende! (for de med adressaabonnement: https://www.adressa.no/pluss/nyheter/20 ... 547199.ece )

Takk!

[Markus]

Gratulerer så mye med bronsen mingjun! Svært imponerende!