A Combi problem

For discussing Olympiad Level Combinatorics problems
User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh
A Combi problem

Unread post by Mehrab4226 » Tue Apr 06, 2021 9:41 am

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:
AIME:2012
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é

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: A Combi problem

Unread post by Anindya Biswas » 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}\]
Seriously? That's the answer?? :o
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: A Combi problem

Unread post by Mehrab4226 » 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}\]
Seriously? That's the answer?? :o
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é

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: A Combi problem

Unread post by Anindya Biswas » Thu Apr 08, 2021 12:51 pm

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}\]
Seriously? That's the answer?? :o
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!
Yes! Thanks for pointing that out.
\[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

Post Reply