Don't get dizzy on the circular train

Posted August 4, 2019

This week, FiveThirtyEight's Riddler Classic is a puzzle about finding the size of a circular train. It came from Ben Tupper. Here's the puzzle:

You find yourself in a train made up of some unknown number of connected train cars that join to form a circle. It's the ouroboros of transportation. Don't think too hard about its practical uses.

From the car you're in, you can walk to a car on either side — and because the train is a circle, if you walk far enough eventually you'll wind up back where you started. Each car has a single light that you can turn on and off. Each light in the train is initially set on or off at random.

What is the most efficient method for figuring out how many cars are in the train?

(Assume that you can't mark or otherwise deface a train car, and that each car's light is only visible from within that car. The doors automatically close behind you, too. There are only two actions you can take: turning on or off a light and walking between cars.)

This puzzle embodies one of my favorite parts of math: its open-endedness. The puzzle does ask a specific question, but even if it didn't, my curiosity would still tend in the same direction, and I might find myself interested in other questions as well. Even as stated, the puzzle is vague in a wonderful way; it leaves the reader to decide what makes a method "efficient." Here are a few options:

1. What is the minimum distance you need to walk to determine the number of cars with high probability (say, 99%)?
2. What is the minimum distance you need to walk to determine the number of cars with 100% certainty?
3. What is the minimum number of switches you need to flip to determine the number of cars with certainty?

These questions are related but each uses a slightly different approach. We'll look at them one by one.

I'll mention one other itch this puzzles scratches: I like problems where you have to measure complexity in settings that are made more confusing by symmetry. (This is the essence of the Ph.D. thesis I'm currently feverishly working to finish, one could say.) "Complexity" means meassuring something like "how far" or "how long" or "how many switches." The symmetry here is that all the train cars look alike. Symmetry can be a beautiful thing, but here it is the enemy; if all the train cars looked different from one another, this problem would be a lot easier.

1. Once around the train

Let's start with question 1: If we're willing to be wrong with probability 1%, how far do we need to walk (measured in how many times we need to step from one car to another)? Allowing ourselves to be wrong occasionally will save us a lot of time; we'll see in the next section that there are some pathological cases where we might be fooled, but they are unlikely, so we won't worry about them.

Still, we'll need to make at least one full loop around the train. Here's why: Let's say we take some number of steps (five maybe) around the train, and don't get back to where we started. How many cars are in the train? Maybe its six, and we're almost all the way around. But maybe it's a million. We have no way to distinguish between these situations.

So here's our plan: Let's put the light on in the car we start in, and then start walking around the train in some direction. Every time we enter a new car, we flip the light out. Eventually, we get all the way around the train, and get back to the car we started in, where we left the light on.

When we get to that car, we'd like to stop there, count our steps, and announce the number of cars in the train. But of course, when we enter a car and see the light on, that doesn't mean that we're in the starting car; we may be in some new car we haven't seen before, which just happens to have its light on by random chance.

But, let's say we see a car with its light on, and keep walking. If the next several cars have their lights off, it's less likely that that happened by random chance, and more likely that we have indeed gotten back to the start and are now entering cars where we already turned the lights out.

Here's when to stop, more precisely: If you get to car \(N\) and find the light on, walk through an additional \(10 + 2 \log_2 N\) cars. If all those lights are off, you can declare that the train has \(N\) cars. Doing this, you will never give an answer that is too high, and the probability that you give an answer that is too low is at most \[ \sum_{m = 1}^{N - 1} (\text{prob of guessing } m \text{ incorrectly}) \leq \sum_{m = 1}^{N - 1} \frac{1}{2^{10 + \lfloor 2 \log_2 m\rfloor + 1}} \leq \frac{1}{2^{10}}\sum_{m = 1}^{\infty} \frac{1}{2^{2 \log_2 m}} = \frac{1}{2^{10}} \sum_{m = 1}^{\infty} \frac{1}{m^2} < 0.01. \] (The last inequality is courtesy of the Basel problem.)

So, the total distance we need to walk can be summarized as once around and a little bit more.

2. Back around the train

If we want to be absolutely sure of the number of trains in the car, walking once around the train is not enough. In fact, as long as we keep walking in one direction, we'll never know if we've gotten back to where we started. We could get somewhere that looks familiar, but could actually be a totally new part of the train that has the same lighting pattern by chance.

The only way to be sure of the size of the train is to observe one car, walk all the way around the train until we get back to that car, flip the light switch, and walk all the way back to check that the light in the original car has indeed changed state. If someone tells you that the train has \(N\) cars, you can verify they are telling the truth by following this strategy, and in total you'll walk around the train twice (all the way around once in one direction, and then back the way you came).

Unfortunately for you, nobody is going to just tell you how many trains are in the car, so this is going to be a little bit more work. For \(k = 3, 4, 5, 6, \ldots\), do the following: Walk out \(2^k\) steps around the train, turning off all the lights as you go. When you get to the end of this walk, turn the light on, and walk back the way you came. If on the way back you come to a car with its light on, you must have walked all the way around the train, so you can answer the number of cars. Otherwise, move onto the next value of \(k\). Eventually, \(2^k\) will be more than the number of cars in the train, and you will be done.

You can optimize this a little further: As you are doing the "walking back" portion for one value of \(k\), you can simultaneously be starting the "walking out" portion for the next value of \(k\). In the worst case, if there are \(N = 2^\ell + 1\) cars in the train, you will walk a total distance of \[ 2^3 + 2^4 + 2^5 + \dots + 2^{\ell + 1} + N \approx 5 N \] car lengths.

So, in the worst case, you will walk approximately five times around the train.

3. Heavy light switches

Maybe you are an avid walker, so don't mind doing many laps around the train, but when you go to flip a light switch, you find it heavy and sticky and making a horrible screeching noise. You would like to minimize the number of switches you need to flip. Let's suppose you also have a very good memory.

In that case, here is the plan: Walk around the train in one direction for quite a long distance, memorizing the state of the light in each car as you go. When you've gone good and far, flip one switch, and walk back the way you came. If you get back to a car whose light is not in the state you remember it being in, you must have walked all the way around the train once, so you can give an answer. If not, you must not have made it all the way around the train yet. Try again, but walk even further.

You can bring the number of flips as low as you want, if you have enough patience and endurance. Specifically: Let \(f(N)\) be a function that outputs the number of light switches you would be willing to flip (at least one) to figure out that there are \(N\) cars in the train. You can choose any \(f\) you want, so long as \(f(N)\) goes to infinity as \(N\) goes to infinity. For example, you could choose \(f(N) = \log \log \log \log N\) (for large \(N\)). It's possible to keep the number of flips to the number specified by \(f\) by following the above strategy.

In summary, you can flip as few light switches as you like.