uniolympiads Ελληνικά

IMC 2006, Day 2, Problem 1

Let VV be a convex polygon with nn vertices.

(a) Prove that if nn is divisible by 33 then VV can be triangulated (i.e. dissected into non-overlapping triangles whose vertices are vertices of VV) so that each vertex of VV is the vertex of an odd number of triangles.

(b) Prove that if nn is not divisible by 33 then VV can be triangulated so that there are exactly two vertices that are the vertices of an even number of the triangles.

Original from the official PDFLet V be a convex polygon with n vertices. (a) Prove that if n is divisible by 3 then V can be triangulated (i.e. dissected into non-overlapping triangles whose vertices are vertices of V ) so that each vertex of V is the vertex of an odd number of triangles. (b) Prove that if n is not divisible by 3 then V can be triangulated so that there are exactly two vertices that are the vertices of an even number of the triangles. (20 points)

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. Apply induction on nn. For the initial cases n=3,4,5n=3,4,5, chose the triangulations shown in the Figure to prove the statement.

[Figure in the original PDF.]

Now assume that the statement is true for some n=kn=k and consider the case n=k+3n=k+3. Denote the vertices of VV by P1,…,Pk+3P_1,\ldots,P_{k+3}. Apply the induction hypothesis on the polygon P1P2…PkP_1P_2\ldots P_k; in this triangulation each of vertices P1,…,PkP_1,\ldots,P_k belong to an odd number of triangles, except two vertices if nn is not divisible by 3. Now add triangles P1PkPk+2P_1P_kP_{k+2}, PkPk+1Pk+2P_kP_{k+1}P_{k+2} and P1Pk+2Pk+3P_1P_{k+2}P_{k+3}. This way we introduce two new triangles at vertices P1P_1 and PkP_k so parity is preserved. The vertices Pk+1P_{k+1}, Pk+2P_{k+2} and Pk+3P_{k+3} share an odd number of triangles. Therefore, the number of vertices shared by even number of triangles remains the same as in polygon P1P2…PkP_1P_2\ldots P_k.

[Figure in the original PDF.]

Transcribed from the official solutions, page 1. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?