Kvant Math Problem 942
For $n=1$, the partition is ${1}$ and ${2}$, hence
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m25s
Source on kvant.digital
Problem
The numbers 1, 2, $\ldots$, $2n-1$, $2n$ are divided into two groups containing $n$ numbers each. Let $a_1\lt a_2\lt\ldots\lt a_n$ be the numbers of the first group arranged in increasing order, and $b_1\gt b_2\gt\ldots\gt b_n$ the numbers of the second group arranged in decreasing order. Prove that $$|a_1-b_1|+|a_2-b_2|+\ldots+|a_n-b_n|=n^2.$$
V. V. Proizvolov
All-Union Mathematical Olympiad (1985)
Exploration
For $n=1$, the partition is ${1}$ and ${2}$, hence
$$|1-2|=1=1^2.$$
For $n=2$, take the partition ${1,4}$ and ${2,3}$. Then
$$a_1=1,\quad a_2=4,\quad b_1=3,\quad b_2=2,$$
and
$$|1-3|+|4-2|=2+2=4=2^2.$$
Take another partition, ${1,2}$ and ${3,4}$. Then
$$|1-4|+|2-3|=3+1=4.$$
The value appears independent of the partition.
The expression involves pairs $(a_i,b_i)$ formed from opposite ends of the two ordered groups. A natural question is whether $a_i-b_i$ always has the same sign. This is false in general. For the partition ${1,4}$ and ${2,3}$,
$$a_1-b_1=-2,\qquad a_2-b_2=2.$$
Hence the absolute values cannot simply be removed.
The crucial point is to understand the relative positions of $a_i$ and $b_i$. Since $a_i$ is the $i$-th smallest element of the first group, at least $i$ numbers of the first group do not exceed $a_i$. Since $b_i$ is the $i$-th largest element of the second group, at least $i$ numbers of the second group are not smaller than $b_i$. These two collections are disjoint. Therefore at least $2i$ numbers among $1,\dots,2n$ lie in the interval $[,b_i,\infty)$ together with $(-\infty,a_i,]$. Counting the complement suggests a relation between $a_i$ and $b_i$.
Trying to make this precise, among the numbers strictly between $a_i$ and $b_i$ there can be at most
$$2n-2i$$
numbers, because at least $i$ numbers of the first group lie on one side and at least $i$ numbers of the second group lie on the other. Since the interval between two integers contains exactly $|a_i-b_i|-1$ integers strictly between them,
$$|a_i-b_i|-1\le 2n-2i,$$
hence
$$|a_i-b_i|\le 2n-2i+1.$$
Testing examples shows equality always holds. The hidden step is proving that there are exactly $2n-2i$ numbers strictly between $a_i$ and $b_i$.
Problem Understanding
We partition the set ${1,2,\dots,2n}$ into two groups of size $n$. The first group is written increasingly as
$$a_1<a_2<\cdots<a_n,$$
and the second decreasingly as
$$b_1>b_2>\cdots>b_n.$$
We must prove that
$$\sum_{i=1}^n |a_i-b_i|=n^2.$$
This is a Type B problem. The statement is given and must be proved.
The core difficulty is to determine the individual quantities $|a_i-b_i|$. The examples suggest that they are not arbitrary. The key insight is that for each index $i$, the two numbers $a_i$ and $b_i$ are separated by exactly $2n-2i$ integers, which forces
$$|a_i-b_i|=2n-2i+1.$$
Summing these fixed values yields $n^2$.
Proof Architecture
For each $i$, the number of integers strictly between $a_i$ and $b_i$ is at most $2n-2i$; this follows because at least $i$ elements of the first group lie on one side of the interval and at least $i$ elements of the second group lie on the other side.
For each $i$, the number of integers strictly between $a_i$ and $b_i$ is at least $2n-2i$; this follows because every element of the first group larger than $a_i$ and every element of the second group smaller than $b_i$ must lie strictly between them.
Combining the two bounds yields that exactly $2n-2i$ integers lie strictly between $a_i$ and $b_i$, hence
$$|a_i-b_i|=2n-2i+1.$$
Summing these equalities gives
$$\sum_{i=1}^n |a_i-b_i| =\sum_{i=1}^n (2n-2i+1) =n^2.$$
The lemma most likely to fail under scrutiny is the first counting bound, because one must handle both possibilities $a_i<b_i$ and $a_i>b_i$ without accidentally assuming a sign.
Solution
Fix an index $i$.
First suppose that $a_i<b_i$.
The numbers
$$a_1,a_2,\dots,a_i$$
belong to the first group and satisfy $a_j\le a_i$. Hence at least $i$ numbers of ${1,\dots,2n}$ lie at or to the left of $a_i$.
The numbers
$$b_1,b_2,\dots,b_i$$
belong to the second group and satisfy $b_j\ge b_i$. Hence at least $i$ numbers of ${1,\dots,2n}$ lie at or to the right of $b_i$.
These two sets are disjoint because $a_i<b_i$. Therefore at least $2i$ numbers do not lie strictly between $a_i$ and $b_i$. Since there are $2n$ numbers altogether, at most
$$2n-2i$$
numbers lie strictly between $a_i$ and $b_i$.
On the other hand,
$$a_{i+1},a_{i+2},\dots,a_n$$
all belong to the first group and are greater than $a_i$. Because $b_i$ belongs to the other group, none of these numbers can equal $b_i$. Since $a_i<b_i$, each of them lies strictly between $a_i$ and $b_i$.
Similarly,
$$b_{i+1},b_{i+2},\dots,b_n$$
all belong to the second group and are smaller than $b_i$. Because $a_i$ belongs to the other group, none of them equals $a_i$. Since $a_i<b_i$, each of them also lies strictly between $a_i$ and $b_i$.
These two collections are disjoint and contain
$$(n-i)+(n-i)=2n-2i$$
numbers. Hence at least $2n-2i$ numbers lie strictly between $a_i$ and $b_i$.
The upper and lower bounds coincide, so exactly $2n-2i$ numbers lie strictly between $a_i$ and $b_i$. Consequently
$$b_i-a_i=(2n-2i)+1,$$
and therefore
$$|a_i-b_i|=2n-2i+1.$$
Now suppose that $a_i>b_i$. Interchanging the roles of $a_i$ and $b_i$ in the preceding argument gives the same conclusion: exactly $2n-2i$ numbers lie strictly between them, and thus
$$|a_i-b_i|=2n-2i+1.$$
Hence for every $i$,
$$|a_i-b_i|=2n-2i+1.$$
Summing over $i$ yields
$$\sum_{i=1}^n |a_i-b_i| =\sum_{i=1}^n (2n-2i+1).$$
Since
$$(2n-1)+(2n-3)+\cdots+1$$
is the sum of the first $n$ odd positive integers,
$$\sum_{i=1}^n (2n-2i+1)=n^2.$$
Thus
$$|a_1-b_1|+|a_2-b_2|+\cdots+|a_n-b_n|=n^2.$$
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the upper bound. When $a_i<b_i$, the sets
$${a_1,\dots,a_i} \quad\text{and}\quad {b_1,\dots,b_i}$$
contain $2i$ distinct numbers because the two groups are disjoint. Every element of the first set is at most $a_i$, and every element of the second set is at least $b_i$. Hence none of these $2i$ numbers lies strictly between $a_i$ and $b_i$. Forgetting to justify disjointness would invalidate the count.
The second delicate step is the lower bound. The numbers
$$a_{i+1},\dots,a_n$$
are all strictly larger than $a_i$. To conclude that they are also strictly smaller than $b_i$, one uses $a_i<b_i$ together with the fact that $b_i$ belongs to the other group. If some $a_k$ exceeded $b_i$, then it would not lie between the endpoints. The counting argument works because every element of the first group larger than $a_i$ must actually lie in the interval $(a_i,b_i)$.
The third delicate point is converting the count of interior integers into a distance. If exactly $m$ integers lie strictly between two distinct integers $x$ and $y$, then
$$|x-y|=m+1.$$
For example, between $3$ and $8$ there are $4$ integers, namely $4,5,6,7$, and indeed $8-3=5$. Applying this with $m=2n-2i$ yields
$$|a_i-b_i|=2n-2i+1.$$
Alternative Approaches
A different proof uses ranks. For each $i$, consider the position of $a_i$ among all numbers $1,\dots,2n$. Exactly $i-1$ elements of the first group are smaller than $a_i$, and exactly $n-i$ elements of the second group are smaller than $b_i$. Careful rank counting shows that the ranks of $a_i$ and $b_i$ differ by precisely $2n-2i+1$, which is equivalent to
$$|a_i-b_i|=2n-2i+1.$$
Summing then gives the result.
The counting proof presented above is preferable because it works directly with the interval between $a_i$ and $b_i$. The quantity to be summed is an absolute difference, and counting the integers lying between the endpoints converts that difference immediately into a combinatorial statement whose upper and lower bounds match exactly.