1995 AHSME Problems/Problem 27

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)}$ .

Side Note (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 system of $2$ linear congruences is:

, 
Find  and  such that , 
So,

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

, 
, 
So,

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$ .

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

Page

Toolbox

Search