Problem 2129

Solution:

The answer is $8$.

Call a set consisting of red points and green points good if no three points are collinear and any unicoloured triangle contains a point of the other colour.

On the one hand, the figure on the left below shows an example of a good set with $8$ points. The figure on the right shows the two types of unicoloured triangles - all other unicoloured triangles are reflections of those.

On the other hand, we shall prove that a good set can have at most four points of each colour. We give two proofs.

First proof. For a proof by contradiction, let $S$ be a counterexample of minimal cardinality. We may assume that $S$ has at least five red points.
Let $P$ be any vertex of the convex hull of $S$. Then $P$ cannot be in the interior of any triangle, so $S \setminus \{P\}$ is good. But $S$ was a minimal counterexample, so $S \setminus \{P\}$ has at most four points of each colour. Therefore, $S$ has exactly five red points, all vertices of the convex hull of $S$ are red, and $S$ has at most four green points.

Consider the convex hull of $S$. It is a triangle, a quadrilateral, or a pentagon.

Case i: The convex hull is a triangle.
Let $A, B$ and $C$ denote the vertices of the triangle, and let $I$ and $J$ be the interior red points. Without loss of generality, we may assume that the line $IJ$ intersects sides $AB$ and $AC$ (and not $BC$), and $I$ is nearer to $AB$ than $J$ is. Now $ABI$, $AIJ$, $AJC$, $BIJ$ and $BJC$ are five unired triangles with disjoint interiors, so at least one of them must be empty, because there are at most four green points. Thus, $S$ is not good, in contradiction to our assumptions.

Case ii: The convex hull is a quadrilateral.
Let the vertices of the quadrilateral be $A, B, C, D$, in this cyclic order, and $I$ be the red point in the interior. Now $ABI$, $BCI$, $CDI$ and $DAI$ are unired triangles with disjoint interiors, each has a green point inside: denote them by $X, Y, Z, W$ respectively. Then $XYZ$ and $ZWX$ are two unigreen triangles, but both cannot have $I$ (the only possible red point) in their interiors.

Case iii: The convex hull is a pentagon.
Let $A, B, C, D$ and $E$ denote the vertices of the pentagon, in this cyclic order. Now $ABC$, $ACD$ and $ADE$ are three unired triangles with disjoint interiors, each must have a green point in its interior, these form a unigreen triangle, which cannot have any red point inside.

Second proof.

Lemma. Let a good set of coloured points be given.
If the convex hull of some red points contains exactly $x$ red points, with exactly $y$ of them being in its interior, then there are at least $x+y-2$ green points in its interior. (The statement is analogous for switched colours.)

Proof. If the convex hull is not a polygon (i.e. $x \leq 2$), the statement is trivial. Otherwise consider a partition of the convex hull of the red points into triangles, all of which have only red points as vertices, and have no other red points in their interiors. Let $N$ be the number of triangles of the partition. Then the sum of their angles is $N\pi$. On the other hand, at each interior point, the sum of the angles of the triangles is always $2\pi$, and at the peripheral points that form a convex $(x-y)$-gon, the sum is $(x-y-2)\pi$. So the sum of the angles of the triangles in the partition is
$$N\pi = 2y\pi + (x-y-2)\pi$$
which reduces to $N = x + y - 2$. Each of the disjoint unicoloured triangles must contain a single point in its interior, which proves the lemma.

Applying the lemma on all $n$ red points, where $m$ red points are inside their convex hull, gives that there are at least $n + m - 2$ green points inside the red points' convex hull. Now applying the lemma again on these green points gives that there are at least $(n + m - 2) - 2$ red points in their convex hull. But these red points are also interior points of the convex hull of all red points, therefore
$$(n + m - 2) - 2 \leq m$$
This reduces to $n \leq 4$, and our statement is proven.