Source:
A Combi problem
- Mehrab4226
- Posts:230
- Joined:Sat Jan 11, 2020 1:38 pm
- Location:Dhaka, Bangladesh
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:
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é
-Henri Poincaré
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- 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.
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}\]
Seriously? That's the answer??
So we have $4$ cases.
- We can take all of the people and put them in a cycle of length $9$.
- We can divide them into $5$-cycle and $4$-cycle.
- We can divide them into $6$-cycle and $3$-cycle.
- We can divide them into three $3$-cycles
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}\]
Seriously? That's the answer??
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
— John von Neumann
— John von Neumann
- Mehrab4226
- Posts:230
- Joined:Sat Jan 11, 2020 1:38 pm
- Location:Dhaka, Bangladesh
Re: A Combi problem
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!Anindya Biswas wrote: ↑Thu Apr 08, 2021 11:22 amIf 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.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.
- We can take all of the people and put them in a cycle of length $9$.
- We can divide them into $5$-cycle and $4$-cycle.
- We can divide them into $6$-cycle and $3$-cycle.
- We can divide them into three $3$-cycles
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}\]
Seriously? That's the answer??
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é
-Henri Poincaré
- Anindya Biswas
- Posts:264
- Joined:Fri Oct 02, 2020 8:51 pm
- Location:Magura, Bangladesh
- Contact:
Re: A Combi problem
Yes! Thanks for pointing that out.Mehrab4226 wrote: ↑Thu Apr 08, 2021 12:33 pmIn 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!Anindya Biswas wrote: ↑Thu Apr 08, 2021 11:22 amIf 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.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.
- We can take all of the people and put them in a cycle of length $9$.
- We can divide them into $5$-cycle and $4$-cycle.
- We can divide them into $6$-cycle and $3$-cycle.
- We can divide them into three $3$-cycles
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}\]
Seriously? That's the answer??
\[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!
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
— John von Neumann
— John von Neumann