, 2009

If $f(b+v_2) = f(b)-1$, then setting $a=2$ and $b = b+v_2$ in the given condition leads to the triangular triple $\{2, f(b+v_2) = f(b)-1, f(b+2v_2)\}$. By the triangle inequality and (c), the only possible value of $f(b+2v_2)$ is $f(b)-2$. Likewise, we can deduce that $f(b+3v_2) = f(b)-3$, and so on. But this impossible, because $f$ takes values in the set of positive integers.
We conclude that $f(b + v_2) = f(b) + 1$. By a simple induction, we have $f(b + kv_2) = f(b) + k$ for positive integers $k$. In particular, setting $b = 1$ yields
$$f(1) = 1, \quad f(1+v_2) = 2, \quad f(1+2v_2) = 3, \quad \dots, \quad f(1+kv_2) = 1+k, \dots \quad (1)$$
Setting $k = v_2$ in (1) gives
$$f(1 + v_2^2) = 1 + v_2.$$
By (b), we conclude that $1+v_2^2 = f(f(1+v_2^2)) = f(1+v_2) = 2$, implying that $v_2 = 1$. Substituting $v_2 = 1$ in (1) leads to the solution $f(x) = x$.

We start with a lemma that is slightly stronger than Freiman's theorem. Part of this lemma could be very helpful in certain proofs of USAMO 2009 problem 2 and IMO 2000 problem 1.

Lemma 1. Let $A, B$ be finite nonempty subsets of $\mathbb{Z}$. Then the set $A+B = \{a+b : a \in A, b \in B\}$ has cardinality at least $|A| + |B| - 1$. Equality holds if and only if either $A$ and $B$ are arithmetic progressions with equal difference or at least one of $|A|$ or $|B|$ is equal to 1. (Here $|S|$ denotes the number of elements in $S$.)

Proof. Let $A = \{a_1 < a_2 < \dots < a_{|A|}\}$ and $B = \{b_1 < b_2 < \dots < b_{|B|}\}$. The following $|A| + |B| - 1$ distinct elements, arranged in increasing order, are in $A+B$:
$$a_1 + b_1 < \dots < a_1 + b_{|B|} < a_2 + b_{|B|} < \dots < a_{|A|+|B|}.$$
Therefore $|A+B| \ge |A| + |B| - 1$, establishing the inequality.

Next we consider the equality case. Let $c_i$ denote the value of the $i^{\text{th}}$ element in the above list. Assume that $|A+B| = |A| + |B| - 1$ and $|A|, |B| > 1$. For any $1 < i \le |A|$ and $1 < j \le |B|$, consider the following list of $|A| + |B| - 1$ distinct elements in $A+B$:
$$\underbrace{a_1 + b_1 < \dots < a_1 + b_{j-1}}_{j-1 \text{ elements}} < \underbrace{a_2 + b_{j-1} < \dots < a_i + b_{j-1}}_{i-1 \text{ elements}} < \underbrace{a_i + b_j < \dots < a_i + b_{|B|}}_{|B|-j+1 \text{ elements}} < \underbrace{a_{i+1} + b_{|B|} < \dots < a_{|A|} + b_{|B|}}_{|A|-i \text{ elements}}.$$
This list must be the same as before. Therefore $a_i+b_{j-1} = c_{i+j-2}$. Likewise $a_{i-1}+b_j = c_{i+j-2}$. Therefore $a_i + b_{j-1} = a_{i-1} + b_j$ and $a_i - a_{i-1} = b_j - b_{j-1}$. Hence, both $A$ and $B$ are arithmetic progressions with the same common difference. $\square$

Now we can complete our proof in a few steps.

(d) For a positive integer $n$, let $I_n = \{1, 2, \dots, n\}$, $\mathcal{A}_n = \{f(i) : i \in I_n\}$. Because $f(f(n)) = n$, the given condition implies the more symmetric fact that $\{a, b, f(f(a) + f(b) - 1)\}$ is triangular. Hence if $a, b \in I_n$, then $f(f(a) + f(b) - 1) \le 2n - 1$.

(e) Combining (c) and (d), we conclude that $|\{f(a) + f(b) - 1 : a, b \in I_n\}| \le 2n - 1$; that is,
$$|\mathcal{A}_n + \mathcal{A}_m| = |\{f(a) + f(b) : a, b \in I_n\}| = |\{f(a) + f(b) - 1 : a, b \in I_n\}| \le 2n - 1 = 2|\mathcal{A}_n| - 1.$$

(f) By the lemma and (e), we deduce that $\mathcal{A}_n$ is an $n$-element set with its elements forming an arithmetic progression starting with $f(1) = 1$.

(g) Consider the elements in $\mathcal{A}_n$ and $\mathcal{A}_{n+1}$. Clearly, $\mathcal{A}_n \subset \mathcal{A}_{n+1}$ and $\mathcal{A}_{n+1}$ has one additional element. If $n \ge 3$, this additional element must be at one of the ends of the arithmetic sequence formed by the elements in $\mathcal{A}_n$. But both sets have minimum value $f(1) = 1$. Hence this new element must be at the upper end. We conclude that $f$ is linear except possibly for $f(2)$ and $f(3)$.

(h) Note that (b) also implies that $f$ is surjective. Combining with (c), we know that $f$ is bijective. By (g), we must have $f(n) = n$ for $n \ge 4$.

(g) For $a = 2$ and large $b$, $\{2, b, f(2)+b-1\}$ is triangular if and only if $f(2)+b-1 < 2+b$, implying that $f(2) = 2$. Likewise, or using injectivity, we have $f(3) = 3$, completing our proof.