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 denote the sum of the numbers in row . What is the remainder when is divided by 100?

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.

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 .

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 .