Difference between revisions of "1995 AHSME Problems/Problem 27"
m (→Solution) |
Isabelchen (talk | contribs) m (→Side Note (Chinese Remainder Theorem)) |
||
(10 intermediate revisions by 2 users not shown) | |||
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) | + | ===Remark (Chinese Remainder Theorem)=== |
+ | |||
+ | Solution 1 needs to calculate the last <math>2</math> digits of <math>2^{100}</math>, meaning to solve <math>2^{100} (\bmod{ 100})</math>. <math>100 = 4 \cdot 25</math>, we are going to get <math>n \bmod{ 100}</math> from <math>n \bmod{ 4}</math> and <math>n \bmod{ 25}</math>. | ||
+ | |||
+ | By Chinese Remainder Theorem, the general solution of the system of <math>2</math> linear congruences is: | ||
+ | <math>n \equiv r_1 (\bmod { \quad m_1})</math>, <math>n \equiv r_2 (\bmod { \quad m_2})</math>, <math>(m_1, m_2) = 1</math> | ||
+ | Find <math>k_1</math> and <math>k_2</math> such that <math>k_1 m_1 \equiv 1 (\bmod{ \quad m_2})</math>, <math>k_2 m_2 \equiv 1 (\bmod{ \quad m_1})</math> | ||
+ | Then <math>n \equiv k_2 m_2 r_1 + k_1 m_1 r_2 (\bmod{ \quad m_1 m_2})</math> | ||
+ | |||
+ | In this problem, <math>2^{100} \equiv (2^{10})^{10} \equiv 1024^{10} \equiv 24^{10} \equiv (-1)^{10} \equiv 1 (\bmod{ \quad 25})</math>, <math>2^{100} \equiv 0 (\bmod{ \quad 4})</math>: | ||
+ | <math>n \equiv 1 (\bmod{ \quad 25})</math>, <math>n \equiv 0 (\bmod{ \quad 4})</math>, <math>(25, 4) = 1</math> | ||
+ | <math>1 \cdot 25 \equiv 1 (\bmod{ \quad 4})</math>, <math>19 \cdot 4 \equiv 1 (\bmod{ \quad 25})</math> | ||
+ | Then <math>n \equiv 19 \cdot 4 \cdot 1 + 1 \cdot 25 \cdot 0 \equiv 76 (\bmod{ \quad 100})</math> | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
+ | |||
+ | ==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 47: | ||
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 09:45, 18 February 2022
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
.
Remark (Chinese Remainder Theorem)
Solution 1 needs to calculate the last digits of
, meaning to solve
.
, we are going to get
from
and
.
By Chinese Remainder Theorem, the general solution of the system of linear congruences is:
,
,
Find
and
such that
,
Then
![]()
In this problem, ,
:
,
,
![]()
,
Then
![]()
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.