Problem 3

Consider

n

disks

C_1,C_2,\ldots,C_n

in the plane such that for each

1\le i<n

, the center of

C_i

lies on the circumference of

C_{i+1}

, and the center of

C_n

lies on the circumference of

C_1

. Define the score to be the number of pairs

(i,j)

for which

C_i

properly contains

C_j

. Determine the maximum possible score.

Step 5 of 6: Contradict minimality

Previous step Next step

|G|\le\frac{(n-2)(n-3)}2+(n-2)=\frac{(n-1)(n-2)}2

Detailed analysis

The restricted set $G'$ obeys the same four rules with $n-1$ indices. By minimality, $|G'|\le\frac{(n-2)(n-3)}2$ . Together with $|G\setminus G'|\le n-2$ , this gives $|G|\le\frac{(n-1)(n-2)}2$ , a contradiction. Thus the bound holds for every configuration.