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 4 of 6: Delete the last index

Previous step Next step

G'=G\cap\{1,\ldots,n-1\}^2,\qquad |G\setminus G'|\le n-2

Detailed analysis

Because $(n,1)\in G$ , transitivity forbids $(1,n-1)$ . If more than $n-2$ pairs involved index $n$ , then all $n-1$ possible such boundary pairs would occur; starting from $(n,1)$ and using transitivity would force $(1,n)$ , contradicting the wrap prohibition. Hence $|G\setminus G'|\le n-2$ .