Taiwan IMO Selection Camp

Let the binary representation of the positive integer $n$ be $n = \sum_{i=1}^{k} 2^{r_i}$; through this binary expansion, we can obtain a one-to-one correspondence between $\mathbb{Z}^+$ and the finite nonempty subsets of $\mathbb{Z}^+ \cup \{0\}$: $S_n := \{r_1, r_2, \dots, r_k\}$. We then define $f(a, b)$ to be the unique function satisfying $S_{f(a,b)} = S_a \cup S_b$.

Since $f(a, a) = a$, $f$ is a surjective function. It is also easy to see that $f(a, b) \le a + b$, with equality holding if and only if $S_a \cap S_b = \emptyset$, so (i) holds; (ii) is obvious. By Lucas' theorem, the binomial coefficient $\binom{m}{n}$ is odd if and only if $S_m \subseteq S_n$, so (iii) also holds.

We now prove that this function $f$ is the unique solution.

Step 1. Again by Lucas' theorem, $S_{f(a,b)} \subseteq S_a \cup S_b$.

Step 2. When $S_a$ and $S_b$ are disjoint, $S_{a+b} = S_a \cup S_b$. Hence we obtain $S_{f(a,b)} \subseteq S_{a+b}$, which gives $f(a, b) \ge a + b$. In this case, combined with (i), we know $f(a, b) = a + b$, and thus $S_{f(a,b)} = S_a \cup S_b$.

Step 3. If $a, b < 2^k$, we prove that $f(a, b) < 2^k$: if not, then there exists $\ell \ge k$ such that $\ell \in S_{f(a,b)}$. In this case we have $S_{f(a,b)} \supseteq S_a \cup \{\ell\}$, and by Step 2 we know $f(a, b) \ge a + 2^\ell > a + b$, a contradiction.

Step 4. We consider a solution $(a_0, b_0)$ of $f(a, b) = 2^k$. By condition (iii) we know $\max\{a_0, b_0\} \le f(a_0, b_0) = 2^k$. But according to Step 3, $a_0, b_0$ cannot both be less than $2^k$. Hence $\max\{a_0, b_0\} = 2^k$, and without loss of generality we may assume $a_0 = 2^k$. If $b_0 < 2^k$, then by Step 2 we get $f(a_0, b_0) = a_0 + b_0 > 2^k$, a contradiction. And by the surjectivity of $f$ we know $f(2^k, 2^k) = 2^k$.

Step 5. If $S_a \cap S_b$ is nonempty, take $t \in S_a \cap S_b$. By (ii) and Step 2 we obtain
$$\begin{align*} f(a, b) &= f(f(a - 2^t, 2^t), f(b - 2^t, 2^t)) \\ &= f(f(a - 2^t, f(2^t, 2^t)), b - 2^t) \\ &= f(f(a - 2^t, 2^t), b - 2^t) \\ &= f(a, b - 2^t). \end{align*}$$

Hence by induction we know: if $S_a \cap S_b = S_c$, then $f(a,b) = f(a,b-c) = a+b-c$
(Step 2). Therefore $S_{f(a,b)} = S_{a+b-c} = S_a \cup (S_b \setminus S_c) = S_a \cup S_b$. This completes the proof.