Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Strife26]

A number isn't always a number. Sometimes it's a couple of numbers next to each other.

[ed boy]

Here's one for you:

There an infinitely long train line, with a station every mile. Somewhere on this train line is a train. You are told the following:
-The train's speed is constant
-The train initially starts at one of the stations
-One hour later, the train passes through another station

You are tasked with finding this train. You are given a magical telephone that allows you, once an hour, to phone up a station and ask the station manager if the train is currently there. You are also, for the purposes of this exercise, immmortal, so you will be able to do a lot of phoning the stations.

How will you use the above to find a method for predicting which stations the train will visit, and when?

[Heliman]

Call the first station and ask how long ago the train left, and the # of hours equals the # of the station the train is at?

or failing that, Call a random train station, ask if the train was there before, and if not keep calling that train station every hour until it does.

[Criptfeind]

I think you can only ask if the train is there.

[rarborman]

Ask for the train's callsign, ask the callsign name station which way the train went, call station that it should be at time to direction.

Trains are very predictable.

[Ampersand]

I think you can only ask if the train is there.

In any case, I think I can come up with a good solution provided there is a way of knowing which direction the train was headed, but with so little information known about the train, the best you can do at this point is to call stations at random forever.

[Sowelu]

Train's speed is constant...So it doesn't slow or stop.

Well, look at the length of a train plus the length of a station; it's significant (if not necessarily large) compared to a mile.  So you've got that going for you.

My guess is that if you continually call stations at random, your probability of eventually catching the train, somewhere, within infinite time, isT+S where T is the length of the train in miles and S is the length of the station in miles.  Chances might be good that you never actually find it.  I'm sure I should probably be expressing this in sigmas or limits or something better like that but I don't know.

[ed boy]

You do not know which station the train starts at, or the one that it passes through at 1 hour.
You are only told if the train is at the station currently or not - you cannot ask if it has previously been at the statement.

There is a way to do it, and it is not guessing randomly.

[Darvi]

My solution -> Stop caring about that crap and start abusing your immortality to do something fun.

[Criptfeind]

Immortality does not sound that fun. What are you going to do? Take a long term position on stocks?

[Darvi]

No, I mean stuff like jumping of a cliff into jagged rocks or something. At least it's more fun that trying to waste an infinite amount of time on traintracking.

[ed boy]

My solution -> Stop caring about that crap and start abusing your immortality to do something fun.

As it so happens, you can think of nothing more fun than to hunt down this train. Oh, what a blast it will be.

[irmo]

How will you use the above to find a method for predicting which stations the train will visit, and when?

Spoiler (click to show/hide)

Pick a random station to be x=0.

Graph this in 2d space (t, x). The train's position is a line with slope either +1 or -1, and an unknown x-intercept (that is, at time t, it's at x=x0+t or x=x0-t). So you pick possible starting positions (x0) and slopes (+ or -) and each hour you call the station where the train would be.
At t=0, guess x0=0 and call station 0.
At t=1, guess x0=1, slope +, call station 2. This also rules out x0=3, slope -.
At t=2, guess x0=1, slope -, call station -1. This also rules out x0=-3, slope +.
At t=3, guess x0=-1, slope +, call station 2. This also rules out x0=5, slope -.
At t=4, guess x0=-1, slope -, call station -5. This also rules out x0=-9, slope +.
At t=5, guess x0=2, slope +, call station 7. This also rules out x0=9, slope -.
At t=6, guess x0=2, slope -, call station -4. This also rules out x0=-10, slope +.
At t=7, guess x0=-2, slope +, call station 5. This also rules out x0=12, slope -.
At t=8, guess x0=-2, slope -, call station -10. This also rules out x0=-18, slope +.
At t=9, guess x0=3, slope +, call station 12. This also rules out x0=21, slope -.
At t=10, guess x0=3, slope -. Except that's already ruled out! As is x0=-3, slope +.
So skip to x0=-3, slope -, call station -13. This also rules out x0=-23, slope +.
Then resume the pattern.
At t=11, guess x0=4, slope +, call station 15. This rules out x0=26, slope -.

Even if you don't skip the ones that are already ruled out, you're guaranteed to check each position x0 in both directions at or before t = 4*|x0|. This will eventually find the train, though it could take arbitrarily long to do it.

(Of course once you find the train, your next call is to a station next to that one, and either the train's there or it's not. You now know its direction.)

[ed boy]

How will you use the above to find a method for predicting which stations the train will visit, and when?

Spoiler (click to show/hide)

Pick a random station to be x=0.

Graph this in 2d space (t, x). The train's position is a line with slope either +1 or -1, and an unknown x-intercept (that is, at time t, it's at x=x0+t or x=x0-t). So you pick possible starting positions (x0) and slopes (+ or -) and each hour you call the station where the train would be.
At t=0, guess x0=0 and call station 0.
At t=1, guess x0=1, slope +, call station 2. This also rules out x0=3, slope -.
At t=2, guess x0=1, slope -, call station -1. This also rules out x0=-3, slope +.
At t=3, guess x0=-1, slope +, call station 2. This also rules out x0=5, slope -.
At t=4, guess x0=-1, slope -, call station -5. This also rules out x0=-9, slope +.
At t=5, guess x0=2, slope +, call station 7. This also rules out x0=9, slope -.
At t=6, guess x0=2, slope -, call station -4. This also rules out x0=-10, slope +.
At t=7, guess x0=-2, slope +, call station 5. This also rules out x0=12, slope -.
At t=8, guess x0=-2, slope -, call station -10. This also rules out x0=-18, slope +.
At t=9, guess x0=3, slope +, call station 12. This also rules out x0=21, slope -.
At t=10, guess x0=3, slope -. Except that's already ruled out! As is x0=-3, slope +.
So skip to x0=-3, slope -, call station -13. This also rules out x0=-23, slope +.
Then resume the pattern.
At t=11, guess x0=4, slope +, call station 15. This rules out x0=26, slope -.

Even if you don't skip the ones that are already ruled out, you're guaranteed to check each position x0 in both directions at or before t = 4*|x0|. This will eventually find the train, though it could take arbitrarily long to do it.

(Of course once you find the train, your next call is to a station next to that one, and either the train's there or it's not. You now know its direction.)

Spoiler: That is wrong, because: (click to show/hide)

You are given that initially it is at one station and after one hour it is at another station. In your solution attempt, you assumed that the two stations are adjacent to each other, that is not necessarily the case.

[irmo]

Spoiler: That is wrong, because: (click to show/hide)

You are given that initially it is at one station and after one hour it is at another station. In your solution attempt, you assumed that the two stations are adjacent to each other, that is not necessarily the case.

Spoiler (click to show/hide)

The same logic applies. The train's velocity has to be some integer number of miles per hour, and its starting position has to be an integer number of miles from station 0 (wherever it's chosen to be). The set of pairs of integers (x, v) can be well-ordered: sort them first by |x|+|v|, and then within that by x, and then by v. Then you can check each (x, v) in order by calling station (x + v*t).
So at t=0, check (0, 0) = 0.
Then check (-1, 0), then (0, -1), then (0, +1), then (+1, 0).
Then (-2, 0), (-1, -1), (-1, +1), (0, -2), (0, +2), (+1, -1), (+1, +1), (+2, 0).
And so on. The terms of the problem rule out the v=0 cases, so skip those. But all of the possible (x, v) pairs are on this list.
Once you find the train's position, do something similar to determine its velocity: one hour later, call station x+1, then station x-2, then station x+4, then x-6, then x+12, and so on until you find the train again.