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 .
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.