2001 AIME II Problem 3

Attempt Problem 3 of the 2001 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2001 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

3.

The first four terms are x1=211,x_1 = 211, x2=375,x_2 = 375, x3=420,x_3 = 420, and x4=523.x_4 = 523. For n5,n \ge 5, xn=xn1xn2+xn3xn4. \begin{aligned} x_n &= x_{n-1} - x_{n-2} \\ &\quad {}+ x_{n-3} - x_{n-4}. \end{aligned} Find the value of x531+x753+x975.x_{531} + x_{753} + x_{975}.

Answer: 898
Concepts:recursionpattern recognition
Difficulty rating: 2070
Small Hint:

Substitute the recurrence for xn1x_{n-1} into the formula for xnx_n to get xn=xn5x_n = -x_{n-5}

Big Hint:

The sequence repeats with period 10,10, so reduce each subscript mod 1010 and compute x5x_5 from the given values

Solution:

For n6,n \ge 6, substitute the recurrence for xn1:x_{n-1}: xn=(xn2xn3+xn4xn5)xn2+xn3xn4=xn5. \begin{aligned} x_n &= \\ &(x_{n-2} - x_{n-3} + x_{n-4} - x_{n-5}) \\ &\quad {}- x_{n-2} \\ &\quad {}+ x_{n-3} - x_{n-4} \\ &= -x_{n-5}. \end{aligned} Hence xn+10=xn+5=xn,x_{n+10} = -x_{n+5} = x_n, so the sequence has period 10.10.

Since 531,531, 753,753, and 975975 leave remainders 1,1, 3,3, and 55 upon division by 10,10, we get x531=x1=211,x_{531} = x_1 = 211, x753=x3=420,x_{753} = x_3 = 420, and x975=x5x_{975} = x_5 =x4x3+x2x1= x_4 - x_3 + x_2 - x_1 =523420+375211= 523 - 420 + 375 - 211 =267.= 267.

The sum is 211+420+267=898.211 + 420 + 267 = 898.

Problem 2#2
Full Exam

Problem 3 in Other Years