Given two fractions $a/b$ and $c/d$ we define their pirate sum as: $\frac{a}{b} \star \frac{c}{d} = \frac{a+c}{b+d}$ where the two initial fractions are simplified the most possible, like the result. For example, the pirate sum of $2/7$ and $4/5$ is $1/2$. Given an integer $n \ge 3$, initially on a blackboard there are the fractions: $\frac{1}{1}, \frac{1}{2}, \frac{1}{3}, ..., \frac{1}{n}$. At each step we choose two fractions written on the blackboard, we delete them and write at their place their pirate sum. Continue doing the same thing until on the blackboard there is only one fraction. Determine, in function of $n$, the maximum and the minimum possible value for the last fraction.
Problem
Source: ITAMO 2021 Problem 4
Tags: algebra, function
sarjinius
03.03.2022 16:16
We claim that the maximum value of the last remaining fraction is $\boxed{\frac{1}{2}}$ and the minimum value of the last remaining fraction is $\boxed{\frac{1}{n-1}}$.
To get $\frac{1}{2}$, just keep choosing the two smallest remaining fractions on the blackboard. After the first operation, the remaining fractions are $\frac{1}{1}, \frac{1}{2},\dots, \frac{1}{n-2}, \frac{2}{2n-1}$. After the second operation, the remaining fractions are $\frac{1}{1}, \frac{1}{2},\dots, \frac{1}{n-3}, \frac{1}{n-1}$.
We will prove by induction that after $k$ operations, the remaining fractions will be $\frac{1}{1}, \frac{1}{2},\dots, \frac{1}{n-k-4}, \frac{1}{n-k-3}, \frac{1}{n-k-1}$. The claim is true for $k = 0$. Note that $\frac{1}{n-k-3} \star \frac{1}{n-k-1} = \frac{1}{n-k-2}$, so after this operation, the remaining fractions will be $\frac{1}{1}, \frac{1}{2},\dots, \frac{1}{n-(k+1)-4}, \frac{1}{n-(k+1)-3}, \frac{1}{n-(k+1)-1}$. This completes the induction.
Hence, the last two remaining fractions will be $\frac{1}{1}$ and $\frac{1}{3}$, which have a pirate sum of $\frac{1}{2}$.
To get $\frac{1}{n-1}$, just keep choosing the two largest remaining fractions on the blackboard. After the first operation, the remaining fractions are $\frac{2}{3}, \frac{1}{3}, \frac{1}{4},\dots, \frac{1}{n-1}, \frac{1}{n}$. After the second operation, the remaining fractions are $\frac{1}{2}, \frac{1}{4},\dots, \frac{1}{n-1}, \frac{1}{n}$.
We will prove by induction that after $k$ operations, the remaining fractions will be $\frac{1}{k+2}, \frac{1}{k+4}, \frac{1}{k+5},\dots, \frac{1}{n-1}, \frac{1}{n}$. The claim is true for $k = 0$. Note that $\frac{1}{k+2} \star \frac{1}{k+4} = \frac{1}{k+3}$, so after this operation, the remaining fractions will be $\frac{1}{(k+1)+2}, \frac{1}{(k+1)+4}, \frac{1}{(k+1)+5},\dots, \frac{1}{n-1}, \frac{1}{n}$. This completes the induction.
Hence, the last two remaining fractions will be $\frac{1}{n-2}$ and $\frac{1}{n}$, which have a pirate sum of $\frac{1}{n-1}$.
Lemma. For any pair of positive rationals $\frac{a}{b}$ and $\frac{c}{d}$ in lowest terms, we have $\text{min}\left\{\frac{a}{b}, \frac{c}{d}\right\} \le \frac{a}{b} \star \frac{c}{d} \le \text{max}\left\{\frac{a}{b}, \frac{c}{d}\right\}$, and any of the two equalities holds if and only if $\frac{a}{b} = \frac{c}{d}$. Proof of lemma. Let $m = \text{min}\left\{\frac{a}{b}, \frac{c}{d}\right\}$ and $M = \text{max}\left\{\frac{a}{b}, \frac{c}{d}\right\}$. Then $mb \le a \le Mb$ and $md \le c \le Md$, so $m = \frac{mb + md}{b + d} \le \frac{a + c}{b + d} \le \frac{Mb + Md}{b + d} = M$. Note that both inequalities are strict if $\frac{a}{b} \ne \frac{c}{d}$, and both equalities hold if $\frac{a}{b} = \frac{c}{d}$, thus proving the lemma.
To show that $\frac{1}{2}$ is indeed the maximum value of the last remaining fraction, we will show that at some point, the largest remaining fraction is at most $\frac{1}{2}$. Let $\frac{x}{y}$ be the first fraction to be paired up with $\frac{1}{1}$. Note that $\frac{x}{y}$ is obtained from operations involving only the fractions $\frac{1}{2}, \frac{1}{3},\dots, \frac{1}{n}$, so by the lemma, $\frac{x}{y} \le \frac{1}{2}$.
If $\frac{x}{y} < \frac{1}{2}$, then $y \ge 2x + 1$. Hence, $\frac{1}{1} \star \frac{x}{y} = \frac{x + 1}{y + 1} \le \frac{x+1}{2x+2} = \frac{1}{2}$. At this point, the largest remaining fraction is at most $\frac{1}{2}$.
If $\frac{x}{y} = \frac{1}{2}$, then $\frac{1}{1} \star \frac{1}{2} = \frac{2}{3}$. Since $\frac{1}{1}$ and $\frac{1}{2}$ cannot be the last two fractions on the blackboard, $\frac{2}{3}$ will eventually be paired with a fraction, let this be $\frac{z}{w}$. By the lemma, $\frac{z}{w} \le \frac{1}{3}$ and $w \ge 3z \ge 2z+1$. Thus, $\frac{2}{3} \star \frac{z}{w} = \frac{z+2}{w+3} \le \frac{z+2}{2z+4} = \frac{1}{2}$.
Hence, we have shown that $\frac{1}{2}$ is indeed the maximum value of the last remaining fraction.
To show that $\frac{1}{n-1}$ is indeed the minimum value of the last remaining fraction, we will show that at some point, the smallest remaining fraction is at least $\frac{1}{n-1}$. Let $\frac{x}{y}$ be the first fraction to be paired up with $\frac{1}{n}$. Note that $\frac{x}{y}$ is obtained from operations involving only the fractions $\frac{1}{1}, \frac{1}{2},\dots, \frac{1}{n-1}$, so by the lemma, $\frac{x}{y} \ge \frac{1}{n-1}$.
If $\frac{x}{y} > \frac{1}{n-1}$, then $y \le nx - x - 1$. Hence, $\frac{1}{n} \star \frac{x}{y} = \frac{x + 1}{y + n} \ge \frac{x+1}{nx+n-x-1} = \frac{1}{n-1}$. At this point, the smallest remaining fraction is at least $\frac{1}{n-1}$.
If $\frac{x}{y} = \frac{1}{n-1}$, then $\frac{1}{n} \star \frac{1}{n-1} = \frac{2}{2n-1}$. Since $\frac{1}{n}$ and $\frac{1}{n-1}$ cannot be the last two fractions on the blackboard, $\frac{2}{2n-1}$ will eventually be paired with a fraction, let this be $\frac{z}{w}$. By the lemma, $\frac{z}{w} \ge \frac{1}{n-2}$ and $w \le nz-2z \le nz-z-1$. Thus, $\frac{2}{2n-1} \star \frac{z}{w} = \frac{z+2}{w+2n-1} \ge \frac{z+2}{nz+2n-z-2} = \frac{1}{n-1}$.
Hence, we have shown that $\frac{1}{n-1}$ is indeed the minimum value of the last remaining fraction.