Maths Olympiad Prep

Library / /10 of 29

Combinatorics Difficulty 5.5 AIME, harder Prove it Silk Road Mathematics Competition

A (non-oriented) graph (without loops) with 2n2n vertices and 2n(n1)2n(n-1) edges is given, n>1n > 1. Prove that some vertices and edges of the graph can be coloured in red in such way that each red edge connects red vertices and each red vertex belongs to exactly nn red edges.

Solution

Consider a regular 2n2n-gon (inscribed in a unit circle), which we label nn segments from the set of all sides and all diagonals.
The problem is equivalent to the following one: prove that some of unlabelled segments (including endpoints) can be coloured in red in such way that each red vertex belongs to exactly nn red segments.
We define k-segment as a segment spanning an arc of the length πk/n\pi k/n.
The following cases are possible:
Case 1. Let some two labelled segments have a common vertex. Then we choose this vertex and other n2n-2 vertices in such way that at least a vertex is chosen in each labelled segment (so, totally we choose 1+(n2)=n11+(n-2)=n-1 vertices). The other vertices will form a complete graph (i.e. a clique) with n+1n+1 vertices: each two vertices are connected by an unlabeled segment. Colour these segments in red and we are done.
Case 2. The labelled segments have no common points.

Subcase 2.1. nn is even.
W.l.o.g. (using an appropriate numeration of vertices) we can assume that all longest diagonals (i.e. nn-segments) are labelled. Colour all kk-segments for k=1,2,,n/2k = 1, 2, \dots, n/2 in red and we are done.
Subcase 2.2. nn is odd.
W.l.o.g. (using an appropriate numeration of vertices again) we can assume that nn 1-segments are labelled (i.e. nn sides of the polygon, in alternating manner). Colour all unlabeled kk-segments for k=1,2,,(n+1)/2k = 1, 2, \dots, (n+1)/2 in red and we are done.

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 and solution reproduced as published; topic and difficulty added by this site.