## Sum of differences

For a given even positive integer, we create two lists of integers such that every positive integer less than or equal to the given integer belongs to exactly one of the two lists and both lists contain an equal number of integers. There is a third list which is initially empty. Then, at every step, we remove the smallest number from the first list, the largest number from the second list and insert the positive difference between the two numbers into the third list.

What do we get if we divide the square of the given even positive integer by the sum of all the numbers in the third list when the first list becomes empty?

[SOLVED]

#### Ilan Mayer solved this puzzle:

Let the given number be $$2n$$.

Let the smallest number in the first list be $$S_1$$. Let the largest number in the second list be $$L_2$$.

There are $$n$$ numbers greater than $$n$$, $$n$$ numbers less than or equal to $$n$$, and $$n$$ numbers in each list.

If $$S_1 \gt n$$, then all numbers in the first list are greater than $$n$$. So, $$L_2 \leqslant n$$.

If $$S_1 \geqslant n$$, then at least one number greater than $$n$$ is in the second list. So, $$L_2 \gt n$$.

Therefore, the first difference is between a number greater than $$n$$ and one less than $$n$$.

After removing these two numbers there are $$n - 1$$ numbers greater than n, $$n - 1$$ numbers less than or equal to n, and $$n - 1$$ numbers in each list. The above argument now applies again, so the second difference is between a number greater than $$n$$ and one less than $$n$$. This applies similarly to all the steps.

Therefore the sum of differences is:

\begin{align*} \sum_{k = n + 1}^{2n} k - \sum_{k = 1}^n k & = \sum_{k = 1}^{2n} k - 2 \sum_{k = 1}^n k \\ & = \sum_{k = 1}^{2n} k - 2 \sum_{k = 1}^n k \\ & = \left(\frac{2n(2n + 1)}{2}\right) - 2 \left(\frac{n(n + 1)}{2}\right) \\ & = n^2. \end{align*}

So, the result of the division is $\frac{(2n)^2}{n^2} = 4.$

#### Susam Pal from cotpi added:

This problem is based on a problem posed by Vyacheslav Proizvolov in the 1985 All-Union Soviet Student Olympiad. The problem soon became popular as Proizvolov's identity. The identity can be stated and proven as follows.

Theorem. The numbers $$1, 2, \dots, n$$ are partitioned arbitrarily into two groups of $$n$$ integers each. If $$a_1 \lt a_2 \lt \dots \lt a_n$$ are the numbers in the first group and $$b_1 \gt b_2 \gt \dots \gt b_n$$ are the numbers in the second one, $\sum_{i = 1}^n |a_i - b_i| = n^2.$

Proof. For any integer $$i$$ where $$1 \leqslant i \leqslant n$$, let us assume $$a_i \leqslant n$$ and $$b_i \leqslant n$$. So,

\begin{align*} 1 \leqslant a_1 \lt a_2 \lt \dots \lt a_i \leqslant n \\ 1 \leqslant b_n \lt b_{n - 1} \lt \dots \lt b_i \leqslant n. \end{align*}

This implies that there are $$n + 1$$ distinct positive integers less than or equal to $$n$$. This is a contradiction. Now, let us assume $$a_i \gt n$$ and $$b_i \gt n$$.

\begin{align*} 2n \geqslant a_n \gt a_{n - 1} \gt \dots \gt a_i \gt n \\ 2n \geqslant b_1 \gt b_2 \gt \dots \gt b_i \gt n. \end{align*}

This implies that there are n + 1 distinct integers greater than n but less than or equal to 2n. Again, we have a contradiction. This shows that either $$a_i \leqslant n \lt b_i$$ or $$b_i \leqslant n \lt a_i$$. In other words, exactly one of $$a_i$$ and $$b_i$$ belongs to $$\{1, 2, \dots, n\}$$ and the other belongs to $$\{n + 1, n + 2, \dots, 2n\}$$. Hence,

\begin{align*} \sum_{i = 1}^n |a_i - b_i| & = \sum_{k = 1}^{n} (n + k) - \sum_{k = 1}^n k \\ & = \sum_{k = 1}^{n} (n + k - k) \\ & = \sum_{k = 1}^{n} n \\ & = n^2. \end{align*}

### Credit

This puzzle is based on:

• Savchev, Svetoslav; Andreescu, Titu. Mathematical Miniatures. Washington, D.C.: Mathematical Association of America, 2003. 66. Chapter 18.