# 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}$.