Five professors attended a lecture. Each fell asleep just twice. For each pair there was a moment when both were asleep. Show that there was a moment when three of them were asleep.
Solution
This is a slightly tricky application of the pigeonhole principle.
For each pair take the first moment when they are both asleep. There are ten pairs, so ten such moments. If two coincide, then we are done because at that moment at least three professors were asleep. So suppose they are all distinct and form a set S. Each such moment must also be one of the 10 occasions when a professor falls asleep. But consider the earliest member of S. Two professors were asleep at that moment so two fell asleep at or before that moment. Thus each of the remaining 9 members of S must be one of the 8 later occasons when a professor fell asleep. So they cannot all be distinct. Contradiction.
© John Scholes
jscholes@kalva.demon.co.uk
26 Aug 2002