[bonanova]

Given that ...

1. Twenty-five Robots, all named after BrainDenizens, are placed at random on a set of rails 1 mile long.
   
2. The robot named Prime is the thirteenth robot from the North end of the rails.
   
3. Each robot faces North or South with equal probability, and travels in the direction it faces.
   
4. When two robots meet, they are unable to pass, so they simply turn around.
   
5. When a robot reaches an end of the rail, it falls off and goes to sleep.
   
6. All robots travel at a uniform speed of 1 mile/hour.
   

How long does it take before we can be certain that Prime has begun his nap?

Only half credit is available for those who resort to infinite series.

[Guest]

1 hour - that's an UN-educated guess

Like trivial persuit it is either one, none or never - but actually 13 could also be thrown in on this case

[Guest]

1 hour

Suppose each robot carries a flag. When it bumps into another robot they swap flags. In this way each flag will continue moving in the same direction uniformly at 1 mile per hour. So no robot will ever be without a flag and no flag can remain on the track for more than 1 hour. Engineering it so that Prime gets the last flag (which made its way from one end to the other) should be easily doable*.

*EDIT: I suppose that's only half an answer, I have to prove it isn't less than an hour. OK here goes, from the north end put 13 robots facing south then 12 facing north. Momentum is conserved so there will always be 13 robots going south and 12 going north, and at the end of all the bumping the south-going ones will all be south of the north-going ones. Since the robots cannot change order the middle one (Prime) must start and end going south. Also each flag travels at constant speed so the south-going flags will stay in the same order. So Prime must end up holding the last south-going flag (the one from the northernmost robot). Provided that flag started right at the north end that flag will take exactly an hour to get to the south end (yawn, still that bit had to be done).

[Guest]

With 25 robots and Prime being right in the middle (13th) it will take the longest in falling of the rail and falling asleep.

suggesting the longest possible time it will take for Prime to fall off, I have made it as difficult as possible for each robot to fall of by putting all those that are closest to South face North and those closest to North face South, with it does not matter which side he face because he is in the middle.

Beginning movement for Prime to reach his first robot it will take half an hour, causing all the robots behind it to turn around until the robot at the back turns around and walks until it falls of the rail road.

The technical mathematics to figure out the time is so:

1/50 (of one hour) + 1/48 + 1/46....+ 1/2. It conveniently has 25 fractions to add together from 1/50 going up in 1/2's until one reaches 1/2.

This equtions ultimatley reaches 3,239.

Therefore Prime will have begun its nap, in absolute certainty in 3 hours and 24 minutes from beginnig of movement.

It might be wrong but I did not say infinity

[Prof. Templeton]

1 hour

Suppose each robot carries a flag. When it bumps into another robot they swap flags. In this way each flag will continue moving in the same direction uniformly at 1 mile per hour. So no robot will ever be without a flag and no flag can remain on the track for more than 1 hour. Engineering it so that Prime gets the last flag (which made its way from one end to the other) should be easily doable.

I agree with this explanation. Octopuppy also has a insightful way of looking at it.

The flags always travel in one direction, it would take at most 1 hour for all flags (and hence all robots) to travel the length of the rail.

[Prime]

1 hour

Suppose each robot carries a flag. When it bumps into another robot they swap flags. In this way each flag will continue moving in the same direction uniformly at 1 mile per hour. So no robot will ever be without a flag and no flag can remain on the track for more than 1 hour. Engineering it so that Prime gets the last flag (which made its way from one end to the other) should be easily doable*.

*EDIT: I suppose that's only half an answer, I have to prove it isn't less than an hour. OK here goes, from the north end put 13 robots facing south then 12 facing north. Momentum is conserved so there will always be 13 robots going south and 12 going north, and at the end of all the bumping the south-going ones will all be south of the north-going ones. Since the robots cannot change order the middle one (Prime) must start and end going south. Also each flag travels at constant speed so the south-going flags will stay in the same order. So Prime must end up holding the last south-going flag (the one from the northernmost robot). Provided that flag started right at the north end that flag will take exactly an hour to get to the south end (yawn, still that bit had to be done).

I cannot top this flag passing model. And I don't see a need for any additional proof. The OP stated "before we can be certain", which means what's the longest possible time. And no flag can stay on the rails longer than one hour. And it is possible (and probable) for Prime to be the last robot off the rail.

[Guest]

One hour at most.

Given n robots, the total collective distance cannot exceed n miles, and no one robot can travel more than one mile. Therefore, one hour at most.

To avoid relying on an infinite geometric series of collision distances, an inductive proof follows (times are in hours and each collision-reversal is assumed to be instantaneous):

Base case:

One robot's travel is maximized by beginning on one end and traveling to the other.

