50-я Международная Математическая OлимпиадаГермания, Бремен, 2009 год

Найдите все функции $f:\mathbb{N}\to \mathbb{N}$ (то есть функции, определенные на множестве всех целых положительных чисел и принимающие целые положительные значения) такие, что для любых целых положительных $a$ и $b$ существует невырожденный треугольник, длины сторон которого равны трем числам $a$, $f(b)$, $f\left( b+f(a)-1 \right)$.
(Треугольник называется невырожденным, если его вершины не лежат на одной прямой.)

Комментарий/решение

Ответ 5

Используем общеизвестный факт который гласит:

В невырожденном треугольнике сумма длин двух сторон больше чем длинна третьей стороны

$$$$

$P(a,b) \rightarrow (1,1)$

$f(1)=f(f(1))$

$P(a,b) \rightarrow (1,f(1))$

$f(1)=f(2f(1)-1)$

$ f(1)=1+k$

$P(a,b) \rightarrow (1,b)$

$f(b)=f(b+k)$

Для любого $b$

$P(a,b) \rightarrow (mk+1,1)$

$f(1+f(mk+1)-1)+f(1)>mk+1$

$f(1)=f(1+k)=f(1+2k)=\dots=f(mk+1)$

$f(f(1))=f(1)$

$2f(1)>mk+1$

Внезависимости от выбора числа $m$

$2k+2>mk+1$

$1>mk-2k \rightarrow k=0$

$$$$

$P(a,b) \rightarrow (a,1)$

$a=f(f(a))$

$$$$

$f(x)=f(y)$

$f(f(x))=f(f(y))$

$x=y$

$f(x)-$ инъективная

$$$$

$P(a,b) \rightarrow (2,b)$

$f(2)-1=k$

$f(b)+4>f(b+k)+2>f(b)$

$f(b+k)=f(b),f(b)-1,f(b)+1$

$f(b+k)=f(b)$ аналогичен случаю $f(1) \ne 1$

$f(b+k)=f(b)-1$

$f(b+k)=f(b+2k)-1= \dots f(b+kn)+n-1$

$f(b)-n=f(b+kn)$

$n=f(b)-1$

$1=f(b+f(b)k-f(b))$

$b=2$

$f(1)=f(2+(k)^2)$

Поскольку $f(x)-$ инъективная

$(k)^2=-1 \rightarrow \varnothing$

$$$$

$f(b+k)=f(b)+1$

$f(b+kn)=f(b)+n$

$f(1+kn)=n+1$

$f(k^2+1)=f(2)$

$k^2+1=2$

$k^2=1 \rightarrow k=1$

$$$$

Раз: $f(1+nk)=n+1$

То: $f(n+1)=n+1$

Значит: $f(x)=x$

$$$$

Ответ: $f(x)=x$

У меня вопрос, откуда получили, что $f(1)=f(f(1))?$

$f(1)+1>f(1+f(1)-1)$

$f(1+f(1)-1)+1>f(1)$

$$$$

Что дает нам равенство этих двух значений

$P(1,a):$

$f(1)=f(a+f(1)-1)$

Если $f(1)≠1$ то $f$ периодично с константой $k=|f(1)-1|$.

$a>f(b)+f(b+f(a)-1)$.Увеличиваем $a$ на $k$ и выйдет противоречие.Значит $f(1)=1$.

$P(a,1):$

$f(f(a))=a$

Значит очевидно $f$ биективная.Пусть $n$ такое что $f(n)=2$.Докажем что $f(k)=(k-1)n-k+2$ по индукции.Пусть это верно для всех $k=1,2,..k$

$P(k,n):$

$k+2>f(kn-k+1)>k$

$f((k-1)n-k+2)=k$

$f(n²-2n+2)=n=f(f(n))=f(2)$

$n²-2n+2=2$ и $n=2$.

$f(x)=x$