Combinatorics AIME Difficult
2007


Problem - 2708

A triangular array of squares has one square in the first row, two in the second, and in general, $k$ squares in the $k$th row for $1 \leq k \leq 11.$ With the exception of the bottom row, each square rests on two squares in the row immediately below (illustrated in given diagram). In each square of the eleventh row, a $0$ or a $1$ 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 $0$'s and $1$'s in the bottom row is the number in the top square a multiple of $3$?


Let the values in the bottom squares be $x_0$, $x_1$, $\cdots$, $x_{10}$, respectively. Then, it can be determined that the value of the top square equals: $$V=\binom{10}{0}x_0 +\binom{10}{1}x_1 + \binom{10}{2}x_2 + \cdots + \binom{10}{9}x_9 + \binom{10}{10}x_{10}$$

We find coefficients $\binom{10}{2}$, $\binom{10}{3}$, $\cdots$, $\binom{10}{8}$ are all multiples of $3$. Therefore $$V\equiv x_0 + 10x_1+10x_9 + x_{10}\equiv x_0 + x_1+x_9+x_{10}\pmod{3}$$

Therefore, in order for $V\equiv 0\pmod{3}$ to hold, either all of them are $0$ or exactly three of them are $1$s. Hence, the totally possibilities are $$1+\binom{4}{3}=5$$

The remaining $7$ elements, $x_2$, $x_3$, $\cdots$, $x_8$, can take either $0$ or $1$ which gives $2^7=128$ choices.

The answer is therefore $5 \times 128 = \boxed{640}$.

report an error