Maths Olympiad Prep

Library / /129 of 155

Combinatorics Difficulty 6.9 National olympiad Prove it Saudi Arabia

Given a set SS of 200 points on the plane: 100 points are the vertices of a convex polygon AA, and 100 other points are in the interior of the polygon. Moreover, there does not exist 3 collinear points. A triangulation is a way to partition the polygon AA into triangles by drawing the edges between some two points of SS such that any two edges do not intersect in the interior, and each point in SS is the vertex of at least one triangle.

1. Prove that number of edges does not depend on the triangulation.
2. Show that for any triangulation, one can draw each triangle by 1 of 3 given colors such that 2 adjacent triangles have different colors.

Solution

1) Suppose that we have kk triangles in some triangulation. By calculating the sum of all angles of these triangles, we have 180k180^\circ \cdot k.
The sum of interior angles of AA is 18098180^\circ \cdot 98.
The sum of angle around each point among 100 points is 360100360^\circ \cdot 100. Hence, we have
180k=18098+360100k=298. 180^\circ \cdot k = 180^\circ \cdot 98 + 360^\circ \cdot 100 \Leftrightarrow k = 298.
Each triangle gives 3 edges and among them, there are 100 edges of AA. Note that the interior edges are double counted, then the number of edges in each triangulation is
32981002+100=497. \frac{3 \cdot 298 - 100}{2} + 100 = 497.

2) Fix the polygon AA, we will prove this problem by induction on m+nm+n of total points, in which nn is the number of vertices of AA and mm is the number of interior points.

For m+n=3m+n=3, which implies that n=3,m=0n=3, m=0, we just have one triangle with no interior point. We color this triangle by some color and finish this case.

For bigger m+nm+n, whenever we add one more point and perform the triangulation, we have two cases:

1. If there are some triangle that share exactly one edge with the polygon AA, call triangle XX. Then XX is adjacent to at most two other triangles then if these two triangles were colored by different colors, we just need to color XX by the third color (in case two triangles were colored by the same color, we color XX by a random color among the rest). Since XX has one vertex that is the interior point, then we can move this point outside as the vertex of AA. It is easy to see that polygon AA still has nn vertices and mm decreases by 1. Then we can apply the induction hypothesis.

Figure 1

2. If for all triangles XX as described above, the vertices of XX are not the interior points then XX is adjacent to exactly one triangle. We just color XX by the color different from the adjacent one and remove the vertex of AA to make number of sides of AA decrease by 2 and nn decreases by 1. Then we can also apply the induction hypothesis.

Therefore, in all cases, we can change the triangulation of m+nm+n points to triangulation of m+n1m+n-1 points, which means the problem can be solved by induction completely.

Then we always can draw the triangle by one of three colors that satisfy the given condition. \square

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 and solution reproduced as published; topic and difficulty added by this site.