Balti Tee 1991 · Ülesanne 12

Kombinatoorika

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.

Muuda valikut

Kui oled valmis

Ülevaatematerjal muutub kättesaadavaks järgmise päevaülesannete komplektiga.

Ülevaade

Teemad

Värvimised ja konfiguratsioonid · Dirichlet’ printsiip ja ekstremaalargumendid · Loendamine

Lahendused

Lahendus

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.

Mujal

AoPS · Baltic Way 1991