Misplaced Priorities - Part 3
Puzzle for the week of 1/19/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/26/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!
This weeks puzzle is an extension of part 2 from last week. In that problem we asked how many 2 person swaps would be needed to correct a line of 10 people who’s order had been shuffled randomly. But this of course assumes that people stay where they’re supposed to once you move them! The particular group of people is antsy and chaotic so they frequently will move around despite your efforts to order them.
Our job is to figure out how many swaps on average are needed to order a line of 10 people that have been shuffled randomly where before each one of your swaps, a random swap will occur. Once you’ve successfully re-ordered the line of 10 people, the random swaps will stop (so the situation doesn’t go on indefinitely). How many swaps on average for a line of n people?
Good luck!
Please submit your thoughts, progress, or answers here.