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 $(1, 2007)$. Inserting the difference between $1$ and $2007$ between them, we get the sequence $(1, 2006, 2007)$. Repeating the process of inserting differences between numbers, we get the sequence $(1, 2005, 2006, 1, 2007)$. A third iteration of this process results in $(1, 2004, 2005, 1, 2006, 2005, 1, 2006, 2007)$. A total of $2007$ iterations produces a sequence with $2^{2007}+1$ terms. If the integer $2004$ appears a total of $N$ times among these $2^{2007}+1$ terms, find the remainder when $N$ gets divided by $2007$.

Solution

Consider the number of times a certain number appears, and consider the lowest number in each iteration. Since $2007$ is the largest number of the sequence, it will appear only one time no matter how many iterations occurred. Also, in the part $1$, $2007$ (last two terms of sequence), one iteration results in $1$,$2006$,$2007$, and another results in $1$,$2005$,$2006$,$1$,$2007$.

Let $n$ be a positive integer less than $2007$ but more than $0$. Assume that part of the sequence is $1$, $n$, $n+1$, $1$ (note that reversing sequence won’t change proof). After an iteration, one of the parts of the sequence will be $1$, $n-1$, $n$, $1$, $n+1$, $n$, $1$. This means that each iteration produces numbers that are less than $n+1$, and each number more than $2$ will be next to $1$ and a consecutive number. Also, each number will have a number one lower and $1$ next to the original after an iteration.

Finally, to count the number of times $2006$ appears in a sequence, note that another one only appears if the previous iteration has a $1$ next to a $2007$. With this in mind, we can make a table that indicates the number of times a term appears in a sequence. Let $a_n$ be the number of times $2007$ appears, $b_n$ be the number of times $2006$ appears, $c_n$ be the number of times $2005$ appears, and $d_n$ be the number of times $2004$ appears, where $n$ is the number of iterations that happened.

Number of iterations $a_n$ $b_n$ $c_n$ $d_n$
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 $n$ is odd, $d_{n}$ will result in a sequence that has a common third difference, so we can write a cubic function. Let $x = \tfrac{n+1}{2}$, so the wanted points $(x,d_{n})$ are $(1,0)$, $(2,1)$, $(3,7)$, and $(4,22)$.

If the given cubic is $ax^3 + bx^2 + cx + d$, then \[a+b+c+d = 0\] \[8a+4b+2c+d = 1\] \[27a + 9b + 3c + d = 7\] \[64a + 16b + 4c + d = 22\] Solving the system results in $a = \tfrac46$, $b = -\tfrac96$, $c = \tfrac56$, and $d = 0$, so the cubic is \[\frac{4x^3 - 9x^2 + 5x}{6}\] \[\frac{x(4x-5)(x-1)}{6}\] If $n = 2007$, then $x = 1004$, so $d_{2007}$ equals \[\frac{1004 \cdot 4011 \cdot 1003}{6}\] \[502 \cdot 1337 \cdot 1003\] Thus, $N = 673187522$, and the remainder when $N$ is divided by $2007$ is $\boxed{1589}$.

See Also

2007 iTest (Problems, Answer Key)
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