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

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

Page

Toolbox

Search

2007 iTest Problems/Problem 54

Problem

Solution

See Also