Maths Olympiad Prep

Library / /6 of 8

Geometry Difficulty 7.7 National Olympiad, round 2 Prove it Middle European Mathematical Olympiad (MEMO)

Problem:

Consider finitely many points in the plane with no three points on a line. All these points can be coloured red or green such that any triangle with vertices of the same colour contains at least one point of the other colour in its interior.
What is the maximal possible number of points with this property?

Solution

Solution:

The answer is 88.

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 88 points. The figure on the right shows the two types of unicoloured triangles - all other unicoloured triangles are reflections of those.

Figure 1

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 SS be a counterexample of minimal cardinality. We may assume that SS has at least five red points.
Let PP be any vertex of the convex hull of SS. Then PP cannot be in the interior of any triangle, so S{P}S \setminus \{P\} is good. But SS was a minimal counterexample, so S{P}S \setminus \{P\} has at most four points of each colour. Therefore, SS has exactly five red points, all vertices of the convex hull of SS are red, and SS has at most four green points.

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

Figure 2

Case i: The convex hull is a triangle.
Let A,BA, B and CC denote the vertices of the triangle, and let II and JJ be the interior red points. Without loss of generality, we may assume that the line IJIJ intersects sides ABAB and ACAC (and not BCBC), and II is nearer to ABAB than JJ is. Now ABIABI, AIJAIJ, AJCAJC, BIJBIJ and BJCBJC 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, SS 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,DA, B, C, D, in this cyclic order, and II be the red point in the interior. Now ABIABI, BCIBCI, CDICDI and DAIDAI are unired triangles with disjoint interiors, each has a green point inside: denote them by X,Y,Z,WX, Y, Z, W respectively. Then XYZXYZ and ZWXZWX are two unigreen triangles, but both cannot have II (the only possible red point) in their interiors.

Figure 3

Figure 4

Case iii: The convex hull is a pentagon.
Let A,B,C,DA, B, C, D and EE denote the vertices of the pentagon, in this cyclic order. Now ABCABC, ACDACD and ADEADE 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 xx red points, with exactly yy of them being in its interior, then there are at least x+y2x+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. x2x \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 NN be the number of triangles of the partition. Then the sum of their angles is NπN\pi. On the other hand, at each interior point, the sum of the angles of the triangles is always 2π2\pi, and at the peripheral points that form a convex (xy)(x-y)-gon, the sum is (xy2)π(x-y-2)\pi. So the sum of the angles of the triangles in the partition is
Nπ=2yπ+(xy2)π N\pi = 2y\pi + (x-y-2)\pi
which reduces to N=x+y2N = 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 nn red points, where mm red points are inside their convex hull, gives that there are at least n+m2n + 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+m2)2(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+m2)2m (n + m - 2) - 2 \leq m
This reduces to n4n \leq 4, and our statement is proven.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.