matematikk.net

Finn alle strengt voksende $f:\mathbb{N}\to\mathbb{N}$ som oppfyller $f(f(n))=3n$ for alle $n\in\mathbb{N}$.

Først ser vi at $f(f(f(n)))=3f(n)=f(3n)$. $f(1)=2$ og $f(2)=f(f(1))=3$.

Dermed er $f(3)=2*3=6$, $f(9)=3f(3)=2*3^2$ etc. Så $f(3^k)=2*3^k$

Videre er $f(6)=f(3*2)=3f(2)=3^2$, $f(18)=f(3*6)=3f(6)=3^3$ etc. Så $f(2*3^k)=3^{k+1}$

Mellom $n=2*3^k$ og $n=3^k$ er det $3^k-1$ hele tall, og mellom de tilhørende funksjonsverdiene $3^{k+1}$ og $2*3^k$ er det også $3^k-1$ hele tall. Det følger at f(n) er unikt bestemt for alle $n$ på formen $3^k$, $2*3^k$ og alle n mellom disse, for alle k:

(Vi har at $f(3^k+1)=2*3^k+1$, $f(3^k+2)=2*3^k+2$,... , $f(2*3^k-1)=3^{k+1}-1$.)

Det gjenstår å finne $f(2*3^k+1)$, $f(2*3^k+2),..., f(3^{k+1}-1)$

Men disse funksjonsverdiene er nå bestemt ved at $f(2*3^k+1)=f(f(3^k+1))=3(3^k+1)$, $f(2*3^k+2)=f(f(3^k+2))=3(3^k+2)$, ... , $f(3^{k+1}-1)=f(f(2* 3^k-1))=3(2*3^k-1)$.

Oppsummert er altså

$f(3^k+m)=2*3^k+m$
$f(2*3^k+m)=3(3^k+m)$ , for $0\leq m<3^k$

(Beklager rotete løsning. Har du en bedre, og hvor er oppgaven hentet fra?)

Løsningen min var omtrent helt identisk. Finner først $f(1)=2$ og $f(2)=3$ og at $f(3n)=3f(n)$.
Dermed følger det enkelt ved induksjon at $f(3^n)=2\cdot 3^n$ og at $f(2\cdot 3^n)=3^{n+1}$.
Ved antagelsen om at $f$ er strengt voksende følger det at $f(3^n+k)=2\cdot3^n+k$ for $0\leq k \leq 3^n$
og dermed til slutt at $f(2\cdot 3^n+k)=f(f(3^n+k))=3^{n+1}+3k$.

Oppgaven kom jeg over på siden http://www.brilliant.org.

Takk for informasjonen:) (litt uoversiktlig side, syns jeg)

Er enig med deg der, men siden har en god del fine oppgaver.

For ordens skyld tar jeg med beviset for at $f(1)=2$ og $f(2)=3$. Anta først at $f(1)=1$, da er $3=f(f(1))=f(1)$. Dette er
selvfølgelig en motsigelse, så $f(1)>1$. Siden $f$ er strengt voksende må da generelt $f(n)>n\;\; (i)$. Hvis $f(1)\geq 3$, så
har vi at $3=f(f(1))\geq f(3)$, men dette stemmer ikke med $(i)$. Da er den eneste gjenværende muligheten at $f(1)=2$. Til
slutt er $f(2)=f(f(1))=3$ som ønsket.