What restrictions are there to subtract from $(n-3)^2$?

Well no two diagonals of the same colour are allowed to intersect inside the polygon.

But... if, for example, your n-3 diagonals all come from the same vertex for each colour. Then they won't intersect again. Then you have $(n-3)^2$ intersections.

Btw, I'm assuming epitomy meant "$n-3$ are colored black and $n-3$ are colored red"... vulgarfraction wrote: But... if, for example, your n-3 diagonals all come from the same vertex for each colour. Then they won't intersect again. Then you have $(n-3)^2$ intersections. Not necessarily, actually. So let's say the you have all possible black diagonals coming from one vertex. Consider one of those diagonals. Let's say it stems from vertex $A$ and goes to vertex $B$. If some red diagonal stems from vertex $C$ and goes to vertex $B$, then the two do not intersect. Nevertheless, I must say a clever idea...

exactly, they have to meet strictly inside the polygon, so meeting at a vertex is not good enough. note the scenario where you have 2 vertices spanning all the $n-3$ edges is not optimal for most cases .. eg try $n=6,7$. and yes i did have a small typo which i have now corrected.

any ideas people on this difficult problem? i hear its from the shortlist 2005 also ...

My solution: the intersection points are at most $\frac{3n^2 - 18 n + 27 + p}{4}$, where $p$ depends on the parity of $n$ and is $0$, if $n$ is odd, $1$ otherwise. I have not yet written it down properly, but the main idea is to prove the following: Claim: The number of blue diagonals with at least $\scriptstyle n-3$ intersection points is at most $\scriptstyle 1$; the number of blue diagonals with at least $\scriptstyle n-4$ intersection points is at most $\scriptstyle 3$; the number of blue diagonals with at least $\scriptstyle n-5$ intersection points is at most $\scriptstyle 5$; ... the number of blue diagonals with at least $\scriptstyle n-3-k$ intersection points is at most $\scriptstyle 1+2k$. This gives you an upper bound that turns out to be optimal: is it possible infact to draw diagonals in such a way that the maximum is attained. The construction is not so obvious, so have fun in finding it! The rest is just counting how many intersection points are there and writing the ugly polynomials of the solution. M.

Answer is $\frac{3}{4}*(n-3)^2+p$, where $p=1/4$ if $n$ is even, and $p=0$ if $n$ is odd. The example is easy. The proof that it can't be more is much harder, i don't have time to write it now.

Please a solution

Consider a chord $XY$, and suppose $a$ points are on one side of it, and $b$ points are on the other side (so in particular $a+b=n-2$). Define the length $\ell(XY)$ to be $\min\{a,b\}$. We have the following main lemma. Lemma: Suppose we have two non-intersecting chords $AB$ and $CD$ of lengths $x$ and $y$. For any triangulation of the $n$-gon, the number of interior intersections with these two chords is bounded above by $x+y+n-4$. Proof: Starting form $A$, let the points be \[A,P_1,\ldots,P_x,B,U_1,\ldots,U_t,C,Q_1,\ldots,Q_y,D,V_1,\ldots,V_s,\]where $x+y+t+s=n-4$. Call a point $P_i$ or $Q_i$ $U$-good if the triangulation has some edge from that point to some $U_j$, and define $V$-good similarly. Let's first count the number of intersections of edges that go from a $P_i$ or $Q_i$ to a $U_j$ with $AB\cup CD$. Let $P_{a_1},\ldots,P_{a_g}$ be the $U$-good $P_i$s where $a_1<\cdots<a_g$, and let $Q_{b_1}<\cdots<Q_{b_h}$ be the $U$-good $Q_i$s where $b_1<\cdots<b_h$. Let the set of $j$s such that $U_j$ is connected to $P_i$ be called $S_{P_i}$, same with $Q_i$. It is clear that all the intervals $[\min S_{P_i},\max S_{P_i}]$ and $[\min S_{Q_i},\max S_{Q_i}]$ can not intersect in their interiors (but can intersect on their boundaries). It is easy to see that this implies that there are at most \[t + (g+h-1)\]such intersections. This means that the number of intersections of edges that go from $P_i$ or $Q_i$ to a $U_j$ with $AB\cup CD$ is bounded above by $t-1$ plus the number of $U$-good points. Similarly, the number of intersections of edges that go from $P_i$ or $Q_i$ to a $V_j$ with $AB\cup CD$ is bounded above by $s-1$ plus the number of $V$-good points. Now we have the count the number of edges between $P_i$s and $Q_j$s (each of these edges count towards to intersections with $AB\cup CD$). Suppose there are $g_u$ $U$-good $P_i$s and $g_v$ $V$-good $P_i$s. It is easy to see then that there are at most $\max\{\min\{x+2-g_u-g_v,x\},0\}$ possible $P_i$s that can even connect to a $Q_i$. We assume that $g_u,g_v\ge 1$ (in they case where they are not we can have a better bound for $P_i$ to $U_j$s or $V_j$s which compensates). If $x+2-g_u-g_v<0$, then we're fine as there are then $0$ possible such edges anyway. Thus, we have that the number of possible edges is at most \[(x+2-g_u-g_v)+(y+2-g_u'-g_v')-1\]edges intersecting $AB\cup CD$ that go from some $P_i$ to some $Q_j$ (where $g_u'$ is the number of $U$-good $Q_i$s and $g_v'$ is similar). Therefore, the total number of intersections is at most \[(t-1)+g_u+g_u'+(s-1)+g_v+g_v'+2[(x+2-g_u-g_v)+(y+2-g_u'-g_v')-1].\]As mentioned above, we are assuming $g_u,g_v,g_u',g_v'\ge 1$, so this is at most \[2(x+y)+t+s+4-(g_u+g_v+g_u'+g_v')\le 2(x+y)+t+s = n-4+x+y,\]as desired. $\blacksquare$ The final bound now follows by summing bounds given by the above lemma. Suppose first that $n$ is odd. Let $d_1\le d_2\le\cdots\le d_{n-3}$ be the lengths of the chords of the red triangulation. Applying the lemma above bounds above the total red-black intersections by \[(d_1+\cdots+d_{n-3})+\frac{n-3}{2}(n-4).\]We claim that $d_1,d_2\le 1$, $d_3,d_4\le 2$, so on till $d_{n-4},d_{n-3}\le \frac{n-3}{2}$. This is clear by induction, since we can start by removing two chords of length $1$ to get an $(n-2)$-gon, and now chords of length $1$ with respect to that $(n-2)$-gon have actual length at most $2$, and so on. This shows that the total number of intersections is at most \[\frac{n-3}{2}\cdot\frac{n-1}{2}+(n-4)\frac{n-3}{2} = \frac{3(n-3)^2}{4}.\]Suppose now that $n$ is even. Note that the number of red-black intersections with any given red chord is at most $n-3$. Thus, a similar bound as above bounds above the number of red black intersections by \[\left(1+1+2+2+\cdots+\frac{n-4}{2}+\frac{n-4}{2}\right)+\frac{n-4}{2}(n-4)+n-3=\frac{3(n-3)^2+1}{4}.\]Therefore, there are always at most $\boxed{\lceil\tfrac{3}{4}(n-3)^2\rceil}$ intersections. We now provide a construction for each $n$. We label the points $1,2,\ldots,n$ in order. If $n$ is even, let the black triangulation have edges \[\{1,3\},\{1,4\},\ldots,\{1,\tfrac{n+1}{2}\},\{\tfrac{n+1}{2}+2,\tfrac{n+1}{2}\},\{\tfrac{n+1}{2}+3,\tfrac{n+1}{2}\},\ldots,\{n-1,\tfrac{n+1}{2}\}\]and the red triangulation have edges given by $\{x+1,y+1\}\pmod{n}$ where $\{x,y\}$ are the black edges. The construction for odd $n$ is similar.

Sorry for the bump, but it's important to mention that the $n$-gon is convex (which the official shortlist statement does).

Suppose we have a convex $n$-gon. Some $n-3$ diagonals are coloured black and some other $n-3$ diagonals are coloured red (a side is not a diagonal), so that no two diagonals of the same colour can intersect strictly inside the polygon, although they can share a vertex. Find the maximum number of intersection points between diagonals coloured differently strictly inside the polygon, in terms of $n$. Proposed by Alexander Ivanov, Bulgaria

Click to reveal hidden text