Problem:
In a group of nine people each person shakes hands with exactly two of the other people from the group. Let 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 is divided by .
Solution:
For any particular method of conducting the handshakes, define a minimal cycle to be any subset of the people in which
no handshake occurs between a person in the subset and a person outside the subset, and
no proper subset has property .
For any particular method of conducting the handshakes select any one of the nine people, . Intersect all subsets of people both containing and satisfying condition . This intersection will satisfy condition and therefore will be minimal. It follows that for any particular method of conducting the handshakes, the set of nine people can be uniquely partitioned into minimal cycles.
The minimum size of a minimal cycle is , so the people can be partitioned into minimal cycles of people each, a minimal cycle of people and a minimal cycle of people, a minimal cycle of people and a minimal cycle of people, or a minimal cycle of people. Consider a minimal cycle of size . Select one person from this set. The two people with whom shakes hands (call them and ) can be selected in ways. The set being minimal implies that shakes hands with a fourth person (for ), shakes hands with a fifth person (for ), and so on, with the last person in the set shaking hands with . Thus there are methods of assigning the handshakes within this minimal cycle. When , and , the number of methods are and , respectively. It remains only to determine the number of ways the partitions can be formed.
The partition can be done in ways, the partition in ways, the partition in ways, and the partition in way. Thus the total number of methods is . , and the requested remainder is .
The problems on this page are the property of the MAA's American Mathematics Competitions