BasicCountingPattern AIME Difficult
2012


Problem - 238
  • 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 $N$.

We do case work by separating the nine people into some subgroups. People in different subgroup do not shake hands. By the requirement, no subgroup should have less than three people. Thus, there are totally $4$ possible cases: $3-3-3$, $3-6$, $4-5$, and $9$.

We also note that within each of such subgroups with more than four people, no two people will shake hands with the same two other people. This is because otherwise these four people can create another sub-subgroup. Therefore, for a $N$-people subgroup, we can imagine they sit in a round table and each person will shake hands with his two neighbors. It follows that there are $\frac{(N-1)!}{2}$ handshaking arrangements by the round-table pattern.

  • $3-3-3$: There are totally $\frac{C_9^3\times C_6^3\times C_3^3}{3!}=280$ different ways to create these three subgroups. Then within each group, there is only one way to make handshaking arrangement. Therefore, the total count in this case is $280$.
  • $3-6$: There are totally $C_9^6=84$ ways to create these two subgroups. In the $3$-people subgroup, there is only one way to make handshaking arrangement. In the $6$-people subgroup, there are $\frac{(6-1)!}{2}=60$ different ways. Hence, the total count in this case is $84\times 1\times 60=5040$.
  • $4-5$. By the similar reasoning as int he previous case, the total count is $C_9^4\times\frac{(4-1)!}{2}\times\frac{(5-1)!}{2}=4536$
  • $9$: There are $\frac{(9-1)!}{2}=20160$ different ways.

Therefore, in conclusion, the total number of ways equals $$280+5040+4536+20160=\boxed{30016}$$


report an error