AlgebraDifficulty 5.4AIME, harderFind the answerItaly
Problem:
We set a1=1 and, for every n≥2, an=n(a1+a2+⋯+an−1). What is the smallest value of n for which an is divisible by 2022?
Pick one
Solution
Solution:
The answer is (C). Let us consider the equations {an=n(a1+a2+⋯+an−1)an+1=(n+1)(a1+a2+⋯+an−1+an) valid for every n≥2. Let us now rewrite the second one in the form an+1=n(a1+a2+⋯+an−1)+(a1+a2+⋯+an−1)+(n+1)an=an+nan+(n+1)an=nn2+2n+1an=n(n+1)2an where - using the first equation - we have replaced a1+a2+⋯+an−1 with nan wherever possible. We then obtain an=n−1n2an−1=n−1n2n−2(n−1)2an−2=⋯=n−1n2n−2(n−1)2⋯232a2. Simplifying the denominator of each fraction with the numerator of the next one, and observing that a2=2, we obtain an=n2⋅(n−1)⋅(n−2)⋅…⋅4⋅23a2=n⋅2n! for every n≥2. At this point, we observe that 2022=2⋅3⋅337 divides n⋅2n! if and only if this number is divisible separately by 2, 3 and 337. On one hand, since n⋅2n! is a product of numbers less than or equal to n and 337 is prime, such a product can be divisible by 337 only if n≥337. On the other hand, if n=337 we have an=337⋅21⋅337!, and 21⋅337!=3⋅4⋅…⋅337 is certainly a multiple of 6, so that 2⋅3⋅337 divides a337, 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.