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 1 of 6: Encode containments as ordered pairs

Previous step Next step

\operatorname{score}(C)=|S_C|,\qquad S_C=\{(i,j):C_i\text{ properly contains }C_j\}

Detailed analysis

Let $S_C$ be the set of ordered pairs $(i,j)$ for which $C_i$ properly contains $C_j$ . Proper containment is irreflexive and transitive, and two disks cannot properly contain one another in both directions.