Difference between revisions of "1995 AHSME Problems/Problem 27"
Isabelchen (talk | contribs) m (→Side Note (Chinese Remainder Theorem)) |
Isabelchen (talk | contribs) m (→Side Note (Chinese Remainder Theorem)) |
||
(5 intermediate revisions by the same user not shown) | |||
Line 24: | 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>. | ||
− | === | + | ===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>. | 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: | 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>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> | 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 | + | 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>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> | <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] | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] |
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.