Estonian Math Competitions

Let all 100 volumes be placed to a shelf $a$ in some order. For every $i=1,2,...,100$, let $a_i$ be the number of the volume that occurs as the $i$th in this order. In the order the volumes occur on shelf $a$, we start relocating the volumes to two new shelves $b$ and $c$. We place a volume to the end of shelf $b$ if, as the intermediate result, all volumes on shelf $b$ would be increasingly sorted by volume numbers. Otherwise, we place the volume to the end of shelf $c$ if, as the intermediate result, all volumes on shelf $c$ would be increasingly sorted by volume numbers. Continuing this way, we either can relocate all volumes onto two shelves in such a way that all volumes on either shelf are increasingly sorted by volume numbers or get stuck on some step $k$ of the process because $a_k$ is less than the number of the last volume on both new shelves. In the last case, let the number of the last volume on shelf $c$ be $a_j$; then, by assumptions, $j<k$ and $a_j>a_k$. Since volume No $a_j$ has been relocated to shelf $c$, some volume with number $a_i$ must occur on shelf $b$ such that $i<j$ and $a_i>a_j$. This means that pairs $(i,j)$ and $(j,k)$ were initially reversed. Hence we can conclude that, in the case of Juku's favourite orderings, all volumes can be relocated to two shelves, i.e, there exist two tuples $a_{i_1},a_{i_2},...,a_{i_s}$ and $a_{j_1},a_{j_2},...,a_{j_t}$ with $s+t=100$, where $i_1<...<i_s$, $a_{i_1}<...<a_{i_s}$ and $j_1<...<j_t$, $a_{j_1}<...<a_{j_t}$. The number of pairs $(i,j)$ such that $i<j$ and the numbers $a_i$ and $a_j$ are in distinct tuples is exactly $st$. Each reversed pair $(i,j)$ must be one of these $st$ pairs. Thus the number of reversed pairs does not exceed $st$. As $st\le (\frac{s+t}{2}{)}^2=50^2=2500$, the number of reversed pairs cannot exceed 2500. The number 2500 is achieved by the order $51,52,...,100,1,2,...,50$.

---

Alternative solution.

Let all 100 volumes be placed to the shelf in some order. Consider the graph whose vertices are numbers $1,2,...,100$ and an edge occurs between vertices $i$ and $j$ if and only if either $(i,j)$ or $(j,i)$ (depending on whether $i<j$ or $j<i$) is reversed. Suppose that the graph contains an odd cycle. Such cycle must contain three consecutive vertices $i,j$ and $k$ that are in either increasing or decreasing order; w.l.o.g., assume that $i<j<k$. Then pairs $(i,j)$ and $(j,k)$ are both reversed. Thus under the conditions of the problem, the graph cannot contain an odd cycle. Hence the graph is bipartite. Let the numbers of vertices in the two parts be $s$ and $t$, respectively; then the maximal number of edges is $st$. By AM-GM, $st\le (\frac{s+t}{2}{)}^2=50^2=2500$. If the volumes are in the order $51,52,...,100,1,2,...,50$, exactly 2500 reversed pairs arise indeed.