in 5 komt een 3hoek voor

Opgave - IMO 2009 dag 2 vraag 2

Vind alle functies $f$:$ \mathbb{N} \to \mathbb{N}$, zodat $\forall a, b \in \mathbb{N} $ geldt dat er een niet-ontaarde driehoek bestaat met zijdelengten
$ a, f(b) \text{ en } f(b + f(a) - 1).$

Oplossing

Merk op dat het hier om de Engelse natuurlijke getallen gaat (zonder 0); anders zou nul ook zijn inbegrepen en krijg je door $a=0$ te nemen een driehoek met zijde $0$, wat onmogelijk is.

Er bestaat een niet-ontaarde driehoek met zijdelengten $x,y,z$ als en slechts als $x+y>z$, $x+z>y$, $z+y>x$. Dit is equivalent met $x+y>z>|x-y|$; dan zal immers $x+y>z$, $z>x-y$, $z>y-x$. We kunnen de voorwaarde dus formuleren als: $\forall a,b \in \mathbb{N} a+f(b)>f(b+f(a)-1)>|a-f(b)|$. Omdat elke term van de ongelijkheid een natuurlijk getal is, voldoet een functie $f \mathbb{N} \rightarrow \mathbb{N}$ als en slechts als $\forall a,b \in \mathbb{N} a+f(b)-1 \ge f(b+f(a)-1) \ge |a-f(b)|+1$. Zij die laatste vergelijking hetzelfde als $P(a,b)$.

Wee bewijzen nu volgende lemma's:

Lemma 1: $f(1)=1$.

Bewijs: Beschouw $P(1,b)$. We zien dat $f(b) \ge f(b+f(1)-1) \ge f(b)$, dus $f(b)=f(b+f(1)-1)$. Stel $f(1) \neq 1$, dan $f(1)>1$. Stel dus $f(1)=n+1$ met $n>0$. Nu zal $f(b+n)=f(b)$, de functie is dus periodiek. Het is niet moeilijk in te zien dat $x \equiv y \pmod n \Rightarrow f(x)=f(y)$. Omdat er slechts $n$ verschillende restklassen zijn modulo $n$, neemt de functie niet meer dan $n$ waarden aan. Daardoor bereikt ze een maximale waarde, zeg $q$. Dan zal $\forall x \in \mathbb{N} f(x) \le q$ (1), per definitie.

Beschouw nu $P(2q,b)$. Wegens (1) zien we dat $q \ge f(b+f(2q)-1) \ge 2q+1-f(b)$, dus $f(b) \ge q+1$, contradictie! Daarom kan $f$ niet periodiek zijn en is bijgevolg $f(1)=1$, waarmee het lemma bewezen is.

Lemma 2: $f$ is bijectief en $f(f(x))=x$.

Bewijs: Beschouw $P(1,a)$. Wegens lemma 1 zien we dat $a \ge f(f(a)) \ge a \Rightarrow f(f(a))=a$. Omdat de functie $g(x)=x$ bijiectief is, zal $f$ dat ook zijn (daar $f(f( ))$ bijectief is), waarmee het lemma bewezen is.

Lemma 3: $n=f((n-1)f(2)-(n-2))$.

Bewijs: Zij, voor het gemak, $k=f(2)$. Dan zal $k>1$, want anders zou $f(k)=1$. Dan zal $f(k)=2$ wegens lemma 2. We geven nu een bewijs van het lemma per inductie:

Inductiebegin: Zij $n=1$. dan zegt het lemma dat $f(0 \cdot k+1)=f(1)=1$, wat waar is. Voor $n=2$, staat er $f(f(2))=2$, wat waar is wegens Lemma 2.

Inductiehypothese: De stelling geldt voor alle waarden van $n$ kleiner dan of gelijk aan $q$.

Inductiestap: Beschouw $P(k,q)$. We zien dat $q+1 \ge f(k+f(q)-1) \ge q-1$. Nu weten we wegens de inductiehypothese dat $f(q)=f(f((q-1)k-(q-2)))=(q-1)k-(q-2)$. Dus $q+1 \ge f(qk-(q-1)) \ge q-1$. Nu is, omdat $k>1$, de functie $g(q)=(k-1)(q-1)+1$ strikt stijgend over $\mathbb{N}$. Wegens de inductiehypothese zal $f((q-1)k-(q-2))=q$ en $f((q-2)k-(q-3))=q-1$. Dus kan $f(qk-(q-1))$ onmogelijk gelijk zijn aan $q$ of $q-1$ (stel namelijk dat ze toch gelijk zouden zijn, dan zou wegens de injectiviteit van $f$ gelden dat $g(q+1)=g(q)$ of $g(q+1)=g(q-1)$, een duidelijke onmogelijkheid omdat $g$ strikt stijgend is). Daarom moet $f(qk-(q-1))=q+1$. Daarmee is het lemma bewezen.

Merk nu op dat uit lemma 2 en 3 volgt dat $f(n)=(k-1)n-k+2$. Maar $f$ is tevens surjectief, dus $\forall s \in \mathbb{N} \exists r \in \mathbb{N} f(r)=s$, dus $(k-1)r-k+2=s$ heeft altijd een oplossing. Zij $s=2$; we zien dat $(k-1)(r-1)=1$. Omdat $k$ en $r$ beiden natuurlijk zijn, kan dit enkel als $k=r=2$. Dus $f(n)=n-2+2=n$. Deze functie voldoet ook: er geldt namelijk dat $a+b>a+b-1>|a-b|$. Q.E.D.