Difference between revisions of "1995 AHSME Problems/Problem 27"
m (→Solution) |
(→Solutions) |
||
Line 13: | Line 13: | ||
<math> \mathrm{(A) \ 12 } \qquad \mathrm{(B) \ 30 } \qquad \mathrm{(C) \ 50 } \qquad \mathrm{(D) \ 62 } \qquad \mathrm{(E) \ 74 } </math> | <math> \mathrm{(A) \ 12 } \qquad \mathrm{(B) \ 30 } \qquad \mathrm{(C) \ 50 } \qquad \mathrm{(D) \ 62 } \qquad \mathrm{(E) \ 74 } </math> | ||
− | + | ==Solution 1 == | |
− | |||
Note that if we re-draw the table with an additional diagonal row on each side, the table is actually just two of [[Pascal's Triangle]]s, except translated and summed. | Note that if we re-draw the table with an additional diagonal row on each side, the table is actually just two of [[Pascal's Triangle]]s, except translated and summed. | ||
<cmath>\begin{tabular}{ccccccccccccccc} & & & & & 1 & & 0 & & 1 & & & & \\ | <cmath>\begin{tabular}{ccccccccccccccc} & & & & & 1 & & 0 & & 1 & & & & \\ | ||
Line 25: | Line 24: | ||
The sum of a row of Pascal's triangle is <math>2^{n-1}</math>; the sum of two of each of these rows, subtracting away the <math>2</math> ones we included, yields <math>f(n) = 2^n - 2</math>. Now, <math>f(100) = 2^{100} - 2 \equiv 2 \pmod{4}</math> and <math>f(100) = 2^{100} - 2 \equiv 2^{20 \cdot 5} - 2 \equiv -1 \pmod{25}</math>, and by the [[Chinese Remainder Theorem]], we have <math>f(100) \equiv 74 \pmod{100} \Longrightarrow \mathrm{(E)}</math>. | The sum of a row of Pascal's triangle is <math>2^{n-1}</math>; the sum of two of each of these rows, subtracting away the <math>2</math> ones we included, yields <math>f(n) = 2^n - 2</math>. Now, <math>f(100) = 2^{100} - 2 \equiv 2 \pmod{4}</math> and <math>f(100) = 2^{100} - 2 \equiv 2^{20 \cdot 5} - 2 \equiv -1 \pmod{25}</math>, and by the [[Chinese Remainder Theorem]], we have <math>f(100) \equiv 74 \pmod{100} \Longrightarrow \mathrm{(E)}</math>. | ||
− | + | ==Solution 2 (induction) == | |
We sum the first few rows: <math>0, 2, 6, 14, 30, 62</math>. They are each two less than a power of <math>2</math>, so we try to prove it: | We sum the first few rows: <math>0, 2, 6, 14, 30, 62</math>. They are each two less than a power of <math>2</math>, so we try to prove it: | ||
Line 32: | Line 31: | ||
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 \bmod{100}</math>. <math>2^{10}=1024</math>, so <math>2^{100}-2\equiv 24^{10}-2\equiv (2^3 \cdot 3)^{10} - 2 </math> <math>\equiv 1024^3 \cdot 81 \cdot 81 \cdot 9 - 2 \equiv 24^3 \cdot 19^2 \cdot 9 - 2 </math> <math>\equiv 74\bmod{100} \Rightarrow \mathrm{(E)}</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 \bmod{100}</math>. <math>2^{10}=1024</math>, so <math>2^{100}-2\equiv 24^{10}-2\equiv (2^3 \cdot 3)^{10} - 2 </math> <math>\equiv 1024^3 \cdot 81 \cdot 81 \cdot 9 - 2 \equiv 24^3 \cdot 19^2 \cdot 9 - 2 </math> <math>\equiv 74\bmod{100} \Rightarrow \mathrm{(E)}</math>. | ||
− | + | ==Solution 3 (plain recurrence solving) == | |
We derive the recurrence <math>S_{n+1}=2S_n + 2</math> as above. Without guessing the form of the solution at this point we can easily solve this recurrence. Note that one can easily get rid of the "<math>+2</math>" as follows: Let <math>S_n=T_n-2</math>. Then <math>S_{n+1}=T_{n+1}-2</math> and <math>2S_n+2 = 2(T_n-2)+2 = 2T_n-2</math>. Therefore <math>T_{n+1}=2T_n</math>. This obviously solves to <math>T_n=2^{n-1} T_1</math>. As <math>S_1=0</math>, we have <math>T_1=2</math>. Therefore <math>T_n=2^n</math> and consecutively <math>S_n=2^n-2</math>. | We derive the recurrence <math>S_{n+1}=2S_n + 2</math> as above. Without guessing the form of the solution at this point we can easily solve this recurrence. Note that one can easily get rid of the "<math>+2</math>" as follows: Let <math>S_n=T_n-2</math>. Then <math>S_{n+1}=T_{n+1}-2</math> and <math>2S_n+2 = 2(T_n-2)+2 = 2T_n-2</math>. Therefore <math>T_{n+1}=2T_n</math>. This obviously solves to <math>T_n=2^{n-1} T_1</math>. As <math>S_1=0</math>, we have <math>T_1=2</math>. Therefore <math>T_n=2^n</math> and consecutively <math>S_n=2^n-2</math>. |
Latest revision as of 12:58, 26 November 2020
Contents
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.
Let denote the sum of the numbers in row . What is the remainder when is divided by 100?
Solution 1
Note that if we re-draw the table with an additional diagonal row on each side, the table is actually just two of Pascal's Triangles, except translated and summed.
The sum of a row of Pascal's triangle is ; the sum of two of each of these rows, subtracting away the ones we included, yields . Now, and , and by the Chinese Remainder Theorem, we have .
Solution 2 (induction)
We sum the first few rows: . They are each two less than a power of , 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 .
Solution 3 (plain recurrence solving)
We derive the recurrence as above. Without guessing the form of the solution at this point we can easily solve this recurrence. Note that one can easily get rid of the "" as follows: Let . Then and . Therefore . This obviously solves to . As , we have . Therefore and consecutively .
See also
1995 AHSME (Problems • Answer Key • Resources) | ||
Preceded by Problem 26 |
Followed by Problem 28 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30 | ||
All AHSME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.