Skip to main content
OlympiadHQ

Browse · MathNet

Print

Belarusian Mathematical Olympiad

Belarus counting and probability

Problem

Some positive integers are written on cards, at least two different numbers on each card. The same number may be written on several cards. Two cards are called adjacent if the maximum number on one of them is equal to the minimum number on the other. Prove that if there are no adjacent cards then all written numbers can be divided into two sets so that any card contains at least one number from every set.
Solution
We construct two required groups and as follows: we choose the smallest number on each card and put it in the group . Therefore, every card contains at least one number from . All other numbers we put in the group . Since there are no adjacent cards, the largest number in any card does not coincide with the smallest number on other cards, so this largest number belongs to . Therefore, every card contains at least one number from .

Techniques

Coloring schemes, extremal arguments