2008 AIME I Problems/Problem 6
Problem
A triangular array of numbers has a first row consisting of the odd integers 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
?
Solution
Let the th number in the
th row be
. We claim by induction on
or inspection that
. Indeed, note that
, which is the correct formula for the first row. By definition of the array,
, and by our inductive hypothesis,
\begin{align*}a(n,k) &= a(n-1,k)+a(n-1,k+1)\\ &= 2^{n-2}(n-1+2k-2)+2^{n-2}(n-1+2(k+1)-2)\\&=2^{n-2}(2n+4k-4)\\&=2^{n-1}(n+2k-2) (Error compiling LaTeX. Unknown error_msg)
thereby completing our induction.
Since and
are relatively prime, we just have to consider the
term. Since every row has one less element than the previous row,
. Hence
, and the only multiple of
which fits this range is
itself. For
, note that we need
to be odd, and also that
. We can check that all odd
satisfying
indeed contains one entry that is a multiple of
, and so the answer is
.
See also
2008 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 5 |
Followed by Problem 7 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |