Problem 1978

First Solution: We start with the following lemma.
Lemma Let $P_iP_j$ is a diagonal used in $\mathcal{T}$, and $\widehat{P_iP_j}$ is non-major and contains $n$ segments of $\mathcal{P}$, then there are at most $\lfloor \frac{n}{2} \rfloor$ good triangles with vertices on $\widehat{P_iP_j}$. More precise there are at most
$$\left\{ \begin{array}{ll} \lfloor \frac{j-i}{2} \rfloor, & \text{if } i < j \\ \lfloor \frac{j-i+2006}{2} \rfloor, & \text{if } i > j \end{array} \right.$$
good triangles with vertices on $\widehat{P_iP_j}$
*Proof:* Without loss of generality, we may assume that $i < j$. We induct on $n$.
The bases cases for $n=1$ and $n=2$ are trivial. Assume the statement is true for $n$ with $n \le k$ and $2 \le k < 1003$. We consider the case $n=k+1$.
Let $P_iP_aP_j$ be a triangle in $\mathcal{T}$ with $P$ on $\widehat{P_iP_j}$. (Note that $P_i, P_a$, and $P_j$ lie on non-major arc $\widehat{P_iP_j}$ on $\omega$ in clockwise order. By the induction hypothesis, there are at most
$$\lfloor \frac{a-i}{2} \rfloor \le \frac{a-i}{2}$$
good triangles with vertices on $\widehat{P_iP_a}$. Similar result holds for $\widehat{P_aP_j}$.
Because $P_iP_aP_j$ is a triangle in $\mathcal{T}$, we conclude that if a good triangles has its vertices on $\widehat{P_iP_j}$ then either it is $P_iP_aP_j$, or all its vertices are on exactly one of $\widehat{P_iP_a}$ or $\widehat{P_aP_j}$. We can now apply the induction hypothesis $\widehat{P_iP_a}$ and $\widehat{P_aP_j}$. We conclude that there are at most
$$1 + \frac{a-i}{2} + \frac{j-a}{2} = \frac{j-i}{2} + 1 \qquad (\ddag)$$
good triangles with vertices on $\widehat{P_iP_j}$.
To finish our proof, we need to reduce the value of the right-hand side of (‡) by 1. We consider the following two cases.
In the first case, we assume that $P_iP_aP_j$ is not good. The summand 1 on the right-hand of (†) should be taken out, and we are done.
In the second case, we assume that $P_iP_aP_j$ is good. Since $\widehat{P_iP_j}$ is non-major, $P_iP_j > P_iP_a$ and $P_iP_j > P_aP_j$. We must have $P_iP_a$ and $P_aP_j$ must be the two equal good sides, and both must be the good sides. Hence both $a-i$ and $j-a$ are odd, and so we can improve (†) to
$$\left\lfloor \frac{a-i}{2} \right\rfloor \le \frac{a-i}{2} - \frac{1}{2},$$
and similar result hold for $\widehat{P_aP_j}$. Then (‡) can be improved to
$$1 + \frac{a-i}{2} - \frac{1}{2} + \frac{j-a}{2} - \frac{1}{2} = \frac{j-i}{2},$$
completing our induction.
■
Since $\widehat{P_iP_j}$ is non-major, $P_aP_b < P_aP_c$ and $P_bP_c < P_aP_c$. Since $P_aP_bP_c$ is good, we must have $P_aP_b$ and $P_bP_c$ be the good segments (with equal lengths). Thus $b-a$ and $c-b$ are both odd. By the induction hypothesis, there are at most
$$\left\lfloor \frac{b-a}{2} \right\rfloor = \frac{b-a}{2} - \frac{1}{2}$$
good triangles with vertices on $\widehat{P_aP_b}$. Similar result holds for $\widehat{P_bP_c}$.
Now we prove our main result. Let $P_iP_k$ be the longest diagonal used in $\mathcal{T}$. Let $P_iP_jP_k$ be a non-obtuse triangle in $\mathcal{T}$. Without loss of generality, we may assume that $i < j < k$. Since $P_iP_jP_k$ is non-obtuse, $\widehat{P_iP_j}$, $\widehat{P_jP_k}$, and $\widehat{P_kP_i}$ are all non-major. By the lemma, there are at most
$$\left\lfloor \frac{j-i}{2} \right\rfloor + \left\lfloor \frac{k-j}{2} \right\rfloor + \left\lfloor \frac{i-k+2006}{2} \right\rfloor \\ \le \frac{j-i}{2} + \frac{k-j}{2} + \frac{i-k+2006}{2} = 1003$$
good triangles besides $P_iP_jP_k$.
If $P_iP_jP_k$ is not good, we are done. If it is, then exactly two of $j-i$, $k-j$, and $i-k$ are odd, and so (*) is strict inequality. We still have at most $1002+1=1003$ good triangles in this case, completing our proof.

Second Solution: Let $P_iP_jP_k$ ($i < j < k$) be a good triangle, with $P_iP_j$ and $P_jP_k$ being good segments. This means that there are an odd number of sides of $\mathcal{P}$ between $P_i$ and $P_j$ and also between $P_j$ and $P_k$. We say $\widehat{P_iP_j}$ and $\widehat{P_jP_k}$ belong to triangle ABC.
At least one side in each of these groups does not belong to any other good triangle. This is so because any odd triangle whose vertices are among the points between $P_i$ and $P_j$ 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 good triangle in $\widehat{P_iP_j}$ must therefore leave at least one side that belongs to no other good triangle. Same argument applies to $\widehat{P_jP_k}$. Let us assign these two sides (one in $\widehat{P_iP_j}$ and one in $\widehat{P_jP_k}$) to triangle $P_iP_jP_k$.
To each good triangle we have thus assigned a pair of sides, with no two good triangles sharing an assigned side. It follows that at most 1003 good triangles can appear in the triangulation; that is, $M \le 1003$.