IMO 2006 Shortlisted Problems

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 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\le 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 $PSQ$ 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.

---

Alternative solution.

Let the terms odd triangle and iso-odd triangle have the same meaning as in the first solution.

Let $ABC$ be an iso-odd triangle, with $AB$ and $BC$ odd sides. This means that there are an odd number of sides of the 2006-gon between $A$ and $B$ and also between $B$ and $C$. We say that these sides belong to the iso-odd triangle $ABC$.

At least one side in each of these groups does not belong to any other iso-odd triangle. This is so because any odd triangle whose vertices are among the points between $A$ and $B$ has two sides of equal length and therefore has an even number of sides belonging to it in total. Eliminating all sides belonging to any other iso-odd triangle in this area must therefore leave one side that belongs to no other iso-odd triangle. Let us assign these two sides (one in each group) to the triangle $ABC$.

To each iso-odd triangle we have thus assigned a pair of sides, with no two triangles sharing an assigned side. It follows that at most $1003$ iso-odd triangles can appear in the dissection.

This value can be attained, as shows the example from the first solution.