October 2025
Explicitly compute \({\bf D}(\sigma)\) for all permutations in \(X_3\). Then try it for \(X_4\). What do you notice about the permutations satisfying \({\bf D}(\sigma) = 2\)?
See if you can argue that at most four integers in \(\{1,2,3,\ldots, n\}\) can satisfy \(\sigma(i) \neq i\). How must those integers interact with each other?
It may be helpful here to consider the path a single integer takes under repeated application of the permutation. For example, in the permutation \(\sigma\) denoted by \(58123764\), we can start with \(1\) and repeatedly apply the permutation. We get, \(\sigma(1) = 5\), \(\sigma(5) = 3\), \(\sigma(3) = 1\), and then the pattern repeats. We can denote this by \(1 \to 5 \to 3 \to 1\). Similarly, the path \(2\) takes is \(2 \to 8 \to 4 \to 2\).
For a permutation \(\sigma\) in \(X_{2k+1}\), think about how a \(\sigma\) that maximizes \({\bf D}(\sigma)\) must behave on the following three sets: \(\{1,2,\ldots,k\}, \{k+1\}, \{k+2,\ldots,2k,2k+1\}\).
See the hint for Question 4.