Maximum combined distance = 1 mile

Total time = 1 hour

Two robots:

Time and total distance are both maximized by placing one on each end, traveling toward each other. They collide in the middle, return to their origins and fall off.

Maximum combined distance = 2 miles

Total time = 1 hour

n robots:

One robot on S end moving N; n-1 robots together on N end moving S. Between all robots, n-1 collisions occur midway. In the end, one robot falls off N end, and n-1 robots fall off S end.

Maximum combined distance = n miles

Total time = 1 hour

n+1 robots: Given any initial arrangement of n robots, there is no way to position an n+1th robot such that the total distance traveled by all robots increases by more than one mile; proving that the greatest distance ANY one robot can travel is one mile, or one hour. Specifically, 24 robots can travel 24 miles at most over one hour at most; adding a 25th robot anywhere will result in no more than 25 combined miles, or one individual mile - one hour!

[Guest]

One hour at most.

Given n robots, the total collective distance cannot exceed n miles, and no one robot can travel more than one mile. Therefore, one hour at most.

To avoid relying on an infinite geometric series of collision distances, an inductive proof follows (times are in hours and each collision-reversal is assumed to be instantaneous):

Base case:

One robot's travel is maximized by beginning on one end and traveling to the other.

Maximum combined distance = 1 mile

Total time = 1 hour

Two robots:

Time and total distance are both maximized by placing one on each end, traveling toward each other. They collide in the middle, return to their origins and fall off.

Maximum combined distance = 2 miles

Total time = 1 hour

n robots:

One robot on S end moving N; n-1 robots together on N end moving S. Between all robots, n-1 collisions occur midway. In the end, one robot falls off N end, and n-1 robots fall off S end.

Maximum combined distance = n miles

Total time = 1 hour

n+1 robots: Given any initial arrangement of n robots, there is no way to position an n+1th robot such that the total distance traveled by all robots increases by more than one mile; proving that the greatest distance ANY one robot can travel is one mile, or one hour. Specifically, 24 robots can travel 24 miles at most over one hour at most; adding a 25th robot anywhere will result in no more than 25 combined miles, or one individual mile - one hour!

Hmm, that interests me. I don't see how it works as an inductive proof. If the combined distance travelled by n robots doesn't exceed n miles, that doesn't imply that no robot goes more than a mile (since some may go less than a mile). It is true that for 1 or 2 robots the time doesn't exceed 1 hour, so an inductive proof could follow if you can prove that n robots<=1 hour implies n+1 robots<=1 hour. Since adding another robot makes all the collisions different I don't see where that is proved. Though it's entirely possible I'm missing something. Can you clarify?

[unreality]

Does the answer change if only ONE side of the rail allows exit?

edit: when you hit the closed end, you would bounce off as if it were a robot

Edited November 1, 2008 by unreality

[peace*out]

Does the answer change if only ONE side of the rail allows exit?

I would think so...

[Guest]

Does the answer change if only ONE side of the rail allows exit?

edit: when you hit the closed end, you would bounce off as if it were a robot

There's a ceiling at 2 hours (since the "flag" can at most travel the length of the rail twice), but it would have to be less than that because there's no way robot 13 could be the last robot to fall.

[unreality]

Well in this case robot 13 isn't the longest to reach the exit, it would be the robot farthest from the exit (call them robot 1). So robot 1 would be the least ideal solution. You would continually bounce off robot 2, then the closed end, then robot 2, then the closed end, etc, until robot 2 has fallen off, then you march for the exit. Robot 2 will bounce off of robot 1, then 3, then 1, then 3, etc, or vice versa (depending on starting direction), until 3 has fallen off, then 2 will bounce off of 1 [maybe, depending on if robot 3 fell off when robot 2 was going toward robot 3 or toward robot 1], then fall off itself. And 3 won't fall off until 4 has fallen off, etc... 25 will be the first to fall off after (a) no collisions or (b) hitting robot 24, depending on starting direction

Hmm, I think this is actually harder than the OP. I'll think more about it in the shower

Edited November 2, 2008 by unreality

[bonanova]

Well in this case robot 13 isn't the longest to reach the exit, it would be the robot farthest from the exit (call them robot 1). So robot 1 would be the least ideal solution. You would continually bounce off robot 2, then the closed end, then robot 2, then the closed end, etc, until robot 2 has fallen off, then you march for the exit. Robot 2 will bounce off of robot 1, then 3, then 1, then 3, etc, or vice versa (depending on starting direction), until 3 has fallen off, then 2 will bounce off of 1 [maybe, depending on if robot 3 fell off when robot 2 was going toward robot 3 or toward robot 1], then fall off itself. And 3 won't fall off until 4 has fallen off, etc... 25 will be the first to fall off after (a) no collisions or (b) hitting robot 24, depending on starting direction

