Maths Olympiad Prep

Library / /510 of 740

, 2024

Number theory Difficulty 5.1 AIME, harder Prove it United States

Problem:
Compute the sum of the three smallest positive integers nn for which
1+2+3++(2024n1)+2024n1+2+3++(4n1)+4n \frac{1+2+3+\cdots+(2024 n-1)+2024 n}{1+2+3+\cdots+(4 n-1)+4 n}
is an integer.

Solution

Solution:
We simplify the expression as follows:
(2024n)(2024n+1)/2(4n)(4n+1)/2=506(2024n+1)4n+1=506(506(4n+1)505)4n+1=50625065054n+1=50622511231014n+1. \begin{aligned} \frac{(2024 n)(2024 n+1) / 2}{(4 n)(4 n+1) / 2} & = \frac{506 \cdot (2024 n+1)}{4 n+1} \\ & = \frac{506 \cdot (506 \cdot (4 n+1) - 505)}{4 n+1} \\ & = 506^{2} - \frac{506 \cdot 505}{4 n+1} \\ & = 506^{2} - \frac{2 \cdot 5 \cdot 11 \cdot 23 \cdot 101}{4 n+1} . \end{aligned}

Thus, the expression is an integer if and only if 4n+14 n+1 divides 511231015 \cdot 11 \cdot 23 \cdot 101. The smallest divisors of 511231015 \cdot 11 \cdot 23 \cdot 101 are
1,5,11,23,55,101,253. 1, 5, 11, 23, 55, 101, 253 .
Since 4n+1>14 n+1 > 1 and is 11 modulo 44, the three smallest values it can take are 55, 101101, and 253253. Hence, the three smallest values of nn are 11, 2525, and 6363, giving the answer of 1+25+63=891+25+63=89.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.