11. Giovanni draws a regular 9-gon with a pencil and connects each of its vertices to the center, drawing a total of 18 segments and thus obtaining nine triangles. He then traces some of the drawn segments with a pen, ensuring that each of the nine triangles has exactly one side traced with a pen. In how many ways can Giovanni choose the set of segments to trace? (Note: two sets of segments that can be obtained from each other by rotation or reflection are to be considered distinct.)
(A) 49
(B) 65
(C) 74
(D) 76
(E) 85
## 11. The answer is (D).

## FIRST SOLUTION

We will call the 9 segments that admit the center of the nonagon as a vertex "radii".

First, note that choosing the set of segments to trace over with a pen is equivalent to choosing a subset of the 9 radii that does not contain two consecutive radii: naturally, Giovanni cannot trace over two consecutive radii; on the other hand, once the radii to be traced are chosen, each side of the nonagon will be traced if and only if neither of the two radii sharing a vertex with the side in question has been traced.

Let's count the possible configurations based on the number of radii traced.

0 - one configuration;

1 - 9 choices for the radius to trace;

2 - once a radius is chosen, the second radius can be any of the remaining ones, except for the two neighbors of the initial radius; the number of configurations is thus half the number of ordered pairs obtained in this way $\left(\frac{1}{2} 9 \cdot 6\right)$, which is 27;

3 - the total number of possible choices for a subset of three radii, ignoring the restriction, is $\frac{1}{6} 9 \cdot 8 \cdot 7$, which is 84; among these, exactly 9 are choices of three consecutive radii; it remains to determine how many configurations consist of two consecutive radii and a third radius not consecutive to either of the other two. The pair of consecutive radii can be chosen in 9 ways; at that point, there are 5 choices for the 'isolated' radius. It follows that there are $84-9-45=30$ acceptable configurations;

4 - in this case, there is exactly one pair of chosen radii separated by a pair of consecutive unchosen radii (outside this interval, chosen and unchosen radii alternate); the configurations are as many as the pairs of consecutive radii, which is 9.

In total, we count $1+9+27+30+9=76$ possible configurations.

## SECOND SOLUTION

Consider a variant of the original problem: Giovanni draws a regular $n$-gon with a pencil, then draws $n$ segments connecting the vertices to the center; thus forming $n$ triangles. Unlike the original problem, suppose that Giovanni chooses one of the segments that have the center as a vertex and decides not to trace it with a pen: we will call this special segment. Let $f(n)$ be the number of ways Giovanni has to choose a subset of the other $2n-1$ segments to trace, always in such a way that each of the $n$ triangles ends up with exactly one segment traced with a pen.

Notice that, if $n>4, f(n)=f(n-1)+f(n-2)$. Consider the triangle that lies to the right of the special segment; it must have a segment traced with a pen, which can be a side of the $n$-gon or a segment that has the center as a vertex. If Giovanni traces the side of the $n$-gon with a pen, he has $f(n-1)$ ways to choose the other segments to trace: he can remove the traced side and identify the other two sides of the triangle in question, making them the special segment of a new configuration with $n-1$ triangles. If Giovanni traces the side of the triangle adjacent to the center of the $n$-gon, then he cannot trace any other side of the triangle to its right; he can then remove two triangles, as in the previous step, to obtain a configuration with $n-2$ triangles and a special segment.

We now show that the answer to the original problem is $f(7)+f(9)$. Choose any of the radii of the nonagon. If this is not traced, then we can consider it as a special segment: there are $f(9)$ ways to choose the segments to trace; otherwise, we can remove the two triangles adjacent to it, identifying the two radii between which they are contained: the identified radii cannot be traced, and are thus a special segment for the configuration with 7 triangles.

It is easy to verify that $f(3)=3$ and $f(4)=5$ by enumerating the configurations; consequently, $f(5)=8 ; f(6)=13 ; f(7)=21 ; f(8)=34 ; f(9)=55$. The answer is $f(7)+f(9)$, which is 76.