Let . Compute the number of functions such that, for all and is not divisible by 3.
Solution
Since for all , each cycle in the cycle decomposition of must have length 1 or 3. Also, since for all , each cycle cannot contain two elements such that . Hence each cycle has exactly three elements, one from each of residue classes mod 3. In particular, belong to distinct cycles. There are ways to choose two other numbers in the cycle containing 1. Then, there are ways to choose two other numbers in the cycle containing 4. Finally, there are ways to choose two other numbers in the cycle containing 7. Hence the desired number of functions is .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.