Problem 2004

Solution:

We set $M_{n}=1 / 2$ and $m_{n}=1 /(n-1)$. We show that $M_{n}$ is the maximum possible value for the last fraction, while $m_{n}$ is the minimum possible value for the last fraction. The proof consists of two parts: a construction showing that these values are indeed achievable, and a verification of the optimality of these values, that is, that one cannot obtain more or less.

Construction. To obtain $m_{n}$ we pair at each step the two largest numbers written on the board. At the first step we pair $1 / 1$ and $1/2$, obtaining $2 / 3$. At the second step we pair $2 / 3$ and $1 / 3$, obtaining $1 / 2$. Therefore, after two steps the numbers written on the board are
$$\frac{1}{2}, \quad \frac{1}{4}, \quad \frac{1}{5}, \ldots, \quad \frac{1}{n}$$
At this point it is easily shown by induction that at the $k$-th step we will have on the board the numbers
$$\frac{1}{k}, \quad \frac{1}{k+2}, \quad \frac{1}{k+3}, \ldots, \quad \frac{1}{n}$$
and so after $n-2$ steps only $1 /(n-2)$ and $1 / n$ will remain, and composing them gives exactly $m_{n}$.

The construction for $M_{n}$ is analogous, simply pairing at each step the two smallest numbers. At the first step we pair $1 / n$ and $1 /(n-1)$, obtaining $2 /(2 n-1)$. At the second step we pair $2 /(2 n-1)$ and $1 /(n-2)$, obtaining $1 /(n-1)$. Therefore, after two steps we will have on the board the numbers
$$\frac{1}{1}, \quad \frac{1}{2}, \ldots, \quad \frac{1}{n-4}, \quad \frac{1}{n-3}, \quad \frac{1}{n-1}.$$
At this point it is easily shown by induction that at the $k$-th step we will have on the board the numbers
$$\frac{1}{1}, \quad \frac{1}{2}, \ldots, \quad \frac{1}{n-k-2}, \quad \frac{1}{n-k-1}, \quad \frac{1}{n-k+1}.$$
It follows that after $n-2$ steps only $1 / 1$ and $1 / 3$ will remain, and composing them gives exactly $1 / 2$.

Optimality. To show that one cannot obtain more than $M_{n}$ or less than $m_{n}$ we will use the following preliminary result.

Lemma. For every pair of positive rationals $a/b$ and $c/d$ (reduced to lowest terms) the following inequality holds
$$\min \left\{\frac{a}{b}, \frac{c}{d}\right\} \leq \frac{a}{b} \diamond \frac{c}{d} \leq \max \left\{\frac{a}{b}, \frac{c}{d}\right\}.$$
Moreover, either of the two equalities holds if and only if $a / b=c / d$.

To prove the lemma, denote by $m$ the minimum of the two rational numbers, and by $M$ the maximum. This means that $m b \leq a \leq M b$ and $m d \leq c \leq M d$, from which it follows that
$$m=\frac{m b+m d}{b+d} \leq \frac{a+c}{b+d} \leq \frac{M b+M d}{b+d}=M$$
which is exactly the inequality of the claim. The same argument shows that, if $a / b \neq c / d$, then both inequalities are strict.

Let us now show that one cannot obtain more than $M_{n}$. Consider the first number $x / y$ that interacts with $1 / 1$. The number $x / y$ is the result of operations carried out starting from the fractions $\{1 / 2,1 / 3, \ldots, 1 / n\}$, and therefore by the lemma it will necessarily be less than or equal to $1 / 2$. Moreover, if $x / y=1 / 2$, then necessarily the number $1 / 2$ has never been involved in pirate sums up to this point (if it had been involved, by the lemma such sums would have produced numbers strictly less than $1 / 2$). We now distinguish two cases.

- If $x / y<1 / 2$, then $y>2 x$ and hence $y \geq 2 x+1$. It follows that
$$\frac{1}{1} \diamond \frac{x}{y}=\frac{x+1}{y+1} \leq \frac{x+1}{2 x+2}=\frac{1}{2}.$$
- If $x / y=1 / 2$, then obviously the pirate sum with $1 / 1$ produces as result $2 / 3$. Consider now the number $e / f$ that at some point interacts with $2 / 3$. By what we observed previously we know that $e / f$ is the result of operations carried out starting from the fractions $\{1 / 3, \ldots, 1 / n\}$, and therefore by the lemma it will necessarily be less than or equal to $1 / 3$. But then $f \geq 3 e \geq 2 e+1$ and therefore
$$\frac{2}{3} \diamond \frac{e}{f}=\frac{2+e}{3+f} \leq \frac{e+2}{2 e+4}=\frac{1}{2}$$
In both cases we have reduced to having only fractions less than or equal to $1 / 2$, and therefore by the lemma all the subsequent numbers, and in particular the last one remaining, will be less than or equal to $1/2$.

We show in an analogous way that one cannot obtain less than $m_{n}$. Let $z / w$ be the first number that interacts with $1 / n$. By the lemma we know that $z / w \geq 1 /(n-1)$, and that the equality sign holds if and only if the number $1 /(n-1)$ has never been used up to this point. We now distinguish two cases.

- If $z / w>1 /(n-1)$, then $w<(n-1) z$ and hence $w \leq(n-1) z-1$. It follows that
$$\frac{1}{n} \diamond \frac{z}{w}=\frac{z+1}{n+w} \geq \frac{z+1}{n z-z+n-1}=\frac{1}{n-1}$$
- If $z / w=1 /(n-1)$, then obviously the pirate sum with $1 / n$ produces as result $2 /(2 n-1)$. Consider now the number $h / k$ that at some point interacts with $2 /(2 n-1)$. By what we observed previously we know that $h / k$ is the result of operations carried out starting from the fractions $\{1 / 1,1 / 2, \ldots, 1 /(n-2)\}$, and therefore by the lemma it will necessarily be greater than or equal to $1 /(n-2)$. But then $k \leq h(n-2) \leq h(n-1)-1$ and therefore
$$\frac{2}{2 n-1} \diamond \frac{h}{k}=\frac{2+h}{2 n-1+k} \geq \frac{2+h}{2 n-1+h(n-1)-1}=\frac{1}{n-1}$$
In both cases we have reduced to having only fractions greater than or equal to $1 /(n-1)$, and therefore by the lemma from that moment on, and in particular at the end, there will only be numbers greater than or equal to $1 /(n-1)$.