Problem:
Let be the number of permutations of the numbers such that the ratios for are all distinct. Prove that is odd for all .
Solution:
For any permutation there is an inverse permutation where we define if and only if . Then the ratios for the permutation are , hence the reciprocals of those for the permutation . Thus we see that has distinct ratios if and only if does. In particular, modulo is the same as the number of permutations which are equal to their own inverse and have distinct ratios.
A permutation is its own inverse if and only if it can be formed by breaking the numbers into singletons and pairs and defining if is a singleton and if is a pair. Any singleton gives a ratio of 1 , so the distinct ratio condition forces there to be at most one singleton (and hence, there is one singleton if is odd and none if is even). Thus we see that , where is the number of ways to form disjoint pairs of elements of such that no pair forms the same ratio as any other pair. (To avoid ambiguity, interpret "the ratio of a pair" to mean the ratio of its larger to its smaller element.)
Note that for any set of disjoint pairs of elements of , if we have two pairs with the same ratio, say and with (or equivalently ), then replacing and with and gives another such pairing. Accordingly, refer to a pair of pairs satisfying as a potential swap. Notice that this move is reversible: we can apply it to potential swap to get to potential swap , and vice versa.
Now build a graph whose vertices are sets of disjoint pairs of elements from , and where two such pairings are connected by an edge if they differ by simultaneously applying the move above to some non-empty collection of (disjoint) potential swaps. This graph has vertices, hence an odd number of vertices. (The notation means , where is odd. To see why this formula holds, note that for even , we have possible partners for the element 1 and then !! ways to pair up the remaining elements by induction. Then, for odd , we have choices for the singleton and ways to pair up the remaining elements.)
Moreover, is the number of isolated vertices of , since all pairs in a given pairing have different ratios if and only if there are no potential swaps.
Whenever we are given a set of pairs all with the same ratio, then we can form disjoint potential swaps from among these pairs in ways. (For , we define .) Hence, the total number of ways to choose disjoint potential swaps from these is
Thus the number of choices (including the empty choice of no potential swaps) is even. More generally, if we are given a set of pairs, for which at least two of them (but not necessarily all) have the same ratio, then the number of ways to form disjoint potential swaps from them is again even: we can arrange the pairs into groups of pairs having the same ratio, and the desired number is just the product of , as ranges over the sizes of the various groups. Thus, for any collection of disjoint pairs from , if the pairs do not all have distinct ratios, then the number of ways of constructing zero or more disjoint potential swaps among these pairs is even. Excluding the empty choice, we see that every non-isolated vertex of has odd degree. Thus, can also be described as the number of vertices of of even degree.
However, by the handshake lemma, any finite graph has an even number of vertices of odd degree. Thus, , having an odd number of vertices, also has an odd number of vertices of even degree. That is, is odd and hence so is .
The problems on this page are the property of the MAA's American Mathematics Competitions