L MOM - Zadanie 5

Zawody matematyczne:

L MOM, 2009

Wyznaczyć wszystkie funkcje $f$ przekształcające zbiór dodatnich liczb całkowitych w zbiór dodatnich liczb całkowitych takie, że dla każdych dwóch dodatnich liczb całkowitych $a$ oraz $b$ istnieje niezdegenerowany trójkąt, którego boki mają długości

$ a,\quad f(b)\quad\text{oraz}\quad f(b+f(a)-1). $

(Trójkąt niezdegenerowany to taki, którego wierzchołki nie leżą na jednej prostej.)

Rozwiązanie

Odpoowiedź: jedyną funkcją spełniającą warunki zadania jest funkcja tożsamościowa, $f(x)=x$ .

Sprawdzimy, że funkcja $f(x)=x$ spełnia warunki zadania. Dla funkcji tej i dla dowolnych dodatnich liczb całkowitych $a$ i $b$ zachodzą nierówności:

$ \begin{split} f(b+f(a)-1)=a+b-1&<a+b=a+f(b),\\ a&<b+a+b-1=f(b)+f(b+f(a)-1)\\ \text{oraz}\quad f(b)=b&<a+b-1+a=f(b+f(a)-1)+a, \end{split} $

czyli liczby $a$ , $f(b)$ oraz $f(b+f(a)-1)$ są długościami boków pewnego niezdegenerowanego trójkąta.

Niech teraz $f$ będzie dowolną funkcją spełniającą warunki zadania. Wykażemy, że dla każdej dodatniej liczby całkowitej $x$ zachodzi równość $f(x)=x$ .

Najpierw udowodnimy, że $f(1)=1$ . W tym celu, dla dowolnej dodatniej liczby całkowitej $x$ , rozważmy liczby całkowite 1, $f(x)$ oraz $f(x+f(1)-1)$ . Są one długościami boków pewnego niezdegenerowanego trójkąta, zatem spełniona jest nierówność $|f(x)-f(x+f(1)-1)|<1$ , czyli

$ f(x+f(1)-1)=f(x). $

Wynika stąd, że gdyby zachodziła nierówność $f(1)>1$ , wówczas funkcja $f$ byłaby funkcją okresową o okresie $f(1)-1$ . Byłaby zatem funkcją ograniczoną, czyli dla pewnej dodatniej liczby $B$ zachodziłaby nierówność $f(x)<B$ dla $x=1,2,\dots$ . Niech $z$ będzie dodatnią liczbą całkowitą spełniającą nierówność $z>2B$ . Wówczas $z>2B>f(1)+f(1+f(z)-1)$ co przeczy temu, że istnieje niezdegenerowany trójkąt, którego boki mają długości $z$ , $f(1)$ oraz $f(1+f(z)-1)$ . Zatem nie może zachodzić $f(1)>1$ . Dowiedliśmy w ten sposób, że $f(1)=1$ .

Niech $x$ będzie dodatnią liczbą całkowitą. Rozważmy trójkąt o bokach mających długości $x$ , $f(1)=1$ oraz $f(1+f(x)-1)=f(f(x))$ . Zachodzi nierówność

$ |x-f(f(x))|<1, $

z której wynika, że $f(f(x))=x$ . W szczególności oznacza to, że funkcja $f$ jest różnowartościowa.

Niech $d=f(2)-1$ . Zauważmy, że $d\geq1$ , gdyż $f(2)\neq f(1)=1$ . Ponieważ dla każdej dodatniej liczby całkowitej $x$ liczby 2, $f(x)$ oraz $f(x+f(2)-1)=f(x+d)$ są długościami boków pewnego niezdegenerowanego trójkąta, więc zachodzi nierówność

$ |f(x)-f(x+d)|<2, $

czyli

$ (1) \qquad f(x+d)\in\{f(x)-1,f(x),f(x)+1\}. $

Stosując indukcję udowodnimy, że $f(1+kd)=1+k$ dla $k=0,1,\dots$ . Wykazaliśmy już, że $f(1+0\cdot d)=f(1)=1=1+0$ . Z kolei $f(1+1\cdot d)=f(f(2))=2=1+1$ . Załóżmy, że $f(1+kd)=1+k$ dla $k=0,1,\dots,n$ , gdzie $n\geq1$ . Wówczas z (1) wynika, że $f(1+(n+1)d)=f((1+nd)+d)$ jest jedną z liczb

$ f(1+nd)-1,\quad f(1+nd)\quad\text{oraz}\quad f(1+nd)+1. $

Z tego, że funkcja $f$ jest różnowartościowa oraz $d>0$ wynika, że

$ \begin{split} f(1+(n+1)d)&\neq f(1+nd)\\ \text{oraz}\quad f(1+(n+1)d)&\neq f(1+(n-1)d)=1+(n-1)=\\&\quad=(1+n)-1=f(1+nd)-1,\\ \text{zatem}\quad f(1+(n+1)d)&=f(1+nd)+1=(1+n)+1=1+(n+1). \end{split} $

Tym samym dowiedliśmy, że $f(1+kd)=1+k$ dla $k=0,1,\dots$ .

Aby zakończyć rozwiązanie zadania należy wykazać, że $d=1$ . Zauważmy, że

$ f(2)=1+(f(2)-1)=1+d=f(1+d\cdot d), $

czyli, wobec różnowartościowości funkcji $f$ , mamy $2=1+d^2$ . Zatem $d=1$ i $f(1+k)=1+k$ dla $k=0,1,\dots$ . Tym samym dowiedliśmy, że $f(x)=x$ dla każdej dodatniej liczby całkowitej $x$ .