tourists
Source: Bulgarian Math Olympiad MO 2004, problem 3
May 17, 2004
pigeonhole principlecombinatorics unsolvedcombinatoricsgraph theory
Problem Statement
A group consist of n tourists. Among every 3 of them there are 2 which are not familiar. For every partition of the tourists in 2 buses you can find 2 tourists that are in the same bus and are familiar with each other. Prove that is a tourist familiar to at most tourists.