Maths Olympiad Prep

Library / /7 of 18

Algebra Difficulty 5.4 AIME, harder Find the answer Italy

Problem:

We set a1=1a_{1}=1 and, for every n2n \geq 2,
an=n(a1+a2++an1). a_{n}=n\left(a_{1}+a_{2}+\cdots+a_{n-1}\right) .
What is the smallest value of nn for which ana_{n} is divisible by 2022?

Pick one

Solution

Solution:

The answer is (C)(\mathbf{C}). Let us consider the equations
{an=n(a1+a2++an1)an+1=(n+1)(a1+a2++an1+an) \left\{ \begin{array}{l} a_{n}=n\left(a_{1}+a_{2}+\cdots+a_{n-1}\right) \\ a_{n+1}=(n+1)\left(a_{1}+a_{2}+\cdots+a_{n-1}+a_{n}\right) \end{array} \right.
valid for every n2n \geq 2. Let us now rewrite the second one in the form
an+1=n(a1+a2++an1)+(a1+a2++an1)+(n+1)an=an+ann+(n+1)an=n2+2n+1nan=(n+1)2nan \begin{aligned} a_{n+1} & =n\left(a_{1}+a_{2}+\cdots+a_{n-1}\right)+\left(a_{1}+a_{2}+\cdots+a_{n-1}\right)+(n+1) a_{n} \\ & =a_{n}+\frac{a_{n}}{n}+(n+1) a_{n} \\ & =\frac{n^{2}+2 n+1}{n} a_{n} \\ & =\frac{(n+1)^{2}}{n} a_{n} \end{aligned}
where - using the first equation - we have replaced a1+a2++an1a_{1}+a_{2}+\cdots+a_{n-1} with ann\frac{a_{n}}{n} wherever possible. We then obtain
an=n2n1an1=n2n1(n1)2n2an2==n2n1(n1)2n2322a2. a_{n}=\frac{n^{2}}{n-1} a_{n-1}=\frac{n^{2}}{n-1} \frac{(n-1)^{2}}{n-2} a_{n-2}=\cdots=\frac{n^{2}}{n-1} \frac{(n-1)^{2}}{n-2} \cdots \frac{3^{2}}{2} a_{2} .
Simplifying the denominator of each fraction with the numerator of the next one, and observing that a2=2a_{2}=2, we obtain
an=n2(n1)(n2)432a2=nn!2 a_{n}=n^{2} \cdot(n-1) \cdot(n-2) \cdot \ldots \cdot 4 \cdot \frac{3}{2} a_{2}=n \cdot \frac{n !}{2}
for every n2n \geq 2. At this point, we observe that 2022=233372022=2 \cdot 3 \cdot 337 divides nn!2n \cdot \frac{n !}{2} if and only if this number is divisible separately by 2, 3 and 337. On one hand, since nn!2n \cdot \frac{n !}{2} is a product of numbers less than or equal to nn and 337 is prime, such a product can be divisible by 337 only if n337n \geq 337. On the other hand, if n=337n=337 we have an=33712337!a_{n}=337 \cdot \frac{1}{2} \cdot 337!, and 12337!=34337\frac{1}{2} \cdot 337! = 3 \cdot 4 \cdot \ldots \cdot 337 is certainly a multiple of 6, so that 233372 \cdot 3 \cdot 337 divides a337a_{337}, and therefore 337 is the minimum sought.

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 translated into English from it; metadata (topic, difficulty) added by this project.