21. Numbers $1,2, \ldots, 2010$ are placed on the circumference of a circle in some order. The numbers $i$ and $j$, where $i \neq j$ and $i, j \in\{1,2, \ldots, 2010\}$ form a friendly pair if
(i) $i$ and $j$ are not neighbours to each other, and
(ii) on one or both of the arcs connecting $i$ and $j$ along the circle, all numbers in between them are greater than both $i$ and $j$.
Determine the minimal number of friendly pairs.
21. Answer: 2007
Consider $n$ distinct numbers where $n \geq 3$. We shall show by induction that the number of friendly pairs is always $n-3$ for $n \geq 3$. Hence the minimal number of friendly pairs is also $n-3$.
If $n=3$, then there are no friendly pairs as each number is adjacent to the other two. Thus the number of friendly pairs is 0 . Assume that the number of friendly pairs for any arrangement of $n$ distinct numbers on the circle is $n-3$ for some $n \geq 3$. Consider $n+1$ distinct numbers on the circle. Let $m$ be the largest number. Now consider the $n$ numbers on circle after deleting $m$. The two numbers adjacent to $m$ which originally form a friendly pair do not form a friendly pair anymore. Any other friendly pair remains a friendly pair when $m$ is deleted. On the other hand, any friendly pair after $m$ is deleted was originally a friendly pair. By induction hypothesis, there are $n-3$ friendly pairs after $m$ is deleted. There fore, there are $(n+1)-3$ friendly pairs originally.