2007 AIME II Problem 13

Attempt Problem 13 of the 2007 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 2007 AIME II solutions, or check the answer key.

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

13.

A triangular array of squares has one square in the first row, two in the second, and, in general, kk squares in the kkth row for 1k11.1 \le k \le 11. With the exception of the bottom row, each square rests on two squares in the row immediately below, as illustrated in the figure. In each square of the eleventh row, a 00 or a 11 is placed. Numbers are then placed into the other squares, with the entry for each square being the sum of the entries in the two squares below it. For how many initial distributions of 00’s and 11’s in the bottom row is the number in the top square a multiple of 3?3?

Answer: 640
Concepts:Pascal’s Trianglemodular arithmeticmultiplication principle
Difficulty rating: 2920
Small Hint:

Each entry feeds upward like Pascal’s triangle: for bottom entries x0,x_0, ,\ldots, x10,x_{10}, the top square is i(10i)xi\sum_i \binom{10}{i} x_i

Big Hint:

Modulo 3,3, except for i=0,i = 0, 1,1, 9,9, 10,10, the coefficient (10i)\binom{10}{i} vanishes, so only x0+x1+x9+x10x_0 + x_1 + x_9 + x_{10} matters

Solution:

Label the bottom-row entries x0,x_0, x1,x_1, ,\ldots, x10.x_{10}. Since each square is the sum of the two below it, the contributions accumulate with Pascal’s-triangle weights: the top square equals i=010(10i)xi.\sum_{i=0}^{10} \binom{10}{i} x_i.

Modulo 3,3, direct checking (or Lucas’ theorem with 10=101310 = 101_3) shows that for 2i8,2 \le i \le 8, (10i)0,\binom{10}{i} \equiv 0, while (100)=(1010)=1\binom{10}{0} = \binom{10}{10} = 1 and (101)=(109)=101.\binom{10}{1} = \binom{10}{9} = 10 \equiv 1. So the top square is a multiple of 33 exactly when x0+x1+x9+x10x_0 + x_1 + x_9 + x_{10} 0(mod3).\equiv 0 \pmod 3.

Because the four entries are 00 or 1,1, their sum is divisible by 33 only when it is 00 or 3:3: either all four are 00 (one way) or exactly three are 11 (four ways), for 55 choices. The remaining seven entries x2,x_2, ,\ldots, x8x_8 are free, so the count is 527=640.5 \cdot 2^7 = 640.

Problem 12#12
Full Exam

Problem 13 in Other Years