Difference between revisions of "1995 AHSME Problems/Problem 27"
(New page: ==Problem== Consider the triangular array of numbers with 0,1,2,3,... along the sides and interior numbers obtained by adding the two adjacent numbers in the previous row. Rows 1 through 6...) |
|||
| Line 16: | Line 16: | ||
We sum the first few rows: 0, 2, 6, 14, 30, 62. They are each two less than a power of 2, so we try to prove it: | We sum the first few rows: 0, 2, 6, 14, 30, 62. They are each two less than a power of 2, so we try to prove it: | ||
| − | Let the sum of row <math>n</math> be <math>S_n</math>. To generate the next row, we add consecutive numbers. So we double the row, subtract twice the end numbers, then add twice the end numbers and add two. That makes <math>S_{n+1}=2S_n-2(n-1)+2(n-1)+2=2S_n+2</math>. If <math>S_n</math> is two less than a power of 2, then it is in the form <math>2^x-2</math>. <math>S_{n+1}=2^{x+1}-4+2=2^{x+1}-2</math>. Since the first row is two less than a power of 2, all the rest are. Since the sum of the elements of row 1 is <math>2^1-2</math>, the sum of the numbers in row <math>n</math> is <math>2^n-2</math>. Thus, using [[Modular | + | Let the sum of row <math>n</math> be <math>S_n</math>. To generate the next row, we add consecutive numbers. So we double the row, subtract twice the end numbers, then add twice the end numbers and add two. That makes <math>S_{n+1}=2S_n-2(n-1)+2(n-1)+2=2S_n+2</math>. If <math>S_n</math> is two less than a power of 2, then it is in the form <math>2^x-2</math>. <math>S_{n+1}=2^{x+1}-4+2=2^{x+1}-2</math>. Since the first row is two less than a power of 2, all the rest are. Since the sum of the elements of row 1 is <math>2^1-2</math>, the sum of the numbers in row <math>n</math> is <math>2^n-2</math>. Thus, using [[Modular arithmetic]], <math>f(100)=2^{100}-2\equiv 2^{20}-2\bmod{100}</math>. <math>2^{10}=1024</math>, so <math>2^{20}-2\equiv 24^2-2\equiv 74\bmod{100} \Rightarrow \mathrm{(E)}</math>. |
==See also== | ==See also== | ||
Revision as of 13:11, 17 June 2008
Problem
Consider the triangular array of numbers with 0,1,2,3,... along the sides and interior numbers obtained by adding the two adjacent numbers in the previous row. Rows 1 through 6 are shown.
\[\begin{tabular}{ccccccccccc} & & & & & 0 & & & & & \\
& & & & 1 & & 1 & & & & \\
& & & 2 & & 2 & & 2 & & & \\
& & 3 & & 4 & & 4 & & 3 & & \\
& 4 & & 7 & & 8 & & 7 & & 4 & \\
5 & & 11 & & 15 & & 15 & & 11 & & 5 & \end{tabular}\] (Error compiling LaTeX. Unknown error_msg)
Let 
denote the sum of the numbers in row 
. What is the remainder when 
is divided by 100?
Solution
We sum the first few rows: 0, 2, 6, 14, 30, 62. They are each two less than a power of 2, so we try to prove it:
Let the sum of row be 
. To generate the next row, we add consecutive numbers. So we double the row, subtract twice the end numbers, then add twice the end numbers and add two. That makes 
. If is two less than a power of 2, then it is in the form 
. 
. Since the first row is two less than a power of 2, all the rest are. Since the sum of the elements of row 1 is 
, the sum of the numbers in row is 
. Thus, using Modular arithmetic, 
. 
, so 
.
