6. a regular 2008-vertical is somehow divided into many triangles with 2005 non-intersecting diagonals. Determine the smallest possible number of non-isosceles triangles that can occur in such a decomposition.

## 1st solution
We call an isosceles triangle good and a non-isosceles triangle bad. For a natural number $n$, let $n^{(2)}$ denote the number of ones in the binary representation of $n$. We will show more generally that in every triangulation of a regular $n$ vertex there are at least $n^{(2)}-2$ bad triangles. To do this, first consider the following:

Lemma 1: For any natural numbers $a, b$, $a^{(2)}+b^{(2)} \geq(a+b)^{(2)}$ with equality if and only if no carry occurs when adding $a+b$ in the binary system.

The main step consists of the following result:

Lemma 2: In every triangulation of a segment of the n-gon over an arc of $k \leq \frac{n}{2}$ sides at least $k^{(2)}-1$ bad triangles occur.

Proof. We use induction according to $k \geq 1$. For the degenerate case $k=1$ the assertion is trivial, we therefore assume $k>1$. The limiting diagonal of this segment is a side of a triangle $\Delta$ in the triangulation. The third vertex of $\Delta$ divides the arc into two partial arcs of lengths $a, b$ with $a+b=k$. According to the induction assumption, at least $a^{(2)}-1$ or $b^{(2)}-1$ bad triangles occur in the triangulation of these arcs. We distinguish between two cases:

(i) $\Delta$ is bad. Then a total of at least $\left(a^{(2)}-1\right)+\left(b^{(2)}-1\right)+1 \geq$ $(a+b)^{(2)}-1=k^{(2)}-1$ bad triangles occur.

(ii) $\Delta$ is good. Because of $k \leq \frac{n}{2}$ then $a=b=\frac{k}{2}$ must be. The number of bad triangles is therefore again at least $\left(a^{(2)}-1\right)+\left(b^{(2)}-1\right)=2\left(k^{(2)}-1\right) \geq k^{(2)}-1$.

We now come to the actual proof and again distinguish between two cases.

(a) One of the diagonals goes through the center of the $n$ vertex. In this case, $n=2 k$ is even and according to Lemma 2, the number of bad triangles is at least $2\left(k^{(2)}-1\right)=2\left(n^{(2)}-1\right)>n^{(2)}-2$.

(b) The center lies in the interior of a triangle $\Delta$ whose vertices divide the edge of the $n$-gon into three arcs of lengths $a, b, c$ with $a+b+c$. If $\Delta$ is bad, then the number of bad triangles is at least $\left(a^{(2)}-1\right)+\left(b^{(2)}-1\right)+\left(c^{(2)}-\right.$ 1) $+1 \geq(a+b+c)^{(2)}-2=n^{(2)}-2$. However, if $\Delta$ is good, then two of the three numbers $a, b, c$ are equal, oBdA let $a=b$. In this case, the number of bad triangles is at least $2 a^{(2)}+c^{(2)}-3 \geq\left((2 a)^{(2)}+1\right)+c^{(2)}-3 \geq n^{(2)}-2$.

Because $2008^{(2)}=7$, every triangulation contains at least 5 bad triangles. Finally, we construct another example with 5 bad triangles. Consider that every segment over an arc whose length is a power of two can be triangulated without bad triangles. If you do this for consecutive sectors of lengths 1024, 512, 256, 128, 64, 16 and 8, then the remaining 7-corner can of course be triangulated with 5 (bad) triangles. This shows everything.

## 2nd solution

We give a second argument that at least $n^{(2)}-2$ bad triangles exist.

Lemma 3 Let $k \leq \frac{n}{2}$ be a natural number.

(a) If a segment of the n-gon can be triangulated over an arc of $k$ sides without bad triangles, then $k$ is a power of two.

(b) If a segment of the n-corner can be triangulated over an arc of $k$ sides with s bad triangles, then so can every segment over an arc of $2 k$ sides.

Proof. For (a) we use induction on $k$, the case $k=1$ is trivial. The bounding diagonal of this segment is a side of an isosceles triangle $\Delta$ in the triangulation, and because of $k \leq \frac{n}{2}$ it must be the base of $\Delta$. The third vertex of $\Delta$ therefore divides the arc into two equally sized partial arcs whose length is a power of two according to the induction condition. Therefore, $k$ is also a power of two. For (b), "stretch" the sector together with its triangulation by a factor of 2 and add small isosceles triangles to the edge $k$.

We now consider a triangulation of the n-corner with the smallest possible number of bad triangles. If there is no bad triangle at all, then we choose a triangle that contains the center of the $n$-triangle in the interior or on the edge and apply (a) to the three segments that are bounded by its sides. The lengths of the corresponding arcs are therefore powers of two and two of them are equal. From this follows $n^{(2)} \leq 2$. We now assume that a bad triangle exists and denote the convex hull of all bad triangles by $H$, this is a convex polygon whose vertices are also vertices of the $n$ vertex. Let $\Delta$ be any good triangle. The two sides of equal size delimit segments of length $<\frac{n}{2}$, and we claim that there is no bad triangle in these segments. According to (b), the union $S$ of the two segments and $\Delta$ can be triangulated with the same number of bad triangles as one of the two segments. It therefore follows from the minimality that the other segment cannot contain any bad triangles. This shows that $H$ and $S$ have no common inner point and, in particular, that $\Delta$ is not contained in $H$. Since $\Delta$ was arbitrary, $H$ consists exclusively of bad triangles. The sides of $H$ therefore delimit segments that consist entirely of good triangles, whose length is therefore a power of two according to (a). The sum of these lengths is equal to $n$ and therefore $H$ has at least $n^{(2)}$ sides and the triangulation has at least $n^{(2)}-2$ bad triangles.

Note: The smallest possible number of bad triangles is actually $n^{(2)}-2$ (or 0 if $n$ is a power of two). The above construction for $n=2008$ immediately applies to the general case. The second solution also gives very precise information about the position of the bad triangles in an optimal triangulation.