Ukrajina 2008

As $(a+b)>(a-b)$, you can not obtain $1$ performing the operations allowed. Therefore it should be written on the board, but one number is not enough. Let's show that two numbers will be enough. Let another number of the two be $x$. $\frac{x+1}{x-1}$ is the only number which can be obtained in the first step. Since it is a natural number, $\frac{x+1}{x-1}\ge 2\Rightarrow (x+1)\ge 2x-2$ or $x\le 3$. Thus the second number should be $2$ or $3$. We obtain the two possible sets: $\{1,2\}$ and $\{1,3\}$.

Let's prove that they both satisfy the condition. As $\frac{2+1}{2-1}=3$ and $\frac{3+1}{3-1}=2$, in the first step we obtain the set $\{1,2,3\}$ in both cases. Now we have to prove that any natural number greater than $3$ can be obtained from these three numbers.

Let's assume that we've already obtained the set $\{1,2,3,...,(2k+1)\}$. Let's show how we can obtain the next two numbers. We obtain number $\frac{(k+2)+(k+1)}{(k+2)-(k+1)}=2k+3$ from numbers $(k+1),(k+2)$. Next we obtain $\frac{(2k+3)+(2k+1)}{(2k+3)-(2k+1)}=2k+2$ from numbers $(2k+3),(2k+1)$. This implies the desired result.