Competition problem — Algebra — Maths Olympiad Prep

Library / /30 of 31

Algebra Difficulty 7.0 National olympiad, round 2 Prove it Estonia

Kärt writes the fractions $\frac{1}{2}$ and $\frac{1}{3}$ 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 $\frac{a}{b}$ and $\frac{c}{d}$ which are already on the blackboard and writes on the blackboard the fraction $\frac{a+c}{b+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?

Solution

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}{2k+1}$ , and $k$ is always coprime with $2k+1$ because any common divisor would also divide $(2k+1) - 2k = 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.

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 and solution reproduced as published; topic and difficulty added by this site.