Misplaced Priorities - Part 4
Puzzle for week of 1/26/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 2/2/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!
Recall that in the last three parts we were considering how to order passengers correctly in order to efficiently board a plane. You consider for a moment that maybe ordering the passengers isn’t worth it so you decide to analyze how quickly you can board the plane if the passengers are in a random order.
Let’s assume that we are boarding a rather strange and simplified plane with only one seat per row. Passengers are ordered randomly and each requires a fixed amount of time Δt to stow their luggage. Passengers can move between rows quickly enough that we can ignore the time it takes for them to move in the aisle. However, as we have all experienced, the aisles of planes are never large enough for you to get around someone who is stowing their luggage so if the person in front of you is in the middle of stowing, you must wait until they are done before you can proceed. The question is, how long does it take for a plane with 10 seats and 10 randomly ordered passengers to board. What about n seats and n passengers?
For extra credit, how long does it take to board a plane where the random order can be corrected with k transpositions where k can take the values 0, … , n-1? Fair warning; I’m unlikely to have a solution for this :)
Please submit your thoughts, progress, or answers here.