2001 AIME II Problem 3

Below is the professionally curated solution for Problem 3 of the 2001 AIME II, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:recursionpattern recognition

Difficulty rating: 2070

3.

Given that x1=211,x_1 = 211, x2=375,x_2 = 375, x3=420,x_3 = 420, x4=523,x_4 = 523, and xn=xn1xn2+xn3xn4when n5,x_n = x_{n-1} - x_{n-2} + x_{n-3} - x_{n-4} \quad \text{when } n \ge 5, find the value of x531+x753+x975.x_{531} + x_{753} + x_{975}.

Solution:

For n6,n \ge 6, substitute the recurrence for xn1:x_{n-1}: xn=(xn2xn3+xn4xn5)xn2+xn3xn4=xn5.x_n = (x_{n-2} - x_{n-3} + x_{n-4} - x_{n-5}) - x_{n-2} + x_{n-3} - x_{n-4} = -x_{n-5}. 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=x5=x4x3+x2x1=523420+375211=267.x_{975} = x_5 = x_4 - x_3 + x_2 - x_1 = 523 - 420 + 375 - 211 = 267.

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

← Problem 2Full ExamProblem 4

Problem 3 in Other Years