uniolympiads English

IMC 2006, Ημέρα 2, Θέμα 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.

Πρωτότυπο από το επίσημο 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)

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

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.]

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 1. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;