Given a positive integer $c$, we construct a sequence of fractions $a_1, a_2, a_3,...$ as follows: $\bullet$ $a_1 =\frac{c}{c+1} $ $\bullet$ to get $a_n$, we take $a_{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 = 20$, then $a_1 =\frac{20}{21}$ and $a_2 =\frac{22}{24} = \frac{11}{12}$ . Then we find that $a_3 =\frac{13}{15}$ (which is already simplified) and $a_4 =\frac{15}{18} =\frac{5}{6}$. (a) Let $c = 10$, hence $a_1 =\frac{10}{11}$ . Determine the largest $n$ for which a simplification is needed in the construction of $a_n$. (b) Let $c = 99$, hence $a_1 =\frac{99}{100}$ . Determine whether a simplification is needed somewhere in the sequence. (c) Find two values of $c$ for which in the first step of the construction of $a_5$ (before simplification) the numerator and denominator are divisible by $5$.
Problem
Source: Dutch NMO 2022 p3
Tags: algebra, simplify, simplification, number theory
18.11.2022 01:37
a): $n=7$. We get $\frac{10}{11} \rightarrow \frac{12}{14} = \frac{6}{7} \rightarrow \frac{8}{10} = \frac{4}{5} \rightarrow \frac{6}{8} = \frac{3}{4} \rightarrow \frac{5}{7} \rightarrow \frac{7}{10} \rightarrow \frac{9}{13}$ is the maximum, because from now on $gcd(9+2k,13+3k) = gcd(9+2k,4+k) = gcd(9+2k,8+2k) = 1$. b): $\frac{99 + 96\cdot 2}{100 + 96\cdot 3} = \frac{3}{4}$ (Found by $gcd(100+3k,99+2k) = gcd(99+2k, 1+k) = gcd(1+k,97k) = 97$ if $k=96$ c):$c=7$: $\frac{7}{8} \rightarrow \frac{9}{11} \rightarrow \frac{11}{14} \rightarrow \frac{13}{17} \rightarrow \frac{15}{20}$ and $c = 27$ work: $\frac{27}{28} \rightarrow \frac{29}{31} \rightarrow \frac{31}{34} \rightarrow \frac{33}{37} \rightarrow \frac{35}{40}$ Method: find $\frac{x}{x+1}$ such that $\frac{x+2}{x+4}, \frac{x+4}{x+7}, \frac{x+6}{x+10}, \frac{x+8}{x+12}$ aren't simplifiable, with $x \equiv 7 \pmod{10}$.
20.09.2023 01:52
a): $n=4$. We get $\frac{10}{11} \rightarrow \frac{12}{14} = \frac{6}{7} \rightarrow \frac{8}{10} = \frac{4}{5} \rightarrow \frac{6}{8} = \frac{3}{4}$ from here on we don't need a simplification of the construction of $a_n$ because the next fraction ($\frac{5}{7}$) we have that 1 + 2k is a coprime sequence of 1 + 3k b): assuming that both are 0 mod x we have that later it will be congruent to 2 and the other congruent to 3 that with $\frac{99}{100}$ that 0 would be 97 and since 97 is prime we have it as the only answer and also that the modular sequence will have 97 numbers, the answer n=97k c):$c=7$ $\frac{7}{8} \rightarrow \frac{9}{11} \rightarrow \frac{11}{14} \rightarrow \frac{13}{17} \rightarrow \frac{15}{20}$ and $c = 27$ function: $\frac{27}{28} \rightarrow \frac{29}{31} \rightarrow \frac{31}{34} \rightarrow \frac{33}{37} \rightarrow \frac{35}{40}$ Doing the operation in reverse with the odd numerator and denominator not divisible by 3 works