Misplaced Priorities - Part 2 [Solution]

Solution for the week of 1/12/25

Our problem from 1/12/25 was

Given that these queued passengers did such a poor job of getting into the correct order the first time, you don’t trust them them to get it right this time. So instead you have each of them display their ticket while you move them around. You can move people by selecting two people and swapping their locations. This is the only movement operation you’re allowed. If we assume there are 10 people in line and their order is completely random, how many swaps will it take to get them ordered correctly? How about for N people?

Shoutout out to Seth Cohen of Concord NH for his correct submission! He solved the problem by constructing a recurrence relation and then performing some algebra magic to obtain a closed-form solution. He found that the total number of swaps needed to correct all possible permutations is given by the relation

\(X(N+1) = X(N) + (N! + X(N))N\)

In his own words

Say we have N people. Person N+1 can be in any of N+1 positions.

• If person N+1 is last, the number of swaps is x(N).

• If person is in any other position, the number of swaps is (N! + x(N))*N. This equation comes from the explanation above: N! is every possible ordering of N people, each of which requires 1 swap to get person N+1 to the end; x(N) is how many swaps to get those N people ordered after N+1 is at the end; and N is the number of positions person N+1 could be, besides the last position.

After some algebra, Seth obtained the closed-from solution

\(X(N) = \frac{1}{2} + \sum_{i=2}^{N-1} \frac{i}{i+1}\)

After a little algebraic manipulation, we can confirm this is the same as the solution below!

I in turn solved it a different way and ChatGPT solved it yet a different (and much easier) way :/

The Hard Way

To solve this problem, we leverage the concept of derangements and the cycle decomposition of permutations:

1. Out-of-order elements: Individuals not in their correct positions form a subset of size k, which corresponds to a derangement (a permutation with no fixed points).

2. Cycle decomposition: Every permutation can be expressed as a product of disjoint cycles. For a derangement, all cycles must have length ≥2, as any cycle of length 1 would imply a fixed point.

3. Swapping to correct cycles:

   • A cycle of length k requires k−1 swaps to correct.

   • The total swaps needed for a derangement of size k is the sum of p−1 for each cycle p in the partition of k (the cycles have the size of the different parts of the partition).

4. Combining probabilities:

   • To compute the expected number of swaps E[S], we sum over all possible values of k (number of out-of-order elements), accounting for:

     • The probability P(k) of having k out-of-order elements.

     • The cycle structures (partitions of k).

     • The probability of each partition of k given k out-of-order elements.

More formally, let S be the number of swaps needed to correct a random permutation. Let P_k be the set of integer partition of k where every partition p is ≥2 and each partition p = {c₁, c₂, …} where c_i is a part of the partition p. Let K be be the event where k of the n elements of a random permutation are fixed. Finally, S(p) is the number of swaps needed to correct a derangement of k elements and is given by

\(S(p) = \sum_{c_i \in p} c_i - 1\)

With these formalizations, we can write the expected number of swaps as

\(E[S] = \sum_{k=0}^n \left[ \sum_{p \in P_k} S(p) P(p|K) \right] P(K)\)

P(K) was computed in part 1.

\(P(p|K) = \frac{k!}{\displaystyle \prod_{p \in P_k} p! \cdot \prod_{s \in \text{\{# partitions of size s}\}} s!}\)

Some additional details and code that computes these values is provided here.

The Easy Way

After finishing this problem, I asked ChatGPT to solve it out of curiosity. ChatGPT then informed me about a neat fact about the statistic of permutations. Apparently, the average number of cycles of length at least m in a random permutation is given by the sum of the harmonic numbers up to the m-th harmonic. Then, by noting that the number of swaps needed is simple n-c where n is the number of people in line and c is the number of cycles, we can easily compute

\(10 - H_{10} = 10 - \sum_{i=1}^{10} \frac{1}{i} = 7.07\)

After seeing this, I was curious if I could derive that fact from the approach I had taken. With a handy little choice of random variable I found from this video by Professor Roman Vershynin, it’s actually pretty easy. If you define a random variable Y_i associated with each element of a permutation and assign it a value of 1 over the length of the cycle it appears in, computing the expectation becomes pretty straightforward :) I’ve included the details here.

I hope you enjoyed this puzzle and please consider submitting a solution or providing feedback (a DM or comment works great)! I’d love for this series to morph into an interactive community where people work together and share ideas on challenging (but fun) puzzles.