Question

A triangular array of numbers has a first row consisting of the odd integers $1, 3, 5, \ldots, 99$ in increasing order. Each row below the first has one fewer entry than the row above it, and the bottom row has a single entry. Each entry in any row after the top row equals the sum of the two entries diagonally above it in the row immediately above it. How many entries in the array are multiples of $67?$ $\scriptsize\begin{array}{ccccccccccc} 1 & & 3 & & 5 & & \cdots & & 97 & & 99 \\ & 4 & & 8 & & 12 & & \cdots & & 196 & \\ & & & & & \vdots & & & & & \end{array}$

Answer

Answer: 17

Concepts:divisibility induction parity

Difficulty rating: 2600

Solution:

By induction, the $n$ th entry of row $r$ is $2^{r-1}(r + 2n - 2):$ row $1$ gives $2^0(2n - 1),$ and summing two adjacent entries of row $r$ gives $2^{r-1}(r + 2n - 2)$ $+ 2^{r-1}(r + 2n)$ $= 2^r\bigl((r + 1) + 2n - 2\bigr),$ the formula for row $r + 1.$ Row $r$ has $51 - r$ entries, so $1 \le n \le 51 - r.$

Since $67$ is odd, an entry is a multiple of $67$ exactly when $67 \mid r + 2n - 2.$ As $n$ runs through row $r,$ the quantity $r + 2n - 2$ takes the values $r, r + 2, \ldots, 100 - r,$ all with the same parity as $r$ and all less than $134.$ So the only possible multiple of $67$ is $67$ itself, which requires $r$ odd and $r \le 67 \le 100 - r,$ that is, $r \le 33.$

Each odd row $r = 1, 3, \ldots, 33$ contains exactly one such entry, for a total of $17.$

2008 AIME I Problem 6

Answer: 17

Difficulty rating: 2600

Solution:

Problem 6 in Other Years