Maths Olympiad Prep

Library / /1 of 6

Combinatorics Difficulty 4.3 AIME Prove it Hong Kong

Suppose there are 6 members in an International Mathematical Olympiad team. Prove that among these 6 members there are three members who either all know each other or all don't know each other.

Solution

Suppose the members are A,B,C,D,E,FA, B, C, D, E, F. By the pigeonhole principle, either AA knows at least 52=3\left\lfloor \frac{5}{2} \right\rfloor = 3 other members, or AA does not know at least 3 other members. WLOG assume it is the former case. Suppose AA knows B,C,DB, C, D. If any two of B,C,DB, C, D know each other, say BB and CC, then we are done since all of A,B,CA, B, C know each other. Otherwise, any two of B,C,DB, C, D do not know each other, which is also our goal. This completes the proof.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.