Online Course Discussion Forum

2012 AIME II #14

 
 
WangDr. Kevin的头像
Re: 2012 AIME II #14
WangDr. Kevin - 2020年08月10日 Monday 00:01
 

Think of it as a graph theory problem.  Each person is a vertex, and if they shake hands, connect them with an edge.  Because every vertex has exactly two edges, the $9$ vertices are all in cycles of lengths at least $3$.  This fact is very easy to prove.

There are $4$ cases.  (1) $3$ cycles of length $3$. (2) $2$ cycles of lengths $4$ and $5$.  (3) $2$ cycles of lengths $3$ and $6$. (4) All $9$ vertices are in one big cycle.

In each case you have to choose the vertices in each cycle and count the circular permutations, remembering that reversing order does not count as a new arrangement.  Also, in case (1), the order of the $3$ cycles does not matter.