Problem

Source: 2021 Estonia TST 1.1

Tags: combinatorics



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