Misplaced Priorities - Part 2

Puzzle for the week of 1/12/25

Inspired by the Fiddler on the Proof (formerly The Riddler), X’s Puzzle Corner aims to produce a weekly puzzle for readers that enjoy math, probability, and algorithms. Please submit your solution! Solutions will be accepted until 11 pm the following Sunday after the puzzle is posted (in this case 1/19/25). While it isn’t required, I encourage you to opt to have your solution shared so that we all get the chance to see how others thought about and attempted the problem!

The answers of all those that volunteered their solutions will be posted around Wednesday at 10 am.

In many cases, I expect the readers will be better puzzlers than me so I make no guarantees the solutions are correct. I also make no promises about having worked out the solutions to the puzzles ahead of time so it may be the case that they’re very challenging. Part of the fun is finding out!

Recalling back to part 1, we were imagining schemes for boarding a plane. For one such scheme we needed the passengers to be ordered based on their seat but we found that they weren’t very good at ordering themselves correctly. This week we’re going to take the next step and have you sort them into the correct order.

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?

Good luck!

Please submit your thoughts, progress, or answers here.