, 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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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