functievergelijking
Opgave - CanMO 1969 vraag 8
Zij $f$ een functie met de volgende eigenschappen:
a) $f(n)$ is gedefinieerd voor ieder natuurlijk getal $n$;
b) $f(n)$ is een natuurlijk getal;
c) $f(2)=2$;
d) $f(mn)=f(m)f(n)$ voor alle $m$ en $n$;
e) $f(m)>f(n)$ als $m>n$.
Bewijs dat $f(n)=n$.
- login om te reageren
Oplossing
We bewijzen eerst door middel van inductie dat $f(2^n)=2^n$:
Voor $n=1$ geldt inderdaad dat $f(2)=2$ (gegeven)
Stel nu dat het bewezen is dat $f(2^n)=2^n$, dan geldt:
$f(2^{n+1})=f(2^n)f(2)=2^n.2=2^{n+1}$
Dus elke macht van twee wordt op dezelfde waarde afgebeeld door $f$.
Tussen $2^n$ en $2^{n+1}$ liggen er $2^n-1$ getallen. Geen twee van deze getallen mogen hetzelfde beeld hebben onder $f$.
Tussen $f(2^n)$ en $f(2^{n+1})$ liggen er $2^n-1$ getallen.
Bovendien zijn de rij $$a,a+1,a+2,...$$
en de rij van de respectievelijke beelden $$f(a), f(a+1), f(a+2), ...$$ gelijk gesorteerd (wegens eigenschap e)
Bijgevolg krijgen we dat $f(a)=a$.
[Edit: Er is niet vermeld wat $f(0)$ en $f(1)$ zijn.
$f(0)=f(0.2)=f(0).f(2) \iff f(0) = 0$
$f(2.1)=f(2).f(1) \iff f(1)=1$]