Library / Danube Mathematical Competition /4 of 28

Danube Mathematical Competition, 2010

Combinatorics Difficulty 4.7 AIME Prove it Romania

All sides and diagonals of a convex $n$ -gon, $n \ge 3$ , are coloured one of two colours. Show that there exist $\lfloor (n+1)/3 \rfloor$ pairwise disjoint monochromatic segments. (Two segments are disjoint if they do not share an endpoint or an interior point.)

Solution

If all sides are monochromatic, then the assertion is clearly true. Otherwise, delete a vertex incident with two sides of different colours together with its neighbours, delete all sides and diagonals incident with these three vertices and apply induction.

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

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