Find all one-to-one mappings $f:\mathbb{N}\to\mathbb{N}$ such that for all positive integers $n$ the following relation holds: \[ f(f(n)) \leq \frac {n+f(n)} 2 . \]
Problem
Source: Romanian ROM TST 2004, problem 3, created by Cristi Mortici
Tags: induction, function, algebra proposed, algebra
pbornsztein
03.05.2004 01:11
Let $f$ be a solution. Notice that for each $n$ we then have $f(f(n)) \leq \max\{n,f(n)\}$, with equality if and only if $f(n)=n$. Let $f^k$ denote the $k^{th}$ iterate of $f$. Suppose that there exists $a$ such that $a > f(a).$ Then $f^2(a) < a$ and by an easy induction $f^k(a) < a$ for all $k>0$ (1). Since there is a finite number of integers in $\{1,2,...,a-1\}$ it follows that there exist $0<i<j$ such that $f^i(a) = f^j(a) = f^i(f^{j-i}(a))$ and using injectivity of $f$ it leads to $f^{j-i}(a) = a$ which contradicts (1). Thus, $a \leq f(a)$ for each $a>0$. Then $f(a) \leq f(f(a))$ for each $a$. On the other hand, from the initial remark we also have $f(f(a)) \leq f(a)$. Thus $f(a) = f(f(a))$ for each $a$, and using injectivity of $f$ we deduce that $f(a) = a$. Conversely, it is easy to verify that $f(x) = x$ is indeed a solution. Pierre.
3X.lich
03.05.2004 07:37
Can you spare us some easy questions, pbornsztein? BTW, very nice solution (and typeset).
pbornsztein
03.05.2004 09:18
Sorry.....But I left two days. Pierre.
Omid Hatami
26.05.2004 06:47
I also solved it with your solution in 45 minutes
Babai
21.07.2012 18:58
As injective so either monotonically increasing or decreasing.If it is a decreasing function then it makes a contradiction as suppose $f(a)=t$ then $f(a+t-1)=1$ and after that it gets no value.So must be a monotonic increasing function. So,$f(1)\geq 1$ and likewise $f(n)\geq n$. Now see $f(n)\geq \frac{n+f(n)}{2}\geq f(f(n))\geq f(n)$ so,all are equal which gives $f(n)=n$.
chaotic_iak
22.07.2012 06:44
No, injectivity doesn't mean monotonicity. The function $f(1) = 2, f(2) = 1$ and $f(x) = x$ otherwise is injective (bijective actually) but not monotonic.
subham1729
23.07.2012 05:01
My first solution is same as pbornsztein's solution 2nd solution : Theorem : If $a_n$ be a sequence of non negative numbers such that $2a_{n+1}\leq a_n+a_{n-1}$ then sequence is bounded. Now choosing $a_k=f^k(n)$ we are done.
mavropnevma
23.07.2012 05:20
But your theorem is almost precisely what pbornsztein has done. If $2a_{n+1} \leq a_n + a_{n-1}$, then $a_{n+1} \leq \max\{a_n, a_{n-1}\}$. And since then clearly $\max\{a_{n+1}, a_{n}\} \leq \max\{\max\{a_n, a_{n-1}\}, a_{n}\} \leq \max\{a_n, a_{n-1}\}$, we're done.
bobthesmartypants
15.04.2016 23:45
Note that $f(f(n))\le \dfrac{n+f(n)}{2}\le \text{max}\{n, f(n)\}$. Similarly, $f(f(f(n)))\le \text{max}\{f(n), f(f(n))\}\le \text{max}\{n, f(n)\}$, and it is easy to apply induction to prove $f^k(n)\le \text{max}\{n, f(n)\}$. Thus, the sequence $n, f(n), f(f(n)), \ldots$ is a bounded function, and therefore eventually periodic. Now suppose that the fundamental period $p$ of this sequence is greater than $1$. Then for big enough $n_0$, for all $k> n_0$, $f^{k+p}(n)=f^k(n)$. Now consider $\max\limits_{1\le i \le p} f^{k+i}(n)=f^{k+i_0}(n)$ for some $1\le i_0\le p $; we have $2f^{k+i_0}(n) > f^{k+i_0-1}(n)+f^{k+i_0-2}(n)\implies f^{k+i_0}(n) > \dfrac{ f^{k+i_0-1}(n)+f^{k+i_0-2}(n)}{2}$ and the inequality is strict because $p\ge 2$; but this gives a contradiction with the problem condition. Thus, eventually $f^k(n)$ becomes constant. Thus, for $k\ge n_0$ for big enough $n_0$, $f^{k+1}(n)=f^k(n)$. However, since $f$ is bijective, it follows that $f(n)=n$ which is our only solution.
MathDelicacy12
23.08.2019 18:13
Valentin Vornicu wrote: Find all one-to-one mappings $f:\mathbb{N}\to\mathbb{N}$ such that for all positive integers $n$ the following relation holds: \[ f(f(n)) \leq \frac {n+f(n)} 2 . \] We claim $f(n) = n$ are the only solutions. It is enough to show that $f(n) \leq n \quad \forall n \in \mathbb{N}$. Suppose $f(n) < n$ for some $n \in \mathbb{N}$. Note that by induction $f^k(n) < f(n) \quad \forall n \in \mathbb{N}$. Let $(a_k)_{k \geq 0}$ be a sequence defined by $a_k = f^k(n) \quad \forall k \in \mathbb{N} , \quad a_0 = n$. Note that the sequence is bounded and discrete. So, there exist $k, l \in \mathbb{N}$ such that $a_k = a_l$. By the injectivity of $f$, we have $a_{k-l} = a_0$ which implies that $a_{k-l-1} = a_1$ which leads to a contradiction. $\blacksquare$
Assassino9931
11.06.2022 12:26
I think this one can be solved without using injectivity.
Fix $n$ and let $a_m = f(f(\cdots f(n) \cdots))$ (the number of iterations of $f$ is $m$, treating $a_0 = n$) for $m\geq 0$. Substituting $n$ with $a_m$ in the given inequality, we get $a_{m+2} \leq \frac{a_{m+1} + a_m}{2}$, i.e. $2a_{m+2} \leq a_{m+1} + a_m$. If this was an equality we would be able to solve this linear recurrence - this motivates to try to prove (by strong induction on $m\geq 0$) the inequality $a_m \leq \frac{a_0+2a_1}{3} + \frac{2}{3}(a_0-a_1)(-\frac{1}{2})^m$.
For $m=0$ and $m=1$ equality holds. Now if we assume that the claim holds for all indices not exceeding some $m\geq 1$, then
$$a_{m+1} \leq \frac{a_{m} + a_{m-1}}{2} \leq \frac{a_0+2a_1}{3} + \frac{1}{3}(a_0-a_1)\left(-\frac{1}{2}\right)^{m-1}\left(1 + \left(-\frac{1}{2}\right)\right) = \frac{a_0+2a_1}{3} + \frac{2}{3}(a_0-a_1)\left(-\frac{1}{2}\right)^{m+1} $$which completes the induction.
On the other hand, $a_{m} > 0$ and so $0 < \frac{a_0+2a_1}{3} + \frac{2}{3}(a_0-a_1)\left(-\frac{1}{2}\right)^{m}$, i.e. $2(a_1-a_0)(-\frac{1}{2})^m < a_0 + 2a_1$. Pick $m$ to be odd, then (as $a_0 = n > 0$ and $a_1 = f(n) > 0$) after multiplying with $(-2)^m = -2^m < 0$ we get $2a_1 - 2a_0 > -2^ma_0 - 2^{m+1}a_1 \Leftrightarrow \frac{a_1}{a_0} > \frac{2^m+2}{2^{m+1}+2}$. The right-hand side of the latter can attain values arbitrarily close to $1$ and so choosing $m$ to be sufficiently large yields $a_1 \geq a_0$, i.e. $f(n) \geq n$.
Hence $f(n) \geq n$ for all $n$. Now it is obvious how to finish. We deduce $f(f(n)) \geq f(n)$ and now the given condition implies $f(n) \leq \frac{n+f(n)}{2}$, i.e. $f(n) \leq n$. Therefore $f(n) = n$ and direct verification shows that this function works.