Juku has the first $100$ volumes of the Harrie Totter book series at his home. For every$ i$ and $j$, where $1 \le i < j \le 100$, call the pair $(i, j)$ reversed if volume No. $j$ is before volume No, $i$ on Juku’s shelf. Juku wants to arrange all volumes of the series to one row on his shelf in such a way that there does not exist numbers $i, j, k$, where $1 \le i < j < k \le 100$, such that pairs $(i, j)$ and $(j, k)$ are both reversed. Find the largest number of reversed pairs that can occur under this condition
Problem
Source: 2021 Estonia TST 1.1
Tags: combinatorics
05.01.2022 04:17
Replacing the number $100$ by $n$, the answer is $\left\lfloor n^2/4\right\rfloor$. In fact, consider an arrangement that satisfies the required condition -- i.e., for which there are no three integers $i, j, k$ satisfying $1 \leq i < j < k \leq n$ such that both pairs $\left(i,j\right)$ and $\left(j,k\right)$ are reversed. We say that a number $p \in \left\{1,2,\ldots,n\right\}$ is leftish if there exists an integer $q > p$ such that the pair $\left(p,q\right)$ is reversed; otherwise, we say that $p$ is rightish. Assume that there are $m$ leftish numbers and therefore $n-m$ rightish numbers. If a pair $\left(p, q\right)$ is reversed, then $p$ is leftish (obviously) and $q$ is rightish (because if $q$ was leftish, then there would be an $r$ such that the pair $\left(q,r\right)$ is reversed, and this would contradict our "no three integers $i, j, k$" condition with $i = p$, $j = q$ and $k = r$). This leaves $m$ options for $p$ and $n-m$ options for $q$. Thus, the total number of reversed pairs is $\leq m \left(n-m\right) \leq \left\lfloor n^2/4 \right\rfloor$ (the latter inequality is well-known and follows, e.g., from AM-GM). To see that $\left\lfloor n^2/4 \right\rfloor$ is indeed possible, arrange the books in the order $m+1, m+2, \ldots, n, 1, 2, \ldots, m$, where $m = \left\lfloor n / 2 \right\rfloor$, and observe that $\left\lfloor n / 2 \right\rfloor \left(n - \left\lfloor n / 2 \right\rfloor\right) = \left\lfloor n^2 / 4 \right\rfloor$.