2008 AIME I Problem 6: Pascal's triangle?

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

Except for writing down some numbers, I wasn't sure how to proceed on this question. Does anyone have any ideas?

Answer 1

Instead of generating each row by taking sums of consecutive elements, take averages. This will divide every element in the whole triangle by some power of $2$, and therefore will not affect which ones are divisible by $67$. Doing it this way the table becomes $$\matrix{ 1&&3&&5&&\cdots&&95&&97&&99\cr &2&&4&&6&&\cdots&&96&&98\cr &&3&&5&&7&&\cdots&&97\cr}$$ with an obvious pattern. At this stage there is one multiple of $67$ in every row that starts with an odd number. This continues until the $33$rd row, which is $$\matrix{33&&35&&37&&\cdots&&65&&67\cr}\ ;$$ after this we have $$\matrix{34&&36&&38&&\cdots&&66\cr&35&&37&&\cdots&&65\cr}$$ and it is clear that there will be no more multiples of $67$. So there is one multiple of $67$ in rows $1,3,5,\ldots,33$, and no more.

Answer. The triangle contains $17$ multiples of $67$.

Answer 2

Claim : every row of the triangular array that you have, is an arithmetic progression. More precisely, the common difference in the $n$th row (difference between consecutive elements of the row) is $2^{n}$.

Proof : Clearly, the first row is an arithmetic progression of common difference two.

Call the elements of the triangular array $a_{n,i}$ where $n$ is the row (from top : the topmost row is $1$, second top most is $2$ etc.) and $i$ is the index within the row (for example, $a_{1,2} = 3$).

Then, $a_{(n+1),i} = a_{n,i+1} + a_{n,i}$ (similar to, but not quite the combinatorial relation), so $a_{(n+1),i+1} - a_{(n+1),i} = (a_{n,i+1} - a_{n,i-1}) = 2 \times 2^{n} = 2^{n+1}$. So our fact follows by induction.

Now, is there a nice formula for the first element of every row? Indeed, $a_{(n+1),1} = a_{n,1} + a_{n,2} = 2a_{n,1} + 2^n$ is a recurrence relation.

Now, we actually have a formula for each element : $a_{n,i} = a_{n,1} + (i-1)2^n$, and the above formula are the key points.

We have yet another claim, however.

Claim : $a_{n,1} = n2^{n-1}$!

Proof : Indeed, it is true for $n = 1$ and $a_{(n+1),1} = (n+1)2^n$ is easy to see, completing the inductive hypothesis.

Finally, we are in a very nice position : $a_{n,i} = a_{n,1} + (i-1)2^n = (n+2i-2)2^{n-1}$.

You can see this : for example, $a_{2,2} = 8 = (2 + (2 \times 2) - 2)2^{2-1}$

Finally, when is $a_{n,i}$ a multiple of $67$? Note that $2^n$ is coprime to $67$.

Therefore, $a_{n,i}$ is a multiple of $67$ precisely when $(n+2i-2)$ is a multiple of $67$.

Knowing that $1 \leq n \leq 99$ and $i \leq 100-n$, can you now do the problem?

EDIT : You should get $17$ multiples.