Competition problem — Combinatorics

Library / /30 of 105

Combinatorics Difficulty 5.4 AIME, harder Prove it JBMO

Problem:

Several (at least two) segments are drawn on a board. Select two of them, and let $a$ and $b$ be their lengths. Delete the selected segments and draw a segment of length $\frac{a b}{a+b}$ . Continue this procedure until only one segment remains on the board. Prove:

a) the length of the last remaining segment does not depend on the order of the deletions.

b) for every positive integer $n$ , the initial segments on the board can be chosen with distinct integer lengths, such that the last remaining segment has length $n$ .

Solution

Solution:

a) Observe that $\frac{1}{\frac{a b}{a+b}} = \frac{1}{a} + \frac{1}{b}$ . Thus, if the lengths of the initial segments on the board were $a_{1}, a_{2}, \ldots, a_{n}$ , and $c$ is the length of the last remaining segment, then $\frac{1}{c} = \frac{1}{a_{1}} + \frac{1}{a_{2}} + \ldots + \frac{1}{a_{n}}$ , proving a).

b) From a) and the equation $\frac{1}{n} = \frac{1}{2n} + \frac{1}{3n} + \frac{1}{6n}$ it follows that if the lengths of the starting segments are $2n, 3n$ and $6n$ , then the length of the last remaining segment is $n$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.