3

At a circular table for $100$ persons, $4$ people will shake hands with each other. How many ways are there to choose $4$ people in that group so that there are no person who shakes hands sits beside another person who shakes hands too?

I have tried something like this problem but simpler. I solve it by enumerating it manually. If I change the total number of people to $8$ and choose $3$ people that shake hands with each other, I found that the answer is $16$.

ABCDEFGH
x-x-x---
x-x--x--
x-x---x-
x--x-x--
x--x--x-
x---x-x-
-x-x-x--
-x-x--x-
-x--x-x-
--x-x-x-
-x-x---x
-x--x--x
-x---x-x
--x-x--x
--x--x-x
---x-x-x

x is the shaking hand group

Can somebody help me solving this problem. Thank you :)

Dimas Riatmodjo
  • 115
  • Since they are in a circle why are 1, 2, 5, 6, 9, 10, 12, and 15 different in your example? – Stephen Meskin Dec 14 '17 at 02:08
  • @StephenMeskin Because it's pointing on different person. – Dimas Riatmodjo Dec 14 '17 at 02:16
  • OK. I'm still trying to understand the problem. Are we to assume that the 100 people are fixed. Can I assume that Mr. 2 sits between Mr. 1 and Ms. 3, that Ms. 3 sits between Mr. 2 and Mrs. 4, etc around the table until we get to Mr. 1 between Ms.100 and Mr.2. And the game is to select 4 people from this arrangement satisfying your condition. – Stephen Meskin Dec 14 '17 at 03:38
  • continued I think I'm starting to understand but if I do then aren't you missing x- -x- -x- from your example? – Stephen Meskin Dec 14 '17 at 04:46
  • There are actually $16$ cases in your example. Using the method I explained, I get $\binom{6}{3} - \binom{4}{1} = 20 - 4 = 16$. You missed the case ADG. – N. F. Taussig Dec 14 '17 at 21:48
  • Oh I'm sorry i didn't realize it btw >_<". Yes actually there are 16 cases. Thank You – Dimas Riatmodjo Dec 14 '17 at 22:48

3 Answers3

2

Let the $n$ people around the table be labeled $1, 2, \ldots n $ and let $k$ be the # of those people to be selected.
We will count using two cases. Case A: $1$ is selected. Case B: $1$ is not selected.

Case A: $ \binom{n-k-1}{k-1}$
Case B: $ \binom{n-k}{k}$
Their sum is $\frac{n}{k}\binom{n-k-1}{k-1}$

You can check that the formula works for your example (for which the answer is 16).

I will prove Case A, leaving Case B for you.

EDIT: This proof has been revised using the methods of the clean proof by @ChristianBlatter

Assume $1$ is selected. Consider a sequence of $n-k\; 0$s. There are $n-k-1$ spaces between the $0$s. Select $k-1$ of these spaces. This can be done $ \binom{n-k-1}{k-1}$ ways. Place a $1$ into each of the selected places. This gives a unique sequence of length $n-1$ consisting $n-k \; 0\text{s and } k-1\; 1$s starting and ending with $0$ and with a $0$ between each of the $1$s.

Now label the elements of the string $2, 3, 4, \ldots , n$. The selected hand shakers are $1$ and the $k-1$ people in the string that had been selected.

Stephen Meskin
  • 1,829
  • 8
  • 17
  • There is more than one way of solving this problem. If you solve the problem for a row, then subtract the number of cases in which people at both ends of the row are selected, you obtain the formula $\binom{n - k + 1}{k} - \binom{n - k - 1}{k - 2}$. – N. F. Taussig Dec 14 '17 at 21:54
2

Assume there are $N$ admissible quadruples. These involve $4N$ choices of an individual, and by symmetry each person is chosen the same number of times, hence ${N\over25}$ times. We now count the number of admissible quadruples having person $100=0$ as a member. The admissible choices of the remaining three persons can be encoded as a binary word of length $99$ obtained in the following way: Write $96$ zeros, and insert a one into $3$ of the $95$ gaps between the zeros.

It follows that the total number of admissible quadruples is given by $$N=25\cdot{95\choose3}=3\,460\,375\ .$$

Christian Blatter
  • 226,825
2

A circle can be formed by joining the ends of a row together. We solve the problem for a row, then remove those solutions in which two of the selected people are at the ends of the row.

We will arrange $96$ blue balls and $4$ green balls in a row so that the green balls are separated. Line up $96$ blue balls in a row, leaving spaces in between them and at the ends of the row in which to insert a green ball. There are $95$ spaces between successive blue balls and two at the ends of the row for a total of $97$ spaces. To separate the green balls, we choose four of these spaces in which to insert a green ball, which we can do in $$\binom{97}{4}$$ ways. Now number the balls from left to right, the numbers on the green balls represent the positions of the selected people.

However, those selections in which there are green balls at both ends of the row are inadmissible since that means the people in those positions will be in adjacent seats when the ends of the row are joined. If two green balls are placed at the ends of the row, the other two green balls must be placed in two of the $95$ spaces between successive blue balls. Hence, there are $$\binom{95}{2}$$ placements of green balls in which both ends of the row are filled by green balls. As these placements are inadmissible, the number of ways four of the $100$ people at the circular table may be selected so that no two are adjacent is $$\binom{97}{4} - \binom{95}{2}$$

N. F. Taussig
  • 76,571