Problem 2

Let

P

be a regular

2006

-gon. A diagonal of

P

is called good if its endpoints divide the boundary of

P

into two parts, each composed of an odd number of sides of

P

. The sides of

P

are also called good. Suppose

P

has been dissected into triangles by

2003

diagonals, no two of which have a common point in the interior of

P

. Find the maximum number of isosceles triangles having two good sides that could appear in such a configuration.

Step 4 of 5: Remove one non-special leaf for each good diagonal

Previous step Next step

In plain words

A good diagonal has a leaf triangle on each side after deletion. Since two special triangles cannot share a good side, one can choose a distinct non-special leaf for each deleted diagonal.

\#\{\text{special leaves of }F\}\le(1003+k)-k=1003

Detailed analysis

For each deleted good-diagonal edge, inspect the two endpoint leaves in the resulting components. At most one endpoint can be special, otherwise two special triangles would share that good diagonal. Processing deleted edges from the outside of the forest inward, always choose the endpoint not already chosen; the tree structure guarantees these choices are distinct (the standard leaf-pairing argument). Thus at least $k$ of the $1003+k$ leaves are non-special, and the number of special triangles is at most $1003$ .