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}_{\geq 1}$.
Bevis. Med Maclaurinrekken til $e^x$ får vi $e^x = \sum_{n=0}^\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!} \implies n! > \left( \frac{n}{e}\right)^n > \left( \frac{n}{3}\right)^n \qquad \blacksquare$

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{alignat*}{2} 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+\dots+(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{alignat*}$$ 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}^\infty \left \lfloor \frac{k}{p^j} \right \rfloor$ der $\lfloor \cdot \rfloor$ er gulvfunksjonen. Nå er $$\begin{alignat*}{2} \nu_2(k!)&=\sum_{j=1}^\infty \left \lfloor \frac{k}{2^j} \right \rfloor < \sum_{j=1}^\infty \frac{k}{2^j} = k \sum_{j=1}^\infty \frac{1}{2^j} \\ &= k \cdot \left(\frac{1}{1-\frac{1}{2}} -1 \right) = k \qquad (\text{uendelig geometrisk rekke})\end{alignat*}$$ 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 \geq 8$ er åpenbart $\frac{n(n-1)}{6}>8$ og $\frac32(n-1)>n$ så $$\left( \frac{(n-1)n}{6} \right)^{\frac{n-1}{2}}>8^{\frac{(n-1)}{2}}=2^{\frac32 (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 \geq 8$. Dermed holder det å sjekke om den diofantiske likningen har løsning for $n \leq 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 \leq 3$ har vi likningen (1) løsningene $(k,n)=(1,1)$ og $(k,n)=(3,2)$.

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

Ved hjelp av Legendres fakultetsformel kan vi bevise at for alle primtall $p \leq 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 \geq 3$), som igjen innebærer at det finnes et heltall $m \geq 4$ slik at

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

Herav følger at

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

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

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

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

${\textstyle (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 ${\textstyle k! > (\frac{k}{e})^k}$ og implikasjonen $k! < 2^{n^2}$ (følger av (4)) finner vi at

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

i.e.

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

som gir (ettersom $c>1$)

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

hvilket impliserer

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

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

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

i.e.

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

hvilket er umulig siden $n \geq 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 \rightarrow HHT \rightarrow HTT \rightarrow 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 offline]

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\rightarrow H$ og $H\rightarrow 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$ i starten}.$$
For $T\rightarrow 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\rightarrow 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}\left[2S+\text{Antall H}\right]=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\rightarrow H$ og $H\rightarrow 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$ i starten}.$$
For $T\rightarrow 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\rightarrow 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}\left[2S+\text{Antall H}\right]=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 offline]

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!