XIX Asian Pacific Mathematics Olympiad

The answer is $(n-1)(n-2)/2$.

Let's call a set of $n$ disks satisfying the given conditions an $n$-configuration. For an $n$-configuration $\mathcal{C}=\{C_1,\dots ,C_n\}$, let $S_{\mathcal{C}}=\{(i,j)\mid C_i$ properly contains $C_j\}$. So, the score of an $n$-configuration $\mathcal{C}$ is $|S_{\mathcal{C}}|$.

We'll show that (i) there is an $n$-configuration $\mathcal{C}$ for which $|S_{\mathcal{C}}|=(n-1)(n-2)/2$, and that (ii) $|S_{\mathcal{C}}|\le (n-1)(n-2)/2$ for any $n$-configuration $\mathcal{C}$.

Let $C_1$ be any disk. Then for $i=2,\dots ,n-1$, take $C_i$ inside $C_{i-1}$ so that the circumference of $C_i$ contains the center of $C_{i-1}$. Finally, let $C_n$ be a disk whose center is on the circumference of $C_1$ and whose circumference contains the center of $C_{n-1}$. This gives $S_{\mathcal{C}}=\{(i,j)\mid 1\le i<j\le n-1\}$ of size $(n-1)(n-2)/2$, which proves (i).

For any $n$-configuration $\mathcal{C}$, $S_{\mathcal{C}}$ must satisfy the following properties: (1) $(i,i)\notin S_{\mathcal{C}}$, (2) $(i+1,i)\notin S_{\mathcal{C}},(1,n)\notin S_{\mathcal{C}}$, (3) if $(i,j),(j,k)\in S_{\mathcal{C}}$, then $(i,k)\in S_{\mathcal{C}}$, (4) if $(i,j)\in S_{\mathcal{C}}$, then $(j,i)\notin S_{\mathcal{C}}$.

Now we show that a set $G$ of ordered pairs of integers between $1$ and $n$, satisfying the conditions (1)~(4), can have no more than $(n-1)(n-2)/2$ elements. Suppose that there exists a set $G$ that satisfies the conditions (1)~(4), and has more than $(n-1)(n-2)/2$ elements. Let $n$ be the least positive integer with which there exists such a set $G$. Note that $G$ must have $(i,i+1)$ for some $1\le i\le n$ or $(n,1)$, since otherwise $G$ can have at most $$\left(\genfrac{}{}{0ex}{}{n}{2}\right)-n=\frac{n(n-3)}{2}<\frac{(n-1)(n-2)}{2}$$ elements. Without loss of generality we may assume that $(n,1)\in G$. Then $(1,n-1)\notin G$, since otherwise the condition (3) yields $(n,n-1)\in G$ contradicting the condition (2). Now let $G^{\prime }=\{(i,j)\in G\mid 1\le i,j\le n-1\}$, then $G^{\prime }$ satisfies the conditions (1)~(4), with $n-1$.

We now claim that $|G-G^{\prime }|\le n-2$: Suppose that $|G-G^{\prime }|>n-2$, then $|G-G^{\prime }|=n-1$ and hence for each $1\le i\le n-1$, either $(i,n)$ or $(n,i)$ must be in $G$. We already know that $(n,1)\in G$ and $(n-1,n)\in G$ (because $(n,n-1)\notin G$) and this implies that $(n,n-2)\notin G$ and $(n-2,n)\in G$. If we keep doing this process, we obtain $(1,n)\in G$, which is a contradiction.

Since $|G-G^{\prime }|\le n-2$, we obtain $$|G^{\prime }|\ge \frac{(n-1)(n-2)}{2}-(n-2)=\frac{(n-2)(n-3)}{2}$$ This, however, contradicts the minimality of $n$, and hence proves (ii).