
08.2. Assume that $n \geq 3$ people with different names sit around a round table. We call any unordered pair of them, say $M$ and $N$, dominating, if

(i) $M$ and $N$ do not sit on adjacent seats, and

(ii) on one (or both) of the arcs connecting $M$ and $N$ along the table edge, all people have names that come alphabetically after the names of $M$ and $N$.

Determine the minimal number of dominating pairs.


Solution. We will show by induction that the number of dominating pairs (hence also the minimal number of dominating pairs) is $n-3$ for $n \geq 3$. If $n=3$, all pairs of people sit on adjacent seats, so there are no dominating pairs. Assume that the number of dominating pairs is $n-3$ for some $n>3$. If there are $n+1$ people around the table, let the person whose name is alphabetically last leave the table. The two people sitting next to that person, who formed a dominating pair, no longer do. On the other hand, any other dominating pair remains a dominating pair in the new configuration of $n$ people, and any dominating pair in the new configuration was also a dominating pair in the old. The number of dominating pairs in the new configuration is $n-3$, so the number in the old was $(n+1)-3$.
