Esmeralda chooses two distinct positive integers \(a\) and \(b\), with \(b > a\), and writes the equation \[ x^2 - ax + b = 0 \] on the board. If the equation has distinct positive integer roots \(c\) and \(d\), with \(d > c\), she writes the equation \[ x^2 - cx + d = 0 \] on the board. She repeats the procedure as long as she obtains distinct positive integer roots. If she writes an equation for which this does not occur, she stops. a) Show that Esmeralda can choose \(a\) and \(b\) such that she will write exactly 2024 equations on the board. b) What is the maximum number of equations she can write knowing that one of the initially chosen numbers is 2024?
Problem
Source: Brazilian Mathematical Olympiad 2024, Level 2, Problem 5
Tags: algebra, quadratics, board, Sequence
13.10.2024 04:25
For the item a) we can prove, by a really simple induction that, for all $n$, Esmeralda can choose $a$ and $b$ such that she´ll write exacly $n$ equations on the board. b) Let $x^2-a_ix+b_i=$ be the $i$-th equation that Esmeralda writes on the board and let $k$ also be the sought value. Note that the pair $(a_k,b_k)$ that can eventually be written and has the lowest value for $a_k+b_k$ is the pair $(2,3)$ because the pair $(1,2)$ clearly cannot be written, since the equation that precedes it should be $x^2-3x+2=0$ which cannot be written because $3>2$ as well as the pair $(1,3)$ and $(1,4)$, since the equation that precedes them should be, respectively $x^2-4x+3=0$ and $x^2-5x+4=0$, which also does not occur because $5>4>3$. Thus, we have that: $a_{k-1}=a_k+b_k\geq5, b_{k-1}=a_kb_k\geq6 \Rightarrow a_{k-2}=a_{k-1}+b_{k-1}\geq11, b_{k-2}=a_{k-1}b_{k-1}\geq30 \Rightarrow a_{k-3}=a_{k-2} +b_{k-2}\geq41, b_{k-3}=a_{k-2}b_{k-2}\geq330 \Rightarrow a_{k-4}=a_{k-3}+b_{k-3}\geq371, b_{k-4}=a_{k-3}b_{k-3}\geq13530 \Rightarrow a_{k-5}=a_{k-4}+b_{k-4}\geq13901, b_{k-5}=a_{k-4}b_{k-4}\geq519630$, therefore, $k\leq5$ Note also that $k$ cannot be $5$, since we would have to have $b_{k-3}=b_2\geq13530$, which does not occur since $b_2$ is a root of $x^2-2024x+b_1$ or $x^2-a_1x+2024$. Now, for $k=4$, we want to find integers \(a_2\) and \(b_2\) such that: \[ a_2+b_2 = 2024 \] But, notice that we can rewrite this equation as: \[ (a_3 + 1)(b_3 + 1) = 2025 \] Now, we need to factor \(2025\) and find all pairs \((a_3 + 1, b_3 + 1)\). Factoring \(2025\), we have: \[ 2025 = 45^2 = 5^2 \times 3^4 \] The divisors of \(2025\) are: \[ 1, 3, 5, 9, 15, 25, 27, 45, 75, 81, 135, 225, 405, 675, 2025 \] Now, for each divisor \(a_3 + 1\) and \(b_3 + 1\), with \(b_3 > a_3\), we calculate \(a_3\) and \(b_3\): 1. \(a_3 + 1 = 1\) and \(b_3 + 1 = 2025 \Rightarrow a_3 = 0, b_3 = 2024\) $\rightarrow$ Not valid, since \(a_3 > 0\) is required. 2. \(a_3 + 1 = 3\) and \(b_3 + 1 = 675 \Rightarrow a_3 = 2, b_3 = 674\) 3. \(a_3 + 1 = 5\) and $b_3 + 1 = 405$ $\Rightarrow$ $a_3=4, b_3=404$ 4. \(a_3 + 1 = 9\) and \(b_ 3 + 1 = 225 \Rightarrow a_3 = 8, b_3 = 224\) 5. \(a_3 + 1 = 15\) and \(b_3 + 1 = 135 \Rightarrow a_3 = 14, b_3 = 134\) 6. \(a_3 + 1 = 25\) and \(b_3 + 1 = 81 \Rightarrow a_3 = 24, b_3 = 80\) 7. \(a_3 + 1 = 27\) and \(b_3 + 1 = 75 \Rightarrow a_3 = 26, b_3 = 74\) 8. \(a_3 + 1 = 45\) and \(b_3 + 1 = 45 \Rightarrow a_3 = 44, b_3 = 44\) $\rightarrow$ Not valid, since \(a_3 \neq b_3\) is required. However, we know that in order for $x^2-a_3x+b_3=0$ to have distinct solutions, we must have $\triangle=a_3^2-4b_3>0\Rightarrow a_3>4b_3$. So the only solutions $(a_3,b_3)$ that can give us $k=4$ are $(24,80)$ and $(26, 74)$, from which we can have $x^2-24x+80$ since this has roots $4$ and $20$, from which we get $b_1=199680$. Therefore, writing the equation $x^2-2024x+199680=0$, Esmeralda will reach the maximum $k$, $k=4$, writing the following equations: \[ x^2-2024x+199680=0 \]\[ x^2-104x+1920=0 \]\[ x^2-24x+80=0 \]\[ x^2-4x+20=0 \]