2007 iTest Problems/Problem 54
The following problem is from the Ultimate Question of the 2007 iTest, where solving this problem required the answer of a previous problem. When the problem is rewritten, the T-value is substituted.
Problem
Consider the sequence . Inserting the difference between and between them, we get the sequence . Repeating the process of inserting differences between numbers, we get the sequence . A third iteration of this process results in . A total of iterations produces a sequence with terms. If the integer appears a total of times among these terms, find the remainder when gets divided by .
Solution
Consider the number of times a certain number appears, and consider the lowest number in each iteration. Since is the largest number of the sequence, it will appear only one time no matter how many iterations occurred. Also, in the part , (last two terms of sequence), one iteration results in ,,, and another results in ,,,,.
Let be a positive integer less than but more than . Assume that part of the sequence is , , , (note that reversing sequence won’t change proof). After an iteration, one of the parts of the sequence will be , , , , , , . This means that each iteration produces numbers that are less than , and each number more than will be next to and a consecutive number. Also, each number will have a number one lower and next to the original after an iteration.
Finally, to count the number of times appears in a sequence, note that another one only appears if the previous iteration has a next to a . With this in mind, we can make a table that indicates the number of times a term appears in a sequence. Let be the number of times appears, be the number of times appears, be the number of times appears, and be the number of times appears, where is the number of iterations that happened.
Number of iterations | ||||
1 | 1 | 1 | 0 | 0 |
2 | 1 | 1 | 1 | 0 |
3 | 1 | 2 | 2 | 1 |
4 | 1 | 2 | 4 | 3 |
5 | 1 | 3 | 6 | 7 |
6 | 1 | 3 | 9 | 13 |
7 | 1 | 4 | 12 | 22 |
8 | 1 | 4 | 16 | 34 |
9 | 1 | 5 | 20 | 50 |
10 | 1 | 5 | 25 | 70 |
Notice that when is odd, will result in a sequence that has a common third difference, so we can write a cubic function. Let , so the wanted points are , , , and .
If the given cubic is , then Solving the system results in , , , and , so the cubic is If , then , so equals Thus, , and the remainder when is divided by is .
See Also
2007 iTest (Problems) | ||
Preceded by: Problem 53 |
Followed by: Problem 55 | |
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 • 31 • 32 • 33 • 34 • 35 • 36 • 37 • 38 • 39 • 40 • 41 • 42 • 43 • 44 • 45 • 46 • 47 • 48 • 49 • 50 • 51 • 52 • 53 • 54 • 55 • 56 • 57 • 58 • 59 • 60 • TB1 • TB2 • TB3 • TB4 |