Let $N$ be the set of positive integers. Find all the functions $f: N\to N$ with $f (1) = 2$ and such that $max \{f(m)+f(n), m+n\}$ divides $min\{2m+2n,f (m+ n)+1\}$ for all $m, n$ positive integers
Problem
Source: Peru IMO TST 2012 p4
Tags: number theory, divides, min, max, positive integers
14.05.2019 16:58
All such functions are $f(x) = x + 1$ and $f(x) = 2x$ which could be easily verified. We'll now prove that these are the only ones. Let $P(x,y)$ be the assertion of $x$ and $y$ to the given equation. Therefore, we get $f(2) \ge 3$. Similarly, note that $f(m + n) + 1 \ge f(m) + f(n)$, which is $f(m + 1) \ge f(m) + 1$. One could then prove that $f(x) \ge x + 1$ for all $x \in \mathbb{N}$. Now, we know that $f(m) + f(n) > m + n$. So $P(m,n)$ is equivalent to \[ f(m) + f(n) | \min \{2m + 2n, f(m + n) + 1 \} \] Now, we know that $f(m) + f(n) \le 2m + 2n$. Plug $n = 1$, then we get $f(m) \le 2m$. Checking $P(2,1)$ gives us: \[ f(2) + 2 | \min \{6, f(3) + 1 \} \]If $f(3) \ge 5$, then we have $f(2) \ge 3$ and $f(2) + 2 | 6$ , giving us $f(2) = 4$. If $f(3) < 5$, then we have $5 \le f(2) + 2 \le f(3) + 1 < 6$ which gives us either $f(2) = 3, f(3) = 4$. Case 01. When $f(1) = 2, f(2) = 3, f(3) = 4$. We will prove by induction that $f(n) = n + 1$ for all $n \in \mathbb{N}$. It is true for $n = 1, 2, 3$. Suppose that it is true for $n = 1, 2, \dots, k$, where $k \ge 3$. Checking $P(k,1)$ gives us \[ k + 3 | \min \{2k + 2, f(k + 1) + 1 \} \]Suppose $f(k + 1) \ge 2k + 1$, then $k + 3 | 2k + 2$ which gives us $k + 3|4$, absurd for $k \ge 3$. Thus, we must have $f(k + 1) \le 2k$ and $k + 3| f(k + 1) + 1$. Suppose $f(k + 1) \not= k + 2$, then $f(k + 1) + 1 \ge 2(k + 3)$ contradicting $f(k + 1) \le 2k $. So, we must have $f(k + 1) = k + 2$. Case 02. When $f(1) = 2, f(2) = 4$, $f(3) \ge 5$. Notice that $P(1,3)$ and $P(2,2)$ gives us \[ f(3) + 2 | \min \{8, f(4) + 1 \} \]\[ 8 | \min \{8, f(4) + 1 \} \]From the second equation, we immediately realize that $f(4) \ge 7$, which then gives us $f(3) = 6$. Now, we will prove that $f(n) = 2n$ for all $n \in \mathbb{N}$. It is true for $n = 1, 2, 3$. Suppose that it is true for $n = 1, 2, 3, \dots, k$. Therefore, $P(k,1)$ gives us \[ 2k + 2 | \min \{ f(k + 1) + 1, 2k + 2\} \]Therefore, we must have $f(k + 1) \ge 2k + 1$. In fact , one can prove $2x - 1 \le f(x) \le 2x$ for all $x \in \mathbb{N}$, Suppose now that there exists an integer $a > 1$ such that $f(a) = 2a - 1$. Then, $P(a,1)$ gives us \[ 2a + 1 | \min \{ 2a + 2, f(a + 1) + 1 \} \]Which is satisfied iff $a = 1$,