## A Combi problem

For discussing Olympiad Level Combinatorics problems
Mehrab4226
Posts: 208
Joined: Sat Jan 11, 2020 1:38 pm

### A Combi problem

In a group of nine people, each person shakes hands with exactly two of the other people from the group. Let $N$ be the number of ways this handshaking can occur. Consider two handshaking arrangements different if and only if at least two people who shake hands under one arrangement do not shake hands under the other arrangement. Find the remainder when $N$ is divided by $1000$.
Source:
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Anindya Biswas
Posts: 196
Joined: Fri Oct 02, 2020 8:51 pm
Contact:

### Re: A Combi problem

If we transform the handshaking into a graph where the people are vertex and handshakes are represented by edges, we will get one or more disjoint cycles. Each cycle must have at least $3$ people so that everyone shakes hand with two other.
So we have $4$ cases.
1. We can take all of the people and put them in a cycle of length $9$.
2. We can divide them into $5$-cycle and $4$-cycle.
3. We can divide them into $6$-cycle and $3$-cycle.
4. We can divide them into three $3$-cycles
For the first case, this is just cyclic permutation and it can be done in $\frac{9!}{2\times9}$ since rotation and reflection results in same handshaking.
For the second case, we can divide $9$ people into group of $5$ people and $4$ people in ${9\choose4}=\frac{9!}{4!\cdot5!}$ ways. For each grouping, there are $\frac{5!}{2\times5}\cdot\frac{4!}{2\times4}$ ways to put them in the cycles. So, by multiplying this two results, we get total $\frac{9!}{2\times4\times2\times5}$ ways

Similarly, for the third case, there are total $\frac{9!}{2\times3\times2\times6}$ ways to do that.

And for the fourth case, there are just $\frac{9!}{2\times3\times2\times3\times2\times3}$ ways similarly.
So, $N=9!\left(\frac{1}{2\times9}+\frac{1}{2^2\times4\times5}+\frac{1}{2^2\times3\times6}+\frac{1}{2^3\times3\times3\times3}\right)$
$\Longrightarrow \boxed{N=31416}$
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Mehrab4226
Posts: 208
Joined: Sat Jan 11, 2020 1:38 pm

### Re: A Combi problem

Anindya Biswas wrote:
Thu Apr 08, 2021 11:22 am
If we transform the handshaking into a graph where the people are vertex and handshakes are represented by edges, we will get one or more disjoint cycles. Each cycle must have at least $3$ people so that everyone shakes hand with two other.
So we have $4$ cases.
1. We can take all of the people and put them in a cycle of length $9$.
2. We can divide them into $5$-cycle and $4$-cycle.
3. We can divide them into $6$-cycle and $3$-cycle.
4. We can divide them into three $3$-cycles
For the first case, this is just cyclic permutation and it can be done in $\frac{9!}{2\times9}$ since rotation and reflection results in same handshaking.
For the second case, we can divide $9$ people into group of $5$ people and $4$ people in ${9\choose4}=\frac{9!}{4!\cdot5!}$ ways. For each grouping, there are $\frac{5!}{2\times5}\cdot\frac{4!}{2\times4}$ ways to put them in the cycles. So, by multiplying this two results, we get total $\frac{9!}{2\times4\times2\times5}$ ways

Similarly, for the third case, there are total $\frac{9!}{2\times3\times2\times6}$ ways to do that.

And for the fourth case, there are just $\frac{9!}{2\times3\times2\times3\times2\times3}$ ways similarly.
So, $N=9!\left(\frac{1}{2\times9}+\frac{1}{2^2\times4\times5}+\frac{1}{2^2\times3\times6}+\frac{1}{2^3\times3\times3\times3}\right)$
$\Longrightarrow \boxed{N=31416}$
In the 4th case, we need to divide by $3!$. And the rest are correct. And don't forget to divide $N$ by 1000 to find the remainder!
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Anindya Biswas
Posts: 196
Joined: Fri Oct 02, 2020 8:51 pm
Contact:

### Re: A Combi problem

Mehrab4226 wrote:
Thu Apr 08, 2021 12:33 pm
Anindya Biswas wrote:
Thu Apr 08, 2021 11:22 am
If we transform the handshaking into a graph where the people are vertex and handshakes are represented by edges, we will get one or more disjoint cycles. Each cycle must have at least $3$ people so that everyone shakes hand with two other.
So we have $4$ cases.
1. We can take all of the people and put them in a cycle of length $9$.
2. We can divide them into $5$-cycle and $4$-cycle.
3. We can divide them into $6$-cycle and $3$-cycle.
4. We can divide them into three $3$-cycles
For the first case, this is just cyclic permutation and it can be done in $\frac{9!}{2\times9}$ since rotation and reflection results in same handshaking.
For the second case, we can divide $9$ people into group of $5$ people and $4$ people in ${9\choose4}=\frac{9!}{4!\cdot5!}$ ways. For each grouping, there are $\frac{5!}{2\times5}\cdot\frac{4!}{2\times4}$ ways to put them in the cycles. So, by multiplying this two results, we get total $\frac{9!}{2\times4\times2\times5}$ ways

Similarly, for the third case, there are total $\frac{9!}{2\times3\times2\times6}$ ways to do that.

And for the fourth case, there are just $\frac{9!}{2\times3\times2\times3\times2\times3}$ ways similarly.
So, $N=9!\left(\frac{1}{2\times9}+\frac{1}{2^2\times4\times5}+\frac{1}{2^2\times3\times6}+\frac{1}{2^3\times3\times3\times3}\right)$
$\Longrightarrow \boxed{N=31416}$
In the 4th case, we need to divide by $3!$. And the rest are correct. And don't forget to divide $N$ by 1000 to find the remainder!
$N=9!\left(\frac{1}{2\times9}+\frac{1}{2^2\times4\times5}+\frac{1}{2^2\times3\times6}+\frac{1}{2^3\times3\times3\times3\times3!}\right)$
$\Longrightarrow N=30016$
So, answer should be $16$. Hoping that this time it's correct!