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 "1995 AHSME Problems/Problem 27"

m (→‎See also)
m (→‎Side Note (Chinese Remainder Theorem))
 
(16 intermediate revisions by 8 users not shown)
Line 7: Line 7:
 
& & 3 & & 4 & & 4 & & 3 & & \\
 
& & 3 & & 4 & & 4 & & 3 & & \\
 
& 4 & & 7 & & 8 & & 7 & & 4 & \\
 
& 4 & & 7 & & 8 & & 7 & & 4 & \\
−
5 & & 11 & & 15 & & 15 & & 11 & & 5 & \end{tabular}</cmath>
+
5 & & 11 & & 15 & & 15 & & 11 & & 5 \end{tabular}</cmath>
  
 
Let <math>f(n)</math> denote the sum of the numbers in row <math>n</math>. What is the remainder when <math>f(100)</math> is divided by 100?
 
Let <math>f(n)</math> denote the sum of the numbers in row <math>n</math>. What is the remainder when <math>f(100)</math> is divided by 100?
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==
+
==Solution 1 ==
−
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:
+
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 & & & & \\
 +
& & & & 1 & & 1 & & 1 & & 1 & & & \\
 +
& & & 1 & & 2 & & 2 & & 2 & & 1 & & \\
 +
& & 1 & & 3 & & 4 & & 4 & & 3 & & 1 & \\
 +
& 1 & & 4 & & 7 & & 8 & & 7 & & 4 & & 1  \\
 +
1 & & 5 & & 11 & & 15 & & 15 & & 11 & & 5 & & 1 \end{tabular}</cmath>
  
−
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>.
+
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>.
 +
 
 +
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:
 +
 
 +
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 \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>.
  
 
==See also==
 
==See also==
Line 22: Line 55:
  
 
[[Category:Introductory Number Theory Problems]]
 
[[Category:Introductory Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 08:45, 18 February 2022

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}\]

Let $f(n)$ denote the sum of the numbers in row $n$. What is the remainder when $f(100)$ is divided by 100?

$\mathrm{(A) \ 12 } \qquad \mathrm{(B) \ 30 } \qquad \mathrm{(C) \ 50 } \qquad \mathrm{(D) \ 62 } \qquad \mathrm{(E) \ 74 }$

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. \[\begin{tabular}{ccccccccccccccc} & & & & & 1 & & 0 & & 1 & & & & \\ & & & & 1 & & 1 & & 1 & & 1 & & & \\ & & & 1 & & 2 & & 2 & & 2 & & 1 & & \\ & & 1 & & 3 & & 4 & & 4 & & 3 & & 1 & \\ & 1 & & 4 & & 7 & & 8 & & 7 & & 4 & & 1 \\ 1 & & 5 & & 11 & & 15 & & 15 & & 11 & & 5 & & 1 \end{tabular}\]

The sum of a row of Pascal's triangle is $2^{n-1}$; the sum of two of each of these rows, subtracting away the $2$ ones we included, yields $f(n) = 2^n - 2$. Now, $f(100) = 2^{100} - 2 \equiv 2 \pmod{4}$ and $f(100) = 2^{100} - 2 \equiv 2^{20 \cdot 5} - 2 \equiv -1 \pmod{25}$, and by the Chinese Remainder Theorem, we have $f(100) \equiv 74 \pmod{100} \Longrightarrow \mathrm{(E)}$.

Remark (Chinese Remainder Theorem)

Solution 1 needs to calculate the last $2$ digits of $2^{100}$, meaning to solve $2^{100} (\bmod{ 100})$. $100 = 4 \cdot 25$, we are going to get $n \bmod{ 100}$ from $n \bmod{ 4}$ and $n \bmod{ 25}$.

By Chinese Remainder Theorem, the general solution of the system of $2$ linear congruences is: 

$n \equiv r_1 (\bmod { \quad m_1})$, $n \equiv r_2 (\bmod { \quad m_2})$, $(m_1, m_2) = 1$
Find $k_1$ and $k_2$ such that $k_1 m_1 \equiv 1 (\bmod{ \quad m_2})$, $k_2 m_2 \equiv 1 (\bmod{ \quad m_1})$
Then $n \equiv k_2 m_2 r_1 + k_1 m_1 r_2 (\bmod{ \quad m_1 m_2})$

In this problem, $2^{100} \equiv (2^{10})^{10} \equiv 1024^{10} \equiv 24^{10} \equiv (-1)^{10} \equiv 1 (\bmod{ \quad 25})$, $2^{100} \equiv 0 (\bmod{ \quad 4})$: 

$n \equiv 1 (\bmod{ \quad 25})$, $n \equiv 0 (\bmod{ \quad 4})$, $(25, 4) = 1$
$1 \cdot 25 \equiv 1 (\bmod{ \quad 4})$, $19 \cdot 4 \equiv 1 (\bmod{ \quad 25})$
Then $n \equiv 19 \cdot 4 \cdot 1 + 1 \cdot 25 \cdot 0 \equiv 76 (\bmod{ \quad 100})$

~isabelchen

Solution 2 (induction)

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 $n$ be $S_n$. 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 $S_{n+1}=2S_n-2(n-1)+2(n-1)+2=2S_n+2$. If $S_n$ is two less than a power of 2, then it is in the form $2^x-2$. $S_{n+1}=2^{x+1}-4+2=2^{x+1}-2$.

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 $2^1-2$, the sum of the numbers in row $n$ is $2^n-2$. Thus, using Modular arithmetic, $f(100)=2^{100}-2 \bmod{100}$. $2^{10}=1024$, so $2^{100}-2\equiv 24^{10}-2\equiv (2^3 \cdot 3)^{10} - 2$ $\equiv 1024^3 \cdot 81 \cdot 81 \cdot 9 - 2 \equiv 24^3 \cdot 19^2 \cdot 9 - 2$ $\equiv 74\bmod{100} \Rightarrow \mathrm{(E)}$.

Solution 3 (plain recurrence solving)

We derive the recurrence $S_{n+1}=2S_n + 2$ 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 "$+2$" as follows: Let $S_n=T_n-2$. Then $S_{n+1}=T_{n+1}-2$ and $2S_n+2 = 2(T_n-2)+2 = 2T_n-2$. Therefore $T_{n+1}=2T_n$. This obviously solves to $T_n=2^{n-1} T_1$. As $S_1=0$, we have $T_1=2$. Therefore $T_n=2^n$ and consecutively $S_n=2^n-2$.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1995_AHSME_Problems/Problem_27&oldid=171351"