Question

一个由正方形组成的三角形阵列，第一行有一个正方形，第二行有两个，依此类推，第 $k$ 行有 $k$ 个正方形，其中 $1 \le k \le 11$ 。除底行外，每个正方形都放在它正下方一行的两个正方形上，如图所示。在第十一行的每个正方形中填入一个 $0$ 或 $1$ 。然后在其他正方形中填数，每个正方形中的数等于它下面两个正方形中的数之和。底行中 $0$ 和 $1$ 的初始分布有多少种，使得顶端正方形中的数是 $3$ 的倍数？

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 \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 $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?$

答案

答案：640

知识点：杨辉三角模运算乘法原理

难度评级：2920

解答：

将底行条目标为 $x_0, x_1, \ldots, x_{10}$ 。由于每个正方形都是下方两个正方形之和，贡献按帕斯卡三角形的权重累积：顶端正方形等于 $\sum_{i=0}^{10} \binom{10}{i} x_i$ 。

模 $3$ 时，直接检查（或用 $10 = 101_3$ 的 Lucas 定理）可知，当 $2 \le i \le 8$ 时 $\binom{10}{i} \equiv 0$ ，而 $\binom{10}{0} = \binom{10}{10} = 1$ ，且 $\binom{10}{1} = \binom{10}{9} = 10 \equiv 1$ 。所以顶端正方形是 $3$ 的倍数，当且仅当 $x_0 + x_1 + x_9 + x_{10}$ $\equiv 0 \pmod 3$ 。

对 $0$ / $1$ 条目，这个和只能是 $0$ 或 $3$ ：要么四个全为 $0$ （一种），要么恰好三个为 $1$ （四种），共 $5$ 种选择。其余七个条目 $x_2, \ldots, x_8$ 可自由选择，所以总数为 $5 \cdot 2^7 = 640$ 。

Label the bottom-row entries $x_0, x_1, \ldots, 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 $\sum_{i=0}^{10} \binom{10}{i} x_i.$

Modulo $3,$ direct checking (or Lucas' theorem with $10 = 101_3$ ) shows $\binom{10}{i} \equiv 0$ for $2 \le i \le 8,$ while $\binom{10}{0} = \binom{10}{10} = 1$ and $\binom{10}{1} = \binom{10}{9} = 10 \equiv 1.$ So the top square is a multiple of $3$ exactly when $x_0 + x_1 + x_9 + x_{10}$ $\equiv 0 \pmod 3.$

For $0$ / $1$ entries this sum is $0$ or $3:$ either all four are $0$ (one way) or exactly three are $1$ (four ways), for $5$ choices. The remaining seven entries $x_2, \ldots, x_8$ are free, so the count is $5 \cdot 2^7 = 640.$

2007 AIME II 第 13 题

答案：640

难度评级：2920

解答：

其他年份的第 13 题