Hmm, I think this is actually harder than the OP. I'll think more about it in the shower

putting a mirror at the closed end of the rail.

Then it would look [and behave] like a two-mile-long-rail with twice as many robots, all obeying the same rules as before.

It really wouldn't matter that now there are two robots of each number.

The answer does not depend on the number of robots, only the length of the rail.

[unreality]

Wow, I never would have thought of it like that My guess was 2 miles, for a different reason though. Maybe both lead to the answer (2 miles). Cool

[Guest]

Hmm, that interests me. I don't see how it works as an inductive proof. If the combined distance travelled by n robots doesn't exceed n miles, that doesn't imply that no robot goes more than a mile (since some may go less than a mile). It is true that for 1 or 2 robots the time doesn't exceed 1 hour, so an inductive proof could follow if you can prove that n robots<=1 hour implies n+1 robots<=1 hour. Since adding another robot makes all the collisions different I don't see where that is proved. Though it's entirely possible I'm missing something. Can you clarify?

The proof was challenging to construct, and I agree it is a tough one to clarify. I think the best way to do this is to borrow from your flag model:

- Suppose x represents southbound robots, and o represents northbound robots. Given any initial configuration, x's and o's simply trade places at each collision, but each x and o maintains a constant velocity until it drops, as in the following sequence:

S-----------------N

1) o__o__x_x_x

2) _o__ox_x_x_

3) __o_xox_x__

4) __xo_xox___

5) _x_xo_xo___

6) x_x_xo__o__

7) _x_x__o__o_

8) x_x____o__o

9) _x______o__

10) x________o

11) __________

- All the x's and o's are mutually independent and don't change direction, velocity, or total count until dropping...they just pass right through each other like ghosts.

- Given n robots, the last one off the rail is represented by the x and/or o that traveled the farthest.

- So, given n robots, adding an n+1th robot merely means adding either an x or an o. But the total clearing time remains the same - one hour at most! This is so even though the total robot-miles change as n changes.

- Algebraically, the total robot-miles can be expressed independently of n, as follows:

t*(n robots)*1mi/hr <= n robot-miles

...reduces to,

t <= 1hr

n disappears!

[Prime]

There is one small point to clarify. Namely, exactly what's the distance traveled by Prime-robot before going off the rail.

From the initial setup, find the robot whose motion (flag) will be the last to collide with Prime.

For that consider all robots to the North of P, who move toward him (South) and all robots to the South of P who move toward P (North).

If the number S of such robots from the direction into which Prime originally moves is less or equal to the number of approaching robots from the other side, then take the Sth robot from the other side as the one whose flag Prime will carry off the rail and use as a blanket. Otherwise, if the number of robots N initially chasing Prime is less, then it is N+1st robot from the South side.

S--<-<-<--<-->--<-->-<-<--<-<--<---<P-->--<-<--->--<--<-<-<<<-<--<----N

<--------------------------------------------------------+

Prime robot travels exactly the initial distance between that robot and the edge towards which that robot was initially moving.

See it this way: while Prime-robot travels some distance bouncing back and forth; the final collision point has approached the same distance towards the edge off which Prime will go.

For the corrolary problem with one closed end, I want to note that putting mirror at the closed end would represent a very specific case of the original problem. The case where the number of robots is always even, and they are arranged in a symmetrical pattern.

[Izzy]

You're 96 hundred millionths of a second off. According to my calculations anyway. It took like 3 hours to draw, so even if I'm wrong, that hard work is not going to waste. Sorry if it's hard to read.

*edit* Original pics were crap. I had to re-take them.

Edited November 2, 2008 by Izzy

[unreality]

Everything is backwards

[Izzy]

Everything is backwards

Yeah, stupid iPhoto. I've fixed it now.

[unreality]

the .00000000002 (or whatever) below from 15 that made it 14.999999988 was almost certainly an error in human measurement

edit: Please don't take that the wrong way, I think what you did was awesome... but don't you think such a small decimal is probably a slight (uber-slight) measurement slip up?

Edited November 2, 2008 by unreality

[Izzy]

the .00000000002 (or whatever) below from 15 that made it 14.999999988 was almost certainly an error in human measurement

edit: Please don't take that the wrong way, I think what you did was awesome... but don't you think such a small decimal is probably a slight (uber-slight) measurement slip up?

Grah, as I was typing out some proof, I realized my mistake. <_< In my scale of 1 mile = 24 cm, .5cm = 0.02083333... of a mile, not 0.02, which is what I used. So the robots would travel .5 cm in 1 minutes 15 seconds.. If anything, I have the ultimate proof that it takes an hour?