IMO 2006 · 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.

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{1003} \]

Solution

Call an isosceles triangle having two good sides a counted triangle. All references to good sides below are with respect to the original polygon \(P\).

A chord is good precisely when either boundary arc between its endpoints contains an odd number of sides. Also, if \(R\) is the circumradius, a chord spanning \(r\) consecutive sides has length \[ 2R\sin\frac{\pi r}{2006}. \] Consequently, this length is strictly increasing for \(1\le r\le1003\).

Claim. Let \(V_0,V_1,\ldots,V_m\) be consecutive vertices of \(P\), where \(1\le m\le1003\). Any triangulation of the region bounded by this boundary arc and the chord \(V_0V_m\) contains at most \[ \left\lfloor\frac m2\right\rfloor \] counted triangles. For \(m=1\), this region is empty.

We prove the claim by induction on \(m\). The case \(m=1\) is immediate. For \(m\ge2\), the triangle incident to the chord \(V_0V_m\) has third vertex \(V_k\), where \(1\le k<m\). Its other two sides span \(k\) and \(m-k\) polygon sides. Both are strictly shorter than \(V_0V_m\).

Thus, if this triangle is isosceles, its equal sides must be \(V_0V_k\) and \(V_kV_m\), and strict monotonicity of chord lengths gives \[ k=m-k. \] Moreover, if it is counted, these equal sides must both be good: otherwise both are bad, leaving at most one good side. Hence \(k=m-k\) is odd.

The remaining triangles belong to the two smaller regions with arc lengths \(k\) and \(m-k\). By induction, their total number of counted triangles is at most \[ \left\lfloor\frac k2\right\rfloor+ \left\lfloor\frac{m-k}{2}\right\rfloor. \] If \(V_0V_kV_m\) is not counted, this is at most \(\lfloor m/2\rfloor\). If it is counted, both \(k\) and \(m-k\) are odd, so including this triangle gives at most \[ \frac{k-1}{2}+\frac{m-k-1}{2}+1 =\frac m2. \] This proves the claim.

Now let \(O\) be the centre of \(P\), and choose a triangle \(T\) of the dissection whose closed region contains \(O\). This includes the possibility that \(O\) lies on a diagonal.

The vertices of \(T\) divide the boundary of \(P\) into three arcs containing \(a,b,c\) sides, respectively, where \[ a+b+c=2006. \] Each of \(a,b,c\) is at most \(1003\). Indeed, if one were greater than \(1003\), the complementary arc, containing all three vertices of \(T\), would be shorter than a semicircle. Those vertices would then lie in an open half-plane bounded by a line through \(O\), contradicting \(O\in T\).

The three sides of \(T\) separate the rest of \(P\) into regions to which the claim applies. Therefore, writing \(\varepsilon=1\) if \(T\) is counted and \(\varepsilon=0\) otherwise, the total number of counted triangles is at most \[ \left\lfloor\frac a2\right\rfloor+ \left\lfloor\frac b2\right\rfloor+ \left\lfloor\frac c2\right\rfloor+\varepsilon. \]

If \(\varepsilon=0\), this is at most \(2006/2=1003\). If \(\varepsilon=1\), two sides of \(T\) are good, so two of \(a,b,c\) are odd. Since their sum is even, the third is even. The bound is therefore \[ \frac{a+b+c-2}{2}+1=1003. \] Thus every permitted dissection has at most \(1003\) counted triangles.

To attain this bound, label the vertices \(A_0,A_1,\ldots,A_{2005}\) cyclically. Draw the \(1003\) diagonals \[ A_{2i}A_{2i+2}\qquad(0\le i\le1002), \] with indices taken modulo \(2006\). These diagonals do not cross and cut off the \(1003\) triangles \[ A_{2i}A_{2i+1}A_{2i+2}. \] Each has two equal sides that are sides of \(P\), so each is counted.

The remaining region is the convex \(1003\)-gon formed by the even-indexed vertices. Triangulate it, for example by drawing a fan from one vertex, using \(1000\) further diagonals. Altogether there are \(1003+1000=2003\) noncrossing diagonals. Every chord between even-indexed vertices is bad, so the central region contributes no counted triangles.

Hence the maximum is \(\boxed{1003}\).

The solution was checked against the official IMO shortlist solutions.