A diagonal of a regular 2006-gon is called odd if its endpoints divide the boundary into two parts, each composed of an odd number of sides. Sides are also regarded as odd diagonals. Suppose the 2006-gon has been dissected into triangles by 2003 nonintersecting diagonals. Find the maximum possible number of isosceles triangles with two odd sides. (Serbia)
Call an isosceles triangle odd if it has two odd sides. Suppose we are given a dissection as in the problem statement. A triangle in the dissection which is odd and isosceles will be called iso-odd for brevity. Lemma. Let \( AB \) be one of the dissecting diagonals and let \( \mathcal{L} \) be the shorter part of the boundary of the 2006-gon with endpoints \( A, B \). Suppose that \( \mathcal{L} \) consists of \( n \) segments. Then the number of iso-odd triangles with vertices on \( \mathcal{L} \) does not exceed \( n / 2 \). Proof. This is obvious for \( n=2 \). Take \( n \) with \( 2 < n \leq 1003 \) and assume the claim to be true for every \( \mathcal{L} \) of length less than \( n \). Let now \( \mathcal{L} \) (endpoints \( A, B \)) consist of \( n \) segments. Let \( PQ \) be the longest diagonal which is a side of an iso-odd triangle \( PQS \) with all vertices on \( \mathcal{L} \) (if there is no such triangle, there is nothing to prove). Every triangle whose vertices lie on \( \mathcal{L} \) is obtuse or right-angled; thus \( S \) is the summit of \( PQS \). We may assume that the five points \( A, P, S, Q, B \) lie on \( \mathcal{L} \) in this order and partition \( \mathcal{L} \) into four pieces \( \mathcal{L}_{AP}, \mathcal{L}_{PS}, \mathcal{L}_{SQ}, \mathcal{L}_{QB} \) (the outer ones possibly reducing to a point).

By the definition of \( PQ \), an iso-odd triangle cannot have vertices on both \( \mathcal{L}_{AP} \) and \( \mathcal{L}_{QB} \). Therefore every iso-odd triangle within \( \mathcal{L} \) has all its vertices on just one of the four pieces. Applying to each of these pieces the induction hypothesis and adding the four inequalities we get that the number of iso-odd triangles within \( \mathcal{L} \) other than \( PQS \) does not exceed \( n / 2 \). And since each of \( \mathcal{L}_{PS}, \mathcal{L}_{SQ} \) consists of an odd number of sides, the inequalities for these two pieces are actually strict, leaving a \( 1 / 2 + 1 / 2 \) in excess. Hence the triangle \( PQS \) is also covered by the estimate \( n / 2 \). This concludes the induction step and proves the lemma.

The remaining part of the solution in fact repeats the argument from the above proof. Consider the longest dissecting diagonal \( XY \). Let \( \mathcal{L}_{XY} \) be the shorter of the two parts of the boundary with endpoints \( X, Y \) and let \( XYZ \) be the triangle in the dissection with vertex \( Z \) not on \( \mathcal{L}_{XY} \). Notice that \( XYZ \) is acute or right-angled, otherwise one of the segments \( XZ, YZ \) would be longer than \( XY \). Denoting by \( \mathcal{L}_{XZ}, \mathcal{L}_{YZ} \) the two pieces defined by \( Z \) and applying the lemma to each of \( \mathcal{L}_{XY}, \mathcal{L}_{XZ}, \mathcal{L}_{YZ} \) we infer that there are no more than 2006/2 iso-odd triangles in all, unless \( XYZ \) is one of them. But in that case \( XZ \) and \( YZ \) are odd diagonals and the corresponding inequalities are strict. This shows that also in this case the total number of iso-odd triangles in the dissection, including \( XYZ \), is not greater than 1003.

This bound can be achieved. For this to happen, it just suffices to select a vertex of the 2006-gon and draw a broken line joining every second vertex, starting from the selected one. Since 2006 is even, the line closes. This already gives us the required 1003 iso-odd triangles. Then we can complete the triangulation in an arbitrary fashion.