8
$\begingroup$

There are $6$ people in a ship. As the journey is long, they decide to take shifts. In each shift, some wake up and control the ship while others sleep. How many such shifts are required so that for any two persons $A$ and $B$ there exists a shift such that $A$ wakes and $B$ sleeps (minimum)?

My try:

I don't know why but I felt that the minimum number of sittings will be when $3$ persons sleep and the other $3$ wake. So I got the following solution :

SLEEP
123
356
146
245

So the required number of sittings is 4. But I think my solution to be a matter of luck. So my question is
" Is there a mathematical solution to this question?"

$\endgroup$
  • $\begingroup$ I think there are more than $4$ combinations of three people chosen from six people... When does $3$ sleep while $2$ is awake? When does $2$ sleep while $3$ is awake? $\endgroup$ – abiessu Feb 23 at 5:59
  • $\begingroup$ In your example, there is no day when 1 wakes and 3 sleeps. My answer is 5. $\endgroup$ – zimbra314 Feb 23 at 6:08
  • $\begingroup$ No there is during the second sitting $\endgroup$ – Abhinav Feb 23 at 6:09
  • $\begingroup$ sorry, 1 sleeps and 3 is awake $\endgroup$ – zimbra314 Feb 23 at 6:10
  • $\begingroup$ I think I have mistyped my solution. Well I will edit it but my question is to find a mathematical solution for the problem. $\endgroup$ – Abhinav Feb 23 at 6:14
2
$\begingroup$

Proof that $4$ is a lower bound for the number of shifts required:

There are $6\cdot5=30$ ordered pairs $(A,B)$ of distinct people from the people in the ship, so the shifts must combine to have at least $30$ ordered pairs of (awake person, asleep person).

If in a given shift $k$ people are awake and $6-k$ are asleep, then the number of such ordered pairs is $k(6-k)$. This is maximized when $k=3$, when there are $9$ such ordered pairs.

Therefore it is impossible for $3$ shifts to cover all possibilities, since there can be at most $27$ ordered pairs covered between them.

$\endgroup$
1
$\begingroup$

Say we have lists $$L_1,L_2,...,L_k$$ of sleeping people. List $L_i$ connect with a pair of people $\{x,y\}$ if exactly one of them is on the list. Let $s_i = |L_i|$. Then list $L_i$ is connected with at most $$s_i(6-s_i)\leq \Big({s_i+(6-s_i)\over 2}\Big)^2 = 9$$ pairs and each pair is connected with at least to different lists. So we have $$k\cdot 9\geq {6\choose 2}\cdot 2\implies k\geq 4$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.