1995 AHSME Problems/Problem 27

From AoPSWiki

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

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

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

1995 AHSME (Problems)
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

Personal tools

Navigation

Search

Toolbox