Open Contests

Question

Kärt writes the fractions 12 and 13 on the blackboard and Märt writes 10 positive integers on the paper, which he does not show to Kärt. Then Kärt starts to write fractions on the blackboard by the following rule: on each step she chooses two fractions ab and cd which are already on the blackboard and writes on the blackboard the fraction a+cb+d after reducing. Can Kärt always choose the fractions so that after a number of steps she writes on the blackboard a fraction whose denominator is coprime with all the numbers Märt has written on the paper?

Accepted Answer

Answer: Yes.

The first fraction that Kärt adds to the blackboard has to be

\frac{2}{5}

. On every following move, let Kärt pick

\frac{1}{2}

as one fraction and the latest written fraction as the other fraction. Ignoring the reducing step, this means that the denominator of every added fraction is larger than the previous fraction by 2, or that the denominators of the fractions are consecutive odd numbers. This is indeed the case, because all fractions added in this way are irreducible (these fractions have the form

\frac{k}{2 k + 1}

, and

k

is always coprime with

2 k + 1

because any common divisor would also divide

(2 k + 1) - 2 k = 1

).

Therefore the denominators of the fractions that Kärt writes include all prime numbers except 2. Since there are infinitely many prime numbers, Kärt will eventually write a fraction with a prime denominator that is larger than all of the numbers written by Märt, and hence coprime with them.