Maths Olympiad Prep

Library / IRL ABooklet /62 of 191

IRL ABooklet

Combinatorics Difficulty 5.5 AIME, harder Prove it Ireland

For n≥2n \ge 2, an n-spinner is a “fidget spinner” with nn identical arms and an angle of 360/n360/n degrees between pairs of adjacent arms. For instance, a 33-spinner and a 44-spinner are illustrated below:
Figure 1

We wish to place each of the numbers 1,…,nm1, \ldots, nm on the arms of an nn-spinner, with mm numbers placed on each arm, all equally spaced in a row. Some possibilities for (n,m)=(4,2)(n, m) = (4, 2) are illustrated below.
Figure 2

Since the first two can be obtained by rotation from each other, they are considered to be the same, and so we count the above as only two different placements. (The third is genuinely different because the “5” is closer to the middle than it is in the other two.) Counting in this manner, how many different placements do we obtain for given n≥2n \ge 2 and m≥1m \ge 1?

Solution

First, place the spinner so that the arm containing the number 11 is at the top. There, it can be put in any of the mm positions on that arm. This orients the nn-spinner and breaks the symmetry. The other nm−1nm - 1 numbers can now be placed in any other positions, so the answer is m(nm−1)!m(nm - 1)!.

Alternatively, we place all numbers as we wish, giving (nm)!(nm)! permutations. We then divide by nn since each placement can be rotated to nn different equivalent placements. Since m(nm−1)!=(nm)!/nm(nm - 1)! = (nm)!/n, the answers are consistent.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.