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}\] (Error compiling LaTeX. Unknown error_msg)

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

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\equiv 2^{20}-2\bmod{100}$ . $2^{10}=1024$ , so $2^{20}-2\equiv 24^2-2\equiv 74\bmod{100} \Rightarrow \mathrm{(E)}$ .

Page

Toolbox

Search

1995 AHSME Problems/Problem 27

Problem

Solution

See also