1995 AHSME Problems/Problem 27
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.
Let denote the sum of the numbers in row . What is the remainder when is divided by 100?
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 .
Remark (Chinese Remainder Theorem)
Solution 1 needs to calculate the last digits of , meaning to solve . , we are going to get from and .
By Chinese Remainder Theorem, the general solution of the system of linear congruences is:
, , Find and such that , Then
In this problem, , :
, , , Then
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 .
Solution 3 (plain recurrence solving)
We derive the recurrence 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 "" as follows: Let . Then and . Therefore . This obviously solves to . As , we have . Therefore and consecutively .
|1995 AHSME (Problems • Answer Key • Resources)|
|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|