During a certain lecture, each of five mathematicians fell asleep exactly twice. For each pair of mathematicians, there was some moment when both were asleep simultaneously. Prove that, at some moment, three of them were sleeping simultaneously.
Problem
Source:
Tags: AMC, USA(J)MO, USAMO, graph theory, combinatorics unsolved, combinatorics
darij grinberg
26.08.2011 13:28
Ages ago, we had this on http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=18809 . I am not sure if this is really pre-olympiad, as the solution requires some olympiad mathematics experience imho. Oh, and I hate to say I still don't understand pbornsztein's solution.
JBL
26.08.2011 15:47
It's closely related to this one: https://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=422227&p=2387989&hilit=interval#p2387989 It also appeared here (with a solution pointlessly copied out of Kalva): https://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=355668&hilit=five+professors and here (with a solution that I haven't looked at yet but maybe which is too simple): https://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=82344&hilit=professors+asleep
GlassBead
27.08.2011 02:29
There is also a very nice solution involving graph theory (from ACoPS).
Basically, let the scientists' names be $A, B, C, D, E$, and the intervals when they fell asleep be $A_1, A_2, B_1, B_2, \ldots$, and let these $10$ points be a graph, and let an edge be drawn between two points if their respective intervals intersect. There are at least $\binom{5}{2}=10$ edges in this graph, and exactly $10$ vertices.
Then you basically need to show that if there is a cycle in this graph, then this would imply that there were at some moment, three scientists sleeping simultaneously.
After that, it suffices to show that there must exist at least one cycle in a graph with $10$ vertices and at least $10$ edges (which is pretty much trivial from the basic property $e+1=v$ of a tree).