Maths Olympiad Prep

Library / /16 of 61

Combinatorics Difficulty 5.7 AIME, harder Prove it Belarus

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 G1G_1 and G2G_2 as follows: we choose the smallest number on each card and put it in the group G1G_1. Therefore, every card contains at least one number from G1G_1. All other numbers we put in the group G2G_2. 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 G2G_2. Therefore, every card contains at least one number from G2G_2.

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.