Difference between revisions of "2008 AIME I Problems/Problem 6"

m (Solution: spacing?)
m
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
Let the <math>k</math>th number in the <math>n</math>th row be <math>a(n,k)</math>. We claim by [[induction]] on <math>n</math> or inspection that <math>a(n,k) = 2^{n-1}(n+2k-2)</math>. Indeed, note that <math>a(1,k) = 2^{1-1}(1+2k-2)=2k-1</math>, which is the correct formula for the first row. By definition of the array, <math>a(n,k) = a(n-1,k)+a(n-1,k+1)</math>, and by our inductive hypothesis,  
+
Let the <math>k</math>th number in the <math>n</math>th row be <math>a(n,k)</math>. We claim by [[induction]] on <math>n</math> or inspection that <math>a(n,k) = 2^{n-1}(n+2k-2)</math>. Indeed, note that <math>a(1,k) = 2^{1-1}(1+2k-2)=2k-1</math>, which is the correct formula for the first row.
<cmath>\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)</cmath>
+
 
 +
By definition of the array, <math>a(n,k) = a(n-1,k)+a(n-1,k+1)</math>, and by our inductive hypothesis,  
 +
<center><math>\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)</math></center>
 
thereby completing our induction.  
 
thereby completing our induction.  
  
Since <math>2^{n-1}</math> and <math>67</math> are [[relatively prime]], we just have to consider the <math>n+2k-2</math> term. Since every row has one less element than the previous row, <math>k \le 51-n</math>. Hence <math>n+2k-2 \le 100-n</math>, and the only multiple of <math>67</math> which fits this range is <math>67</math> itself. For <math>n+2k-2 = 67</math>, note that we need <math>n</math> to be odd, and also that <math>n+2k-2 = 67 \le 100-n \Longrightarrow n \le 33</math>. We can check that all odd <math>n</math> satisfying <math>1 \le n \le 33</math> indeed contains one entry that is a multiple of <math>67</math>, and so the answer is <math>\frac{33+1}{2} = \boxed{017}</math>.
+
Since <math>2^{n-1}</math> and <math>67</math> are [[relatively prime]], we only have to consider the <math>n+2k-2</math> term. Since every row has one less element than the previous row, <math>k \le 51-n</math>. Hence <math>n+2k-2 \le 100-n</math>, and the only multiple of <math>67</math> which fits this range is <math>67</math> itself.
 +
 
 +
For <math>n+2k-2 = 67</math>, note that we need <math>n</math> to be odd, and also that <math>n+2k-2 = 67 \le 100-n \Longrightarrow n \le 33</math>.
 +
 
 +
We can check that all odd <math>n</math> satisfying <math>1 \le n \le 33</math> indeed contains one entry that is a multiple of <math>67</math>, and so the answer is <math>\frac{33+1}{2} = \boxed{017}</math>.
  
 
== See also ==
 
== See also ==

Revision as of 14:27, 19 April 2008

Problem

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

Solution

Let the $k$th number in the $n$th row be $a(n,k)$. We claim by induction on $n$ or inspection that $a(n,k) = 2^{n-1}(n+2k-2)$. Indeed, note that $a(1,k) = 2^{1-1}(1+2k-2)=2k-1$, which is the correct formula for the first row.

By definition of the array, $a(n,k) = a(n-1,k)+a(n-1,k+1)$, 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 $2^{n-1}$ and $67$ are relatively prime, we only have to consider the $n+2k-2$ term. Since every row has one less element than the previous row, $k \le 51-n$. Hence $n+2k-2 \le 100-n$, and the only multiple of $67$ which fits this range is $67$ itself.

For $n+2k-2 = 67$, note that we need $n$ to be odd, and also that $n+2k-2 = 67 \le 100-n \Longrightarrow n \le 33$.

We can check that all odd $n$ satisfying $1 \le n \le 33$ indeed contains one entry that is a multiple of $67$, and so the answer is $\frac{33+1}{2} = \boxed{017}$.

See also

2008 AIME I (ProblemsAnswer KeyResources)
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