xander wrote:You proposed solution depends upon being able to create a sequence of lights that you can recognize. Unfortunately, you cannot create such a sequence, as it could occur at random. Given a long enough train of wagons, any sequence of lights that are on and off could occur. How do you know that you are at the beginning of your sequence, rather than the beginning of a sequence that occurs later in the wagon train that looks like your sequence by random happenstance?
As an example, suppose that the train has 10 wagons in it, and the initial pattern of lights is 0000101010 (0 for off, 1 for on). You start by turning on the first light. You get to the fifth light, and your pattern starts again. How do you know that you are not at the beginning?
You are correct that you cannot know that you are not at the beginning without backtracking. However, every solution suffers from the same problem, because each solution must involve a step where you backtrack; my second solution is a modified version of my first solution, where we use an all-off sequence instead of an alternating sequence, and backtrack whenever we come to a wagon with the light off.
Perhaps there are faster solutions that use completely different strategies, but they must contain an instruction to backtrack at some point, and it is necessarily true at that point that you are uncertain whether you are at the beginning or not.
In other words, I agree that my solution has the undesirable property that you described, but I think that every solution must have the same property.
Here's how the second solution would deal with your example (0000101010):
Suppose that we require a 'depth' of 4 before we disrupt the pattern; that is, we must encounter a string of 4 on-off lights that we expect before we disrupt the pattern and backtrack. Then in this example we get to the 8th wagon, with the wagons in state "1010101010", and we disrupt the pattern at the 8th wagon to get "1010101110". We then backtrack to the 4th wagon, and see that the pattern has not been disrupted, so we continue in the reverse (i.e., left) direction. Eventually, we get to the fifth wagon, with the wagons in state "1010101010" again, and since we encounter and expected to encouter "1101" (from our reversed perspective), this satisfies our requirement for a depth of 4, so we disrupt the pattern there to get "1010001010". Then we backtrack in the forwards (i.e., right) direction, until we get back to the fifth wagon, and conclude with certainty that there are exactly 10 wagons.