Monotonically increasing sequences with sums

Let $a_1, \dots, a_{1007}$ and $b_1, \dots, b_{1007}$ be monotonically increasing sequences such that:

For all $i$, $0 \leq a_i \leq 2013$ and $0 \leq b_i \leq 2013$.

For $i \neq j$, $a_i + a_j \neq 2013$ and $b_i + b_j \neq 2013$

$a_0 = b_0$

There exists a real number S such that for all $i$, $a_i + b_{1008-i} = S$.

What are the possible values of $S$?

Solution

Note that for $a_i$ and $b_i$, we need to choose 1007 numbers from 2014 numbers (0,1,...,2013) and no two of those chosen ones may add up to 2013. Thus, from each of the following pairs of numbers $(0,2013), (1,2012), \dots, (1006,1007)$ we must choose exactly one number. Thus, at most one of 0 or 2013 may be chosen. For now, let's assume that $a_1 = b_1 = 0$, which means 2013 is not chosen in both $a_i$ and $b_i$. We'll deal with the other cases later.

Let $k$ be the first number that is not chosen in $a_i$. That means $0, \dots, k-1$ are all chosen, so we have $a_1 = 0, a_2 = 1, \dots, a_k = k-1$.

This also means that $2013, \dots, 2013-(k-1)$ are not chosen but $2013-k$ is chosen. In other words, $2013-k$ is the largest chosen number in $a_i$, so $a_{1007} = 2013-k$. Because $b_1 = 0$ then $S = 2013-k$. That means $b_{1007}=2013-k - a_0 = 2013-k$

Because $2013-k$ is the largest chosen number in $b_i$, then $2013-k+1,\dots,2013$ are not chosen in $b_i$, therefore $0,\dots,k-1$ are chosen in $b_i$ and $k$ is not chosen in $b_i$.

Because $0,\dots,k-1$ are chosen in $b_i$, and $S = 2013-k$, that means $2013-k, 2013-k-1, \dots, 2013-(2k-1)$ are chosen in $a_i$, which means $k,k+1,\dots,2k-1$ are not chosen in $a_i$. Likewise, because $0,\dots,k-1$ are chosen in $a_i$, and $S = 2013-k$, that means $2013-k, 2013-k-1, \dots, 2013-(2k-1)$ are chosen in $b_i$, which means $k,k+1,\dots,2k-1$ are not chosen in $b_i$.

At this point, we have established the following fact:

• The first $k$ numbers in $a_i$ and $b_i$ are chosen, and the next $k$ numbers are not chosen.
• The last $k$ numbers in $a_i$ and $b_i$ are not chosen, and the previous $k$ numbers are chosen.

We would like then to claim that this pattern would have to continue itself all the way to the "middle" of the sequences, which finally means that $2k$ divides 2014. Formally, we claim that for each $m \geq 0$, we have the following:

• $2km, \dots, (2m+1)k-1$ are chosen in $a_i$ and $b_i$.
• $(2m+1)k, \dots, (2m+2)k-1$ are not chosen in $a_i$ and $b_i$.
• $2013-((2m+1)k-1), \dots, 2013-2km$ are not chosen in $a_i$ and $b_i$.
• $2013-((2m+2)k-1), \dots, 2013-(2m+1)k$ are chosen in $a_i$ and $b_i$.

The case of $m=0$ has been proven above. Now suppose it holds for $m$.

Because $(2m+1)k, \dots, (2m+2)k-1$ are not chosen in $a_i$ and $S = 2013-k$ then $2013-k-((2m+2)k-1), \dots, 2013-k-(2m+1)k$ are not chosen in $b_i$. In other words, $2013-((2m+3)k-1), \dots, 2013-(2m+2)k$ are not chosen in $b_i$. Similarly, they're not chosen in $a_i$ as well.

Now because those are not chosen in $b_i$, then $(2m+2)k,\dots,(2m+3k)-1$ are chosen in $b_i$. Similarly, chosen in $a_i$ as well.

Because $S=2013-k$ and $(2m+2)k,\dots,(2m+3k)-1$ are chosen in $b_i$ then $2013-((2m+4)k-1), \dots, 2013-(2m+3)k$ are chosen in $a_i$, and similarly, chosen in $b_i$ as well.

Because the above are chosen, then $(2m+3)k, \dots, (2m+4)k-1$ are not chosen in $a_i, b_i$, and this completes the induction step.

So now that our claim is proven, we note that this pattern must continue for all values of $m$ as long as no index becomes negative. There is no restriction of the value of $m$ in our proof of the claim. That means that towards the end of the sequence, our pattern must "line up" with what we know about $a_{1007}$ and $b_{1007}$, namely, that $2013-k$ is the largest chosen number in the sequence. This means that the sequence of numbers from 0 to 2013 is divided into an even number of groups, each having $k$ elements. Each group would alternate between all being chosen and all being not chosen. It's easy to check that this configuration matches the conditions above.

From there, we know that $2k | 2014$ or $k | 1007$. Because $1007 = 19 \times 53$, then we have four possible values of $k$.

If $k=1$, then both sequences look like this: $0,2,4,\dots, 2012$. Then $S=2012$.

If $k=19$, then both sequences look like this: $0,1,2,\dots,17,18,38,39,\dots,55,56,\dots, 988$. Then $S=1994$.

If $k=53$, then both sequences look like this: $0,1,2,\dots,51,52,106,107,\dots,158,159,\dots, 988$. Then $S=1960$.

If $k=1007$, then both sequences look like this: $0,1,2,\dots,1006$. Then $S=1006.

Now, we have to address the case where 0 is not chosen in $a_i$ and $b_i$. We define new sequences $c_i = 2013-a_{1008-i}$ and $d_i = 2013-b_{1008-i}$. It's easy to see that $c_i,d_i$ satisfy the conditions of the problem, and since $0$ is not chosen in $a_i,b_i$ then 2013 must be chosen in them, which means $0$ is chosen in both $c_i,d_i$. This reduces $c_i,d_i$ to the case above, except $S$ is replaced with $4026-S$.

Because the possible values for $S$ in the first case is $1007,1960, 1994, 2012$ then the possible values for $S$ in this case is $2014,2032,2134,3020$.