train wagons

Have an interesting puzzle? Let's hear it!

Re: train wagons

xander wrote: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.
Q.E.D. , or not?
Zapp
University

Posts: 124
Joined: Thu Feb 10, 2011 3:49 pm

Re: train wagons

Zapp wrote:
xander wrote: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

xander
University

Posts: 154
Joined: Fri Feb 11, 2011 12:14 am
Location: Sparks, NV, USA

Re: train wagons

xander wrote:
Zapp wrote:
xander wrote: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
Q.E.D. , or not?
Zapp
University

Posts: 124
Joined: Thu Feb 10, 2011 3:49 pm

Re: train wagons

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?

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.
ironclaw
Kindergarten

Posts: 4
Joined: Thu Feb 10, 2011 4:32 pm

Re: train wagons

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.
qmod
Kindergarten

Posts: 3
Joined: Mon Feb 14, 2011 9:49 am

Re: train wagons

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?
housey
Kindergarten

Posts: 2
Joined: Tue Apr 26, 2011 7:56 am

Re: train wagons

housey wrote: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.
Q.E.D. , or not?
Zapp
University

Posts: 124
Joined: Thu Feb 10, 2011 3:49 pm

Re: train wagons

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.
There was an open question which i have asked many proffesors and fellow mathematicians, but none were able to answer:

Is there a function f:R->R (not necessarily continuous on ALL of R) which:
for every linear function g(x)=m*x+n, there is a number X for which g is the tangent of f in? (for each x g(x)=f(X)+f'(X)(x-X))
i think not.

(i almost solved it - using a small set theory tweak and a big topology tweak)
Ekuurh
Elementary School

Posts: 14
Joined: Tue Apr 19, 2011 12:28 pm

Re: train wagons

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.
Gary
Mathlete

Posts: 57
Joined: Mon Nov 07, 2011 10:49 am

Previous