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 (→‎Solution: spacing?)
 
(14 intermediate revisions by 8 users not shown)
Line 2: Line 2:
 
A [[triangle|triangular]] array of numbers has a first row consisting of the odd integers <math>1,3,5,\ldots,99</math> 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 <math>67</math>?
 
A [[triangle|triangular]] array of numbers has a first row consisting of the odd integers <math>1,3,5,\ldots,99</math> 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 <math>67</math>?
  
−
== Solution ==
+
==Solution 1==
−
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>. Writing out some numbers, we find that <math>a(n,k) = 2^{n-1}(n+2k-2)</math>.{{ref|1}}
−
<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>
 
−
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>.
+
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>. By definition of the array, <math>a(n,k) = a(n-1,k)+a(n-1,k+1)</math>, and by our inductive hypothesis,
 +
<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)\end{align*}</cmath>
 +
thereby completing our induction.
 +
 
 +
==Solution 2==
 +
 
 +
The result above is fairly intuitive if we write out several rows and then divide all numbers in row <math>r</math> by <math>2^{r-1}</math> (we can do this because dividing by a power of 2 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, with each row the row will have one less element, and the <math>99-67+1 = 33</math>rd row is the last time <math>67</math> will appear. Therefore the number of multiples of 67 in the entire array is <math>\frac{33+1}{2} = \boxed{017}</math>.
  
 
== See also ==
 
== See also ==
Line 13: Line 30:
  
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 16:21, 22 March 2018

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 1

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$. 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)\end{align*} thereby completing our induction.

Solution 2

The result above is fairly intuitive if we write out several rows and then divide all numbers in row $r$ by $2^{r-1}$ (we can do this because dividing by a power of 2 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, with each row the row will have one less element, and the $99-67+1 = 33$rd row is the last time $67$ will appear. Therefore the number of multiples of 67 in the entire array is $\frac{33+1}{2} = \boxed{017}$.

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_AIME_I_Problems/Problem_6&oldid=93411"