1999 AIME Problem 7

Below is the professionally curated solution for Problem 7 of the 1999 AIME, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 1999 AIME 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:prime factorizationmodular arithmeticcomplementary counting

Difficulty rating: 2650

7.

There is a set of 10001000 switches, each of which has four positions, called A,A, B,B, C,C, and D.D. When the position of any switch changes, it is only from AA to B,B, from BB to C,C, from CC to D,D, or from DD to A.A. Initially each switch is in position A.A. The switches are labeled with the 10001000 different integers 2x3y5z,2^x 3^y 5^z, where x,x, y,y, and zz take on the values 0,1,,9.0, 1, \ldots, 9. At step ii of a 10001000-step process, the iith switch is advanced one step, and so are all the other switches whose labels divide the label on the iith switch. After step 10001000 has been completed, how many switches will be in position A?A?

Solution:

The switch labeled dd is advanced exactly once for each step ii whose label is a multiple of d.d. The multiples of 2x3y5z2^x 3^y 5^z among the labels are the 2x3y5z2^{x'} 3^{y'} 5^{z'} with xx9,x \le x' \le 9, etc., so that switch advances (10x)(10y)(10z)(10 - x)(10 - y)(10 - z) times. It returns to position AA exactly when this count is a multiple of 4.4.

Write a=10x,a = 10 - x, b=10y,b = 10 - y, c=10z,c = 10 - z, each ranging over 11 through 10.10. We count the triples where abcabc is not divisible by 4:4: either all three are odd, or exactly one is even but not divisible by 4.4. Among 1,,101, \ldots, 10 there are 55 odd values and 33 values (2,6,102, 6, 10) that are twice an odd number. That gives 53=1255^3 = 125 triples of the first kind and 3352=2253 \cdot 3 \cdot 5^2 = 225 of the second, or 350350 in all.

Therefore 1000350=6501000 - 350 = 650 switches end in position A.A.

← Problem 6Full ExamProblem 8

Problem 7 in Other Years