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 3 of 6: Use transitivity

Previous step Next step

C_i\subsetneq C_j,\ C_j\subsetneq C_k\Longrightarrow C_i\subsetneq C_k

Detailed analysis

Suppose a set of ordered pairs satisfying the preceding rules had more than $\frac{(n-1)(n-2)}2$ elements, and choose the least such $n$ . If no forward pair $(i,i+1)$ and no wrap pair $(n,1)$ belonged to it, there would be at most $\frac{n(n-3)}2$ , which is smaller. Thus one forbidden-direction boundary pair occurs; by cyclic relabeling assume $(n,1)$ occurs.