Baltic Way 1991 · Problem 12

Combinatorics

The vertices of a convex 1991-gon are enumerated with integers from 1 to 1991. Each side and diagonal of the 1991-gon is coloured either red or blue. Prove that, for an arbitrary renumeration of vertices, one can find integers $k$ and $l$ such that the line connecting vertices with numbers $k$ and $l$ before the renumeration has the same colour as the line between the vertices having these numbers after the renumeration.

Change pool

When you’re ready

Review material becomes available with the next Daily.

Review

Topics

Colorings and configurations · Pigeonhole and extremal arguments · Counting and enumeration

Solutions

Solution

Solution:

Assume there exists a renumeration such that for any numbers $1 \leq k < l \leq n$ the segment connecting vertices numbered $k$ and $l$ before the renumeration has a different colour than the segment connecting vertices with the same numbers after the renumeration. Then there has to be an equal number of red and blue segments, and thus the total number of segments must be even. However, the number of segments is $\binom{1991}{2} = 995 \cdot 1991$ , an odd number.

Elsewhere

AoPS · Baltic Way 1991