8.5. In the list $1,2, \ldots, 2016$, two numbers $a<b$ were marked, dividing the sequence into 3 parts (some of these parts might not contain any numbers at all). After that, the list was shuffled in such a way that $a$ and $b$ remained in their places, and no other of the 2014 numbers remained in the same part where they were initially. In how many ways could $a$ and $b$ have been chosen?
Answer: $1+2+\ldots+1008=1009 * 504=508536$ ways.

## Solution:

Hypothesis. We will prove that the question is equivalent to counting the number of ways to split 2014 into three ordered non-negative addends $2014=x+y+z$, for which the non-strict triangle inequality holds, i.e., $x+y \geq z, x+z \geq y, y+z \geq x$.

Necessity. If we choose $a$ and $b$, then we have formed three numerical segments, in which there are 2014 numbers in total. It is clear that if the number of numbers in one of them is greater than the sum of the numbers in the other two, we will not be able to shuffle the numbers in the specified way.

Sufficiency. Choose $a=x+1, b=x+y+2$, that is, divide the sequence into parts with $x, y$ and $z$ numbers. We will prove that we can shuffle the numbers in the specified way. Assume $x \geq y \geq z$. It is known that $y+z \geq x$, and the other inequalities are automatically satisfied. Now we will swap numbers from $y$ and $z$ in pairs until the number of untouched numbers in $y$ and $z$ is exactly $x$. After that, we swap all numbers from $x$ with all untouched numbers from $y$ and $z$ and obtain the desired permutation.

Why is this possible? First, the number of numbers in $y$ and $z$ is at least $x$ by the triangle inequality, and each action reduces the number of untouched numbers by 2. But $x+y+z=$

2014, so $x$ and $(y+z)$ have the same parity, which means we will eventually get the required result.

Counting the ways: We will iterate over $x$. It changes from 0 to 1007, then $y+z \geq x$ is satisfied.

$x=0, y \geq z, z \geq y$, therefore, $z=y=1007$ - one way

$x=1,1+y \geq z, z+1 \geq y, y=2013-z$, therefore, $1007 \geq z ; z \geq 1006$ - two ways

$x=k . k+y \geq z, z+k \geq y, y=2014-k-z$. Therefore, $k+2014-k-z \geq z, z+k \geq 2014-k-z$, that is, $1007 \geq z ; z \geq 1007-k-(k+1)$ ways.

In total, $1+2+\ldots+1008=1009 * 504=508536$ ways.

Criteria:

Only the answer - 0 points

Only the hypothesis - 1 point.

Only the necessity - 1 point.

Only the sufficiency - 2 points.

Only the counting - 3 points.

These points are summed.