Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m
(clarify)
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.
+
Let the <math>k</math>th number in the <math>n</math>th row be <math>a(n,k)</math>. Writing out some numbers, we find that <math>a(n,k) = 2^{n-1}(n+2k-2)</math>.{{ref|1}}
  
−
By definition of the array, <math>a(n,k) = a(n-1,k)+a(n-1,k+1)</math>, and by our inductive hypothesis,  
+
We wish to find all <math>(n,k)</math> such that <math>67| a(n,k) = 2^{n-1} (n+2k-2)</math>. Since <math>2^{n-1}</math> and <math>67</math> are [[relatively prime]], it follows that <math>67|n+2k-2</math>. Since every row has one less element than the previous row, <math>1 \le k \le 51-n</math> (the first row has <math>50</math> elements, the second <math>49</math>, and so forth; so <math>k</math> can range from <math>1</math> to <math>50</math> in the first row, and so forth). Hence
 +
 
 +
<center><math>n+2k-2 \le n + 2(51-n) - 2 = 100 - n \le 100,</math></center>
 +
 
 +
it follows that <math>67| n - 2k + 2</math> implies that <math>n-2k+2 = 67</math> itself.
 +
 
 +
Now, 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 rows with 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>.
 +
 
 +
 
 +
<br />
 +
 
 +
{{note|1}} Proof: 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. We claim the result by [[induction]] on <math>n</math> that. 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>
 
<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 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>.
+
The result above is fairly intuitive if we write out several rows, each time dividing the result through by <math>2</math> (as this doesn't affect divisibility by <math>67</math>). The second row will be <math>2, 4, 6, \cdots , 98</math>, the third row will be <math>3, 5, \cdots, 97</math>, and so forth. Clearly, only the odd-numbered rows can have a term divisible by <math>67</math>. However, each with each row the row will "shrink", and the <math>33</math>rd row is the last time <math>67</math> will appear.  
  
 
== See also ==
 
== See also ==

Revision as of 17:24, 5 September 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)$. Writing out some numbers, we find that $a(n,k) = 2^{n-1}(n+2k-2)$.[1]

We wish to find all $(n,k)$ such that $67| a(n,k) = 2^{n-1} (n+2k-2)$. Since $2^{n-1}$ and $67$ are relatively prime, it follows that $67|n+2k-2$. Since every row has one less element than the previous row, $1 \le k \le 51-n$ (the first row has $50$ elements, the second $49$, and so forth; so $k$ can range from $1$ to $50$ in the first row, and so forth). Hence

$n+2k-2 \le n + 2(51-n) - 2 = 100 - n \le 100,$

it follows that $67| n - 2k + 2$ implies that $n-2k+2 = 67$ itself.

Now, 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 rows with 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}$.



^ Proof: Indeed, note that $a(1,k) = 2^{1-1}(1+2k-2)=2k-1$, which is the correct formula for the first row. We claim the result by induction on $n$ that. 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.

The result above is fairly intuitive if we write out several rows, each time dividing the result through by $2$ (as this doesn't affect divisibility by $67$). The second row will be $2, 4, 6, \cdots , 98$, the third row will be $3, 5, \cdots, 97$, and so forth. Clearly, only the odd-numbered rows can have a term divisible by $67$. However, each with each row the row will "shrink", and the $33$rd row is the last time $67$ will appear.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_AIME_I_Problems/Problem_6&oldid=27806"