1
$\begingroup$

$40$ people sit around a circular table. In how many ways can we choose $5$ people so that between any two of them there are at least $3$ other people?

Things I have done so far: This question is a form of stars and bars problem. So consider a person $A$. The number ways that person $A$ is included is equal to $${35+5-1-3-3-3-3-3 \choose 5-1}={24 \choose 4}.$$

The answer (according to the answer key): $\frac{40}{5} {24 \choose 4}$

I don't understand where the $\frac{40}{5}$ come from.

$\endgroup$
  • $\begingroup$ @Vikram: Instead of just introducing MathJax, please try to fix as many problems with the post as possible. $\endgroup$ – user642796 Jul 28 '14 at 10:38
1
$\begingroup$

When a seat is chosen the next three seats to the right are blocked. Assume that seat ${\bf 1}$ is chosen. Then the seats ${\bf 2}$–${\bf 4}$ are blocked, and we have to choose four more seats from the remaining $36$ seats. An admissible choice can be encoded as a binary word $w$ containing four ones and twenty zeros (the zeros are for "voluntarily" unchosen seats). There are ${24\choose 4}$ such words. After the word $w$ has been written three additional zeros are inserted after each $1$. The resulting word $\tilde w$ has length $36$ and represents an admissible choice of seats. Conversely, each admissible choice containing seat ${\bf 1}$ can be realized in this way.

Denote the total number of admissible choices by $N$. Each choice affects $5$ seats, so that $5N$ seats would be chosen when playing it all through. For symmetry reasons all seats would be chosen an equal number of times, namely ${5N\over40}$ times. Since we already know that seat ${\bf 1}$ would be chosen ${24\choose 4}$ times the total number $N$ of admissible choices is given by $$N={40\over5}\cdot{24\choose 4}=85\,008\ .$$

$\endgroup$
  • $\begingroup$ Nice solution! Is there an easy way to handle the case where the number of people to be chosen does not divide the total number of people, or is that a much harder problem? $\endgroup$ – user84413 Jul 28 '14 at 22:04
  • $\begingroup$ @user84413: Thank you for the question. I have edited my answer, so that it becomes evident that there is no divisibility condition. $\endgroup$ – Christian Blatter Jul 29 '14 at 8:17
  • $\begingroup$ Thanks - I can see now that your method applies even when the number of people chosen is not a divisor of 40. $\endgroup$ – user84413 Jul 30 '14 at 23:59

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.