Browse · MathNet
PrintSAUDI ARABIAN MATHEMATICAL COMPETITIONS
Saudi Arabia counting and probability
Problem
Given a set of 200 points on the plane: 100 points are the vertices of a convex polygon , 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 into triangles by drawing the edges between some two points of such that any two edges do not intersect in the interior, and each point in 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.
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 triangles in some triangulation. By calculating the sum of all angles of these triangles, we have . The sum of interior angles of is . The sum of angle around each point among 100 points is . Hence, we have Each triangle gives 3 edges and among them, there are 100 edges of . Note that the interior edges are double counted, then the number of edges in each triangulation is
2) Fix the polygon , we will prove this problem by induction on of total points, in which is the number of vertices of and is the number of interior points.
For , which implies that , we just have one triangle with no interior point. We color this triangle by some color and finish this case.
For bigger , 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 , call triangle . Then is adjacent to at most two other triangles then if these two triangles were colored by different colors, we just need to color by the third color (in case two triangles were colored by the same color, we color by a random color among the rest). Since has one vertex that is the interior point, then we can move this point outside as the vertex of . It is easy to see that polygon still has vertices and decreases by 1. Then we can apply the induction hypothesis.
2. If for all triangles as described above, the vertices of are not the interior points then is adjacent to exactly one triangle. We just color by the color different from the adjacent one and remove the vertex of to make number of sides of decrease by 2 and decreases by 1. Then we can also apply the induction hypothesis.
Therefore, in all cases, we can change the triangulation of points to triangulation of 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.
2) Fix the polygon , we will prove this problem by induction on of total points, in which is the number of vertices of and is the number of interior points.
For , which implies that , we just have one triangle with no interior point. We color this triangle by some color and finish this case.
For bigger , 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 , call triangle . Then is adjacent to at most two other triangles then if these two triangles were colored by different colors, we just need to color by the third color (in case two triangles were colored by the same color, we color by a random color among the rest). Since has one vertex that is the interior point, then we can move this point outside as the vertex of . It is easy to see that polygon still has vertices and decreases by 1. Then we can apply the induction hypothesis.
2. If for all triangles as described above, the vertices of are not the interior points then is adjacent to exactly one triangle. We just color by the color different from the adjacent one and remove the vertex of to make number of sides of decrease by 2 and decreases by 1. Then we can also apply the induction hypothesis.
Therefore, in all cases, we can change the triangulation of points to triangulation of 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.
Techniques
Euler characteristic: V-E+FConvex hullsAngle chasingColoring schemes, extremal argumentsInduction / smoothingConstructions and loci