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 2 of 6: Record the forbidden successor pairs

Previous step Next step

(i+1,i)\notin S_C\ (1\le i<n),\qquad(1,n)\notin S_C

Detailed analysis

The center of $C_i$ is on the circumference of $C_{i+1}$ , so $C_{i+1}$ cannot properly contain $C_i$ . Likewise the center of $C_n$ is on $C_1$ , so $(1,n)\notin S_C$ . These are the successor pairs forbidden by the configuration.