Five people stay overnight in a hotel.

combinatorics/five.sleepers New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Five people stay overnight in a hotel.  Each sleeps twice during the
night (sleeps, wakes up for some time, and sleeps again), and for every
two people there is a period of time during which both are asleep.
Show that for some three people there is a period of time during which
all three are asleep.

Show solution

Assume that no 3 people are ever simultaneously sleeping. Whenever
someone falls asleep, there can be at most one other person sleeping at
that instant, so this event produces at most one pair of people that are
simultaneously sleeping. Since 5 people each fall asleep twice, this
event occurs exactly 10 times. So we end up with at most 10 pairs of
people that are simultaneously sleeping.

However, the first person to fall asleep does not give a pair of
simultaneous sleepers. So we end up with at most 9 pairs of people that
are simultaneously sleeping. This contradicts the condition that every 2
people are simultaneously sleeping, since there are 10 pairs of people.

In article <1996Apr26.070046.21817@sequent.com>, naineni@sequent.com
(Malahal Rao Naineni) writes:
>Generalizations: n people, every m people have a common period,
>then there is a common period for (m+1) people. What are the
>possible values of m for a given n?

Too general for me. The original problem makes a nice puzzle. This
generalization sounds like serious mathematics.

-- Barry Wolk <wolk@ccm.umanitoba.ca>