train wagons

[Zapp]

How do you know that you are not at the beginning?

as I said, disrupt the pattern after a few steps into the naturaly occuring pattern and go back to your starting position. if you have encountered a disruption in your pattern, then you know how many wagons there are.

[xander]

How do you know that you are not at the beginning?

as I said, disrupt the pattern after a few steps into the naturaly occuring pattern and go back to your starting position. if you have encountered a disruption in your pattern, then you know how many wagons there are.

But then you are employing exactly the same strategy that was originally proposed...

xander

[Zapp]

How do you know that you are not at the beginning?

as I said, disrupt the pattern after a few steps into the naturaly occuring pattern and go back to your starting position. if you have encountered a disruption in your pattern, then you know how many wagons there are.

But then you are employing exactly the same strategy that was originally proposed...

xander

well, yes, but it is faster in some cases, because you don't turn back if an anomaly with a 50% chance of occurence occurs, but after an anomaly with a 25% chance of occurence

[ironclaw]

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?

xander

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.

[qmod]

A faster method, which is easier to understand at least.

Original method (which everyone accepted)
T(n) = 2 * (1 + 2 + .. n) = n *(n+1)
steps.

New method: Instead of going 1 step each time, do 2^k steps and while going back to (1) if you see anything turned ON on the way you stop (Compare with don't look anywhere on the way until you reach (1))

T(n) = 2* (1 + 2 + 2^2 + 2^3 + .. n) = 4 n steps

So ideally you can speed aymptotically upto 2n+e steps.

[housey]

Just a quick thought, if we are using standard lightbulbs. Why not unscrew or smash [make it permanently off] the first lightbulb then count the number of wagons until you reach that first lightbulb again. Or was it meant to be a little more complicated than that?

[Zapp]

Just a quick thought, if we are using standard lightbulbs. Why not unscrew or smash [make it permanently off] the first lightbulb then count the number of wagons until you reach that first lightbulb again. Or was it meant to be a little more complicated than that?

genius.

[Ekuurh]

Spoiler! :

you start with a random light, and make sure it's on. you go to the next light that's on, remember how much you went, and turn it off. go abck the same number of steps, and see if the original is off. if it is, the number u remembered is the number of wagon, if not, repeat.

[Gary]

An interesting problem and solution. While this is a counting problem, I think solutions will be analogous to various sorting algorithms; something for one the computer people to look into.