Maths Olympiad Prep

Library / /14 of 24

Algebra Difficulty 6.5 National olympiad Prove it Netherlands

Given a positive integer cc, we construct a sequence of fractions a1,a2,a3,a_1, a_2, a_3, \dots as follows:
* a1=cc+1a_1 = \frac{c}{c+1};
* to get ana_n, we take an1a_{n-1} (in its most simplified form, with both the numerator and denominator chosen to be positive) and we add 2 to the numerator and 3 to the denominator. Then we simplify the result again as much as possible, with positive numerator and denominator.
For example, if we take c=20c = 20, then a1=2021a_1 = \frac{20}{21} and a2=2224=1112a_2 = \frac{22}{24} = \frac{11}{12}. Then we find that a3=1315a_3 = \frac{13}{15} (which is already simplified) and a4=1518=56a_4 = \frac{15}{18} = \frac{5}{6}.

a. Let c=10c = 10, hence a1=1011a_1 = \frac{10}{11}. Determine the largest nn for which a simplification is needed in the construction of ana_n.

b. Let c=99c = 99, hence a1=99100a_1 = \frac{99}{100}. Determine whether a simplification is needed somewhere in the sequence.

c. Find two values of cc for which in the first step of the construction of a5a_5 (before simplification) the numerator and denominator are divisible by 5.

Solution

a.
The sequence starts as follows.
a1=1011,a2=1214=67,a3=810=45,a4=68=34,a5=57,a6=710,a7=913 \begin{aligned} a_1 &= \frac{10}{11}, & a_2 &= \frac{12}{14} = \frac{6}{7}, & a_3 &= \frac{8}{10} = \frac{4}{5}, & a_4 &= \frac{6}{8} = \frac{3}{4}, \\ a_5 &= \frac{5}{7}, & a_6 &= \frac{7}{10}, & a_7 &= \frac{9}{13} \end{aligned}
It seems that the last simplification occurred at a4a_4. With induction to nn, we will prove that there is no simplification for all n5n \ge 5. At the same time, we will prove that an=1+2(n3)1+3(n3)a_n = \frac{1+2(n-3)}{1+3(n-3)} for all n5n \ge 5.
For n=5n = 5, the statement is true, because a5=57=1+2(53)1+3(53)a_5 = \frac{5}{7} = \frac{1+2(5-3)}{1+3(5-3)} and this fraction 57\frac{5}{7} cannot be simplified further. Now suppose the statement is true for n=k1n = k - 1. Consider n=kn = k. Because there has been no simplification for ak1a_{k-1}, the numerator of ak1a_{k-1} equals 1+2(k4)1 + 2(k - 4) and the denominator equals 1+3(k4)1 + 3(k - 4). Then the number aka_k is defined as 1+2(k4)+21+3(k4)+3=1+2(k3)1+3(k3)\frac{1+2(k-4)+2}{1+3(k-4)+3} = \frac{1+2(k-3)}{1+3(k-3)}.
We will argue by contradiction that there is no simplification here. Namely, suppose there is an integer d>1d > 1 such that both 1+2(k3)1 + 2(k - 3) and 1+3(k3)1 + 3(k - 3) are divisible by dd. In particular, 3(1+2(k3))2(1+3(k3))=13 \cdot (1 + 2(k - 3)) - 2 \cdot (1 + 3(k - 3)) = 1 will also be divisible by dd. This gives a contradiction, and the proof by induction is finished. \square

b.
We will show that there must be a simplification at some point. Indeed, suppose there is no simplification. Just like in part (a), we can show by induction that an=97+2n97+3na_n = \frac{97+2n}{97+3n}. In particular, we see that a97a_{97} is not a simplified fraction, because both the numerator and denominator are divisible by 97, and that is a contradiction. \square

c.
You can use c=7c = 7 or c=27c = 27, for example. Then we get the sequences
78,911,1114,1317,1520=34 \frac{7}{8}, \frac{9}{11}, \frac{11}{14}, \frac{13}{17}, \frac{15}{20} = \frac{3}{4}
and
2728,2931,3134,3337,3540=78. \frac{27}{28}, \frac{29}{31}, \frac{31}{34}, \frac{33}{37}, \frac{35}{40} = \frac{7}{8}.
\square

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.