9,10

Someone has arranged a 10-volume collection of works in a random order. Let's call a disorder a pair of volumes where the volume with the higher number is to the left. For this arrangement of volumes, the number $S$ of all disorders has been calculated. What values can $S$ take?
If two adjacent volumes are swapped, the number of inversions will change (decrease or increase) by 1.

## Solution

It is clear that the number $S$ of inversions is not less than 0 and not more than the number of all possible pairs of 10 volumes (the number of such pairs is $10 \cdot 9: 2=45$). We will show that any value from 0 to 45 can be achieved with some arrangement of the volumes. Initially, arrange the volumes in reverse order. In this case, each pair of volumes will be an inversion, and the total number of inversions $S=45$. Suppose we already have an arrangement for which $S=i>0$; then we will find two adjacent volumes that form an inversion (such two volumes will be found, otherwise the arrangement of volumes would be correct and $S$ would be 0). By swapping these two volumes, we will get an arrangement with exactly one fewer inversion, that is, $S$ will become $i-1$. Thus, starting from an arrangement of volumes for which $S=45$, we can sequentially obtain arrangements for which $S=44,43, \ldots, 1,0$.

## Answer

Any integer value from 0 to 45.

Send a comment