In July’s puzzle, we pitched an unusual offer: unlimited airline tickets. But there was a catch — each destination would be a random choice of all destinations in the network. If you take the deal, how many flights should you expect to take before you return home?
The key was to imagine the winner taking a great many flights. In the above picture, you would fly to all airports with equal frequency, so your home airport should be the destination once every 25 flights on average. This means that, on average, there are 25 flights between home visits.
On first thought, it might seem we need a system of equations relating each airport in the network which we could then solve.
Happily, there are simpler ways to approach it.
For this approach, imagine taking many trips instead of just one.
Any given trip can be short (ex. home to Paris back to home) or long (ex. home to Djibouti to Madrid to Tokyo to Riyadh to Kuala Lampur to Djibouti to [300 more flights] back to home).
But what if the winner takes flights forever?
If we laid all the flights out in a line, we’d see random sequences of airports (gray circles) punctuated by the home airport (stars). Here’s an example of such a line (using only $6$ airports for simplicity):
In fact, this line contains all possible trips that our winner could take. so, the average spacing between stars is the expected length of a trip.
However, there’s no difference between the airports. This means that we should expect 1 of every 25 tiles in the line to be the home airport.
In other words, on average, every 25th flight should take them back home, making the expected trip length 25 flights.