2
$\begingroup$

$9$ people were in a meeting. Some of them fell asleep during some intervals in the meeting, each of them at most $4$ intervals. For any pair of them, at some point they are both asleep. Prove that at some point, at least $3$ of them were asleep.

If the assumption were that each of them fell asleep for at most $1$ interval, we could show that at some point all of them were asleep. This is because, suppose they fell asleep at $[x_1,y_1],[x_2,y_2],\ldots,[x_9,y_9]$, with $x=\max(x_1,\ldots,x_9)$ and $y=\min(y_1,\ldots,y_9)$, then the assumption on pairs implies that $x\leq y$.

$\endgroup$

1 Answer 1

2
$\begingroup$

Sorry for posting a new answer, as my previous answer is indeed logically wrong and even though the new answer uses a similar approach, it is logically very different from the previous one. (And if I edited the old one all the comments will not make sense any more) So I deleted the previous one and posted this answer as a new one.

Assume no three people sleep at the same time for the sake of contradiction.

Now since there are $9$ people and each two of them have an intersection, and also since no three people are on the same intersection, we have at least ${9\choose2}=36$ intersections.

Also since each person has at most $4$ intervals, that means altogether there are at most $36$ intervals.

Define a graph $G=(I,N)$ which vertices are the set of intervals $I$ and edges are the intersections $N$ where two vertices are connected when they have an intersection.

We can show that no cycle exist in $G$.

We first show no 3-cycle exist: suppose it exists and the intervals $i_1,i_2,i_3$ have pairwise intersections. This means $i_{1min}<i_{2max}, i_{2min}<i_{1max}$ and similar for the other pairs.

Now consider the interval $[max(i_{1min},i_{2min},i_{3min}),min(i_{1max},i_{2max},i_{3max})]$. Since the former is smaller than the latter by the pairwise inequalities, we can conclude this is indeed a valid interval that is the intersection of three different people, contradiction.

Hence no three intervals have pairwise intersections.

Now suppose a cycle of length $k$ exists, that is, there exist intervals $i_1,i_2,...,i_k$ such that all pairs $(i_1,i_2,), (i_2,i_3),...,(i_{k-1},i_k),(i_k,i_1)$ have intersections.

Let's consider the interval that finishes the earliest, $i_f$ such that $\large{i_{f_{max}}\leq i_{j_{max}}}$ for all $j=1,2,...,k$.

Now let $i_e$ be the preceeding vertex of $i_f$ in the cycle (i.e for $f=2$, $e=1$ and for $f=1$, $e=k$). Also let $i_g$ be the next vertex of $i_f$ in the cycle.

Then we have $\large{i_{e_{max}}\geq i_{f_{max}} > i_{g_{min}}}$ and also $\large{i_{g_{max}}\geq i_{f_{max}} > i_{e_{min}}}$ so $i_e$ and $i_g$ has an intersection contradicting a 3-cycle does not exist.

Hence there is no cycle in $G$.

Hence $G$ is a forest (a graph where all components are trees). Hence the number of vertex is strictly greater than the number of edges. $36\geq|I|>|N|\geq 36$ contradiction.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .