This is probably my favorite math problem. The solution requires no complex mathematics, but rather several separate, elegant insights. If you can't solve it, but think you have some insights to add, post them.

There is an irregularly shaped castle wall with 12 irregularly spaced guard towers around the perimeter. The towers may be evenly spaced; they may all be clustered together; they may be somewhere in between those two options. There is a guard at each tower. Each guard patrols the castle perimeter, walking at a pace that allows him to make a complete loop around the perimeter in exactly one hour. (Thus, all 12 guards walk at the same pace as each other.) At noon, each guard starts at his own station and begins to walk either clockwise or counterclockwise (to be determined randomly). Whenever two guards meet each other, they immediately each turn around and start walking back in the direction from which they came. Their turnaround is immediate and they lose no time in switching directions.

Prove that at midnight each guard is back at his original tower.

This would not work for odd N.

Proof: If guards simply passed each other rather than turning around, this would be true. Because turning around doesn't cost any time, the turning around rule doesn't change the positions at which guards are located at any moment (though it does change the identity of the guard at any particular position). QED.

Lemma 2: If Guard A begins at tower 1 and guard B begins at tower 2, where tower 2 is the next tower clockwise from 1, Guard B will, at the end of every hour, be at a tower one spot clockwise from that where guard A is.

Proof: No two guards can ever pass each other. Thus, the ordering of guards around the circle is never changed.

Thus, all we need to keep track of is which tower guard A is at at the end of 12 hours; so long as he is at the same tower where he began, all other guards must be as well. I'm not sure yet how to show that A ends up at tower 1. But here's another lemma that may be useful.

Lemma 3: Let each step in a clockwise direction count for +1 and each step in a counterclockwise direction count for -1. Suppose that the perimeter is K steps long. After each hour, the total step count must be JK, where J=(# of guards who start out clockwise)-(# of guards who start out counterclockwise).

Proof: Follows immediately from the logic of Lemma 1.

If all the guards walk in the same direction (whether clock- or counterclock-wise), they'll never bump into each other and will make exactly 12 complete loops in twelve hours, ending where they started.

Wait, hangon. If you have G1 and G2 walking in the opposite direction and they meet each other and immediately turn around, then you have G1 immediately replacing G2 on G2's path, and vice versa---the guard that turned around is always exactly in the position and traveling in the direction that would have been the position and direction of the guard he just bumped into. So, since from the paragraph above we know that the initial trajectory of each guard will take that guard back to his initial point in exactly one hour if not interrupted, we can conclude that even if interrupted, each guard will wind up at

sometower at the end of every hour.But so far I can't figure out how to find out which tower he'll end up at after each hour, nor how to prove that the tower at hour 12 equals the tower at hour 0. Does it have something to do with "tower" rhyming with "hour"?

Consider guard 1. he starts walking in one direction or the other (randomly). He will either bump into another guard, or he won't. If he doesn't, then he will make it all the way around back to his original tower in an hour, wearing hat #1.

If he does bump into another guard, they'll (1) switch hats, and (2) turn around. Note that now the other guard is wearing hat #1, and that since the other guard has "bounced" off of guard #1, HAT #1 is still progressing around the circle as if there had been no bump at all. The only difference is that hat #1 is now being worn by a different guard.

If this new guard wearing hat #1 makes it all the way around without bumping into another guard, then hat #1 will arrive back at tower #1 after one hour. If the new guard bumps into someone else, hat #1 will be handed off to the new guy, and hat #1 will continue making its way around the circle. Since all the guards walk at the same speed, in this manner hat #1, no matter how many bumps there are, will make it all the way around back to its original location after one hour.

. . .

When the guard reaches his original tower, does he stop or keep going?

1) Number the towers 1-12.

2) Each guard holds a piece of paper with the number of their tower on it.

3) As each guard passes another guard, they switch numbers but keep going.

I think we can agree this problem is equivalent if we prove every guard ends up with their original number.

As a result...

1) At the end of each hour, there is a guard at each tower, going in the same direction as they were originally but possibly with a different number.

2) The only difference between the state of the castle at each hour is the numbers the guards are holding. Everything else is the same.

The original permutation of the guards is (1 2 3 ... 10 11 12).

After the first hour, the permutation of the guards is a rotation of the original permutation, by Jesse's argument.

The permutation for each hour, however, is the same because nothing has changed but the number each guard is holding.

Consequently, the permutation of the guards after twelve hours is R^12, where R is the permutation every hour. Since R is a rotation, all rotations of twelve numbers restore the original order after twelve identical rotations.

Does that work?

But as for each hour simply repeating what happened in the previous hour (and thus rotating 12 times total), how do we know that that is true? We have no information about what direction the guards are walking after an hour; it could be different from how they started walking, and thus they will walk in a different pattern than they did for the first hour. Also, since the towers are not evenly spaced, if guards 1 and 2 leave towers 1 and 2 walking towards each other, this will have a different result than if they later leave towers 4 and 5 walking towards each other.

I don't think anyone has addressed this yet.

Aha---got it. Jesse points out "No two guards can ever pass each other. Thus, the ordering of guards around the circle is never changed." Since each guard will set out from a tower at the start of each hour on the path originally set out upon by the guard that occupied that tower at 12:00 noon, plus given the fact that the closest guard clockwise and the closest guard counterclockwise are the same guards at all times (Jesse's point) and they also start each hour at one tower, each guard moves clockwise or counter-clockwise some equal integer number of towers each hour. (There's no empty towers, and the order of guards never changes, so if one guard winds up X towers away, they all end up X towers away, in the same direction.) That number can be any integer, but at the end of 12 repetitions of this over 12 hours, the total number of towers shifted will be divisible by 12. Therefore, each guard will have shifted some integer multiple of the whole loop, and will be where he started.

The towers are NOT evenly spaced while the traversal rate is constant, therefore your lemma cannot be correct.

Picture towers 1-11 5 ft apart and tower 12 halfway between 1 and 11 on the other loop (each of which is, say, 49% of the total distance) -- you're saying that Guard 12 is at a tower at the end of each hour even though he can only traverse 1/12 of the distance in an hour, and has to go ~1/2 of the distance to find a tower)?

"Ever hear the old robot saying, 'Does not compute'?" - Bender B. Rodriguez, Futurama

Damn, twice in one day, and on the same post to boot.

*hangs his head in shame*

OK, it's a walk around the

perimeterin one hour, not 12 hours.I'm just going to shut up now.

I take back everything I said about Jesse's lemma, because I did not read the problem correctly.

Consider it this way: Irrespective of each guard, there is one pathway that continues in a continuous loop. That path is always occupied by

aguard (as shown above by many posters), but which guard it is isn't necessarily known. After each hour, that path has gone all the way around the loop and is starting out from where it was at noon. You can see that from the hats metaphor above; for any one guard, the point that would be reached by him and the direction he would be traveling if he continued uninterrupted after an hour (i.e., the same tower and the same direction), that point will be occupied and that direction taken by either that guard, or the first guard who bumps into him, or the next guard who bumps intothatguard, or the next guard who bumps intothatguard, and so on---but in any event, a guard.So after each hour, there is

aguard walking out of the same tower and in the same direction that some guard, whether the same or different, was walking at noon. So at the beginning of each hour, all the towers see a guard leave in the same direction they took at noon. Since the spacing of the towers doesn't change, and the pacing is always the same, if guards leave each tower in the same direction as they did at noon, then they'll just repeat the same bumps and turn-arounds as happened from noon to 1:00, in each hour.The critical fact is that at each hour, the guards must be displaced by the same amount. i.e. if guard 1 ends hour 1 in tower 2, then at the end of hour 2 he will be in tower 3, at the end of hour 3 he will be in tower 4, and at the end of 12 hours he will be back in tower 1.

The proof of this is as follows: As above, let the #steps in the perimeter equal K. In a hour, the net number of steps moved clockwise must equal JK, where J = # guards moving clockwise - # guards moving counterclockwise. Since the # guards moving in each direction never changes, JK is the same regardless in every hour.

Now, consider what happens if each guard finishes a particular hour exactly N towers away from his starting point. i.e. N=0 means you finish in the same tower you began the hour in, and N=1 means you finish one tower clockwise.

To do that, each guard must individually travel the distance between his/her starting tower (Tower M) and his finishing tower (Tower M + N). Now if N=1, it is clear that the sum of the distances travelled by the 12 guards must be K -- the perimeter of the castle. Likewise, for any N, the sum of the net distances travelled by the 12 guards must be NK.

We already know that the sum of the net distances is JK for every hour. Therefore, N=J, and every hour the guards end up exactly J towers to the right.

Since there are 12 towers and 12 hours, after 12 hours each guard will have travelled J*12 towers to the right == a multiple of 12 == back to his/her original tower.

If in some hour each guard moves N towers to the right, the guard starting at tower M must travel a net distance of Sum(k(M)..k((M+N)mod 12)). Summing over all 12 guards we get Sum(k(1) .. k(1+N)) + Sum(k(2) .. k(2+N) + ... + Sum(k(11) .. k((11+N) mod 12). Rearranging terms, this will give us:

Net Distance = N * k(1) + N * k(2) + N * k(3) + .. + N * k(11).

Since we know K=Sum(k(1) .. k(11)), we know the net clockwise distance travelled by all 12 guards must be NK.

Meanwhile, we know that the (#guards moving clockwise - # guards moving counterclockwise) = J is constant throughout the 12 hours. Therefore, the net distance covered by the guards in each hour is a constant JK. ==> N=J ==> if we begin with 8 guards moving clockwise and 4 moving counterclockwise, every hour the guards will advance by 4 towers.

Note that the directions the individual guards are travelling does not matter at all. In fact, as long as we keep the # of guards travelling clockwise and counterclockwise constant, we could randomly shuffle the directions of travel for each guard at each hour.

After hour one, there can only be two states of the world:

1. All guards went in the same direction, in which case they have all returned to their home towers.

2. The guards went in different directions, in which case at a minimum 1 guard returned to his home tower.

This is because the guard bumped into another and was able to return back from whence he came without a second bump. You cannot arrange the towers so that

allguards get bumped twice within an hour (try it!) and a guard who is bumped only once necessarily returns from whence he came.Now for the inductive step...

Again, there can only be two states of the world an hour later.

Either all of the guards are now travelling in the same direction, in which case they all return home.

Or they are not. In which case . . . and here's where I lose it.

At an attempt for extra credit, I think the number of positions rotated is equal to the number of people walking in that direction. 12 walking the same direction get back to their original destination every time. Imagine eleven are walking counter-clockwise and one clockwise, then each counter-clockwise guard as they hit the original path of the clockwise guard will follow that path until the path of the guard behind them is hit, rotating the whole bunch of them one position clockwise by the end. The same sort of thing happens when there are two walking clockwise, only twice and potentially more complicated.

The insight that guards never pass each other is useful, as is the fact that we know what the answer has to be, and get to reason backward from that.

Personally, I find it easier to work on the problem keeping in mind that we might as well treat the castle as a circle with irregularly spaced points of interest; the wall may be irregularly shaped, but that's irrelevant to the paths traced. More advanced demonstrations of this sort of irrelevancy are why a donut is topologically the same as a coffee cup, and why I never became a mathematician.

Since we'll need to measure distances in two directions around a circle, I'll call AB the distance from A to B clockwise, and BA the distance from B to A clockwise, i.e. the distance from A to B counterclockwise.

I see three cases to examine, depending on how the random decisions of walking directions go.

If everyone walks clockwise, or counterclockwise, the answer is trivial.

If equal numbers walk in opposite directions, it works because each guard walks in oscillations around his tower. In the simpler case with two guards walking in opposite directions from towers A and B, each of them will meet up half-way between A and B in one direction, and then half-way between the two towers in the other direction. Since A and B are points on a circle, the two points equidistant from them must be endpoints of a diameter - a path from one such endpoint to the other will cover half the circumference. So, each guard covers half the circumference of the castle twice, ending up in his original tower. Looking at the numbers, A travels 1/2AB(bump) + 1/2AB + 1/2BA(bump)+ 1/2BA - or a distance equal to AB + BA, the whole circle.

If there are more than two guards (still even numbers of guards, still equal numbers of guards moving in opposite directions) you get the same phenomena but with more frequent iterations.

The third case, where there are odd numbers of guards moving in any given direction (11-1, 9-3, 7-5), needs more thought, and this post is too long already.

For example, guard a at post 1 will spend 6 hours walking away from post 1 and six hours walking back towards post 1 and at the end of 12 hours will be back at the post in started. Guard 2 at post b will be the guard that meets him and turns around at the same time. So he will walk away from post 2 for 6 hours and back towards post 2 for 6 hours.

Meanwhile, guard 3 will leave post d walking towards post E and guard 4 will leave E towards d. Each of them will spend half ot their time walking towards their post and half walking back towards their origninal post.

It does not matter that the distances are different.

If the distance are different they will turn around a different number of times, but they will still spend 6 hours walking away from their original post and 6 hours walking towards their original post and all end up 12 hours later exactly where they started.

I just lucked out in immediately getting the right mental picture.

It's not necessarily true that a guard who gets bumped will get bumped at exactly 12:30, even if the rest of your assumptions are true. Therefore his post-bump travel won't necessarily be the opposite of his pre-bump travel.Actually, I think it is necessarily true that he gets bumped before 12:30, by the momentum logic described above.

somewherein the initial arrangement of guards is one moving in the opposite direction from our one-bump guard. Since momentum is conserved, and since it travels at a full perimeter per hour, our one-bump guard must necessarily encounter its opposite before it is 50% of the way around the perimeter.1. There are 12 guards

2. At the end of the first hour, each guard is at a post, but not necessarily his/her own.

3. The order of the guards remains the same, since they cannot pass one another.

4. Therefore, the guards have shifted n towers in a clockwise direction, where n is an integer 0 through 11)

For each hour thereafter, the shift reoccurs -- another n towers.

After 12 hours, each guard has shifted 12n towers. In this instance, n is equal to the number of times the shift has circled the castle, placing the guard back at their own tower.

1. There are 12 guards

2. At the end of the first hour, each guard is at a post, but not necessarily his/her own.

3. The order of the guards remains the same, since they cannot pass one another.

4. Therefore, the guards have shifted n towers in a clockwise direction, where n is an integer 0 through 11)

For each hour thereafter, the shift reoccurs -- another n towers.

After 12 hours, each guard has shifted 12n towers. In this instance, n is equal to the number of times the shift has circled the castle, placing the guard back at their own tower.

Here is how I explain the solution to people:

1) Note that since every time guards bump into each other they change directions, two guards cannot pass one another. Thus, at all times (at the end of one hour, at the end of 12 hours, always), the guards will be arranged in the same order as when they started, but perhaps rotated and spaced differently.

2) Pretend that instead of two guards reversing directions, they simply crossed each other. In this case, it is clear that after every hour, each guard will end up back at the station he started at, since he will have walked a complete circle without interruption. Ignoring the identity of the guards (i.e., thinking of Alice and Bob just as Guard and Guard), this tells us that _a_ guard will end up back at each tower at the end of each hour.

3) Imagine that every guard leaves his station in a random direction, and carries a placard that says what direction he is walking ("clockwise" or "counterclockwise"). Every time two guards bump, they each reverse direction, so let's say they also switch placards. Thus, the placards never stop moving in a perfectly smooth circle. Therefore, if a placard reading "clockwise" leaves a tower at the beginning of an hour, it will arrive back at that tower, going in the same direction, at the end of the tower. Thus, the person leaving any given tower at the start of any hour is moving in the same direction as the person who left that tower at the start of this whole exercise.

4) Combining 1 and 2, we know that after one hour, the whole orientation of the guards has simply rotated by some number of towers. I.e., every guard is now x towers to the right of where he started, where x is a number from 0 to 11. Facts 2 and 3 tell us that after each hour, the guards (ignoring their identities) are oriented as they were at the start of the first hour. I.e., there is a guard at every tower, and the guard at each tower leaves in the same direction as the guard who left at the beginning of the first hour. Thus, since all the initial conditions are the same at the beginning of each hour, all the crazy bumping and moving will also be the same. So, each hour repeats what happened in the first hour. Thus, after 12 hours, each guard has moved 12x towers from where he started, which puts him right back where he began.

Then people are only moving left, they move at a rate of 1 full rotation every 1/2 hour, and the towers allign with their original positions every hour. People only get bumped to the left. Each left moving excitation hits every stationary excitation twice in 1 hour, inducing 2 switches per excitation. Every time there is a bump the guards shift to the left by one position (all guards do as they maintain their ordering as proved above). So if n people are moving left then the ring shifts by 2n positions.

As a corrollary to the extra credit problem what is the minimum number of hours needed for all guards to return to their original positions? (hint its less than 12). Provide a proof :) How about for arbitrary n?

That

isthe math. The rest is arithmetic.1. I think the guards *do* have to be at a tower at the end of each hour, regardless of the spacing of the towers. It seems counter-intuitive to say that but if we use the "switching hats" metaphor then it's clear every hat makes a full trip around the wall to its starting point every hour. If every hat is back in its own tower every hour then every guard must be in a tower too.

2. Also going with the "switching hats" metaphor, it's clear that each hat goes either clockwise or counter-clockwise around the perimeter. Since the order of the guards never changes, the chain-of-possession for each guard's hat only has two possible "routes" through the other guards. For example, Guard 1's hat will travel a path of either:

a: 1-12-11-10-9-8-7-6-5-4-3-2-1

or

b: 1-2-3-4-5-6-7-8-9-10-11-12-1

I don't know how to prove, however, that those last "hand-off's" are the ones immediately before midnight, returning the hat to its original guard. There must be a simpler proof than this.

1. The order of the guards relative to one another cannot change because no guard ever passes another.

2. There must be a guard at a tower at the end of each hour because of the principle of conservation of guard momentum. The guard will be headed the same direction as the guard that began in that tower for the same reason.

3. Each guard is thus displaced by the same number of towers (n) in the same direction each hour.

4. At the end of 12 hours each guard will move n spaces in the same direction 12 times.

5. The guard will thus make n rotations, and wind up in his original position.

I note that although I'm not sure where the error is in all the math above, the number n is not equal to the clockwise - counterclockwise guards. I only know this because I worked it out for a configuration of guards where there only one was going counterclockwise, and the displacement was 2 stations. (Its useful to imagine the guard houses as positions on a clock face, and the guard speed as 1 second per minute.

Will each guard be back at his own tower at 6 pm?

I have an answer which I'll give soon.

Here's how I was thinking about it. Let's say that, halfway around the perimeter from each tower is its "shadow tower". Basically, Kevan's argument all applies if we look at things every half hour, rather than hourly, except each half hour we switch between regular towers and shadow towers (so guards are in a shadow tower at half past the hour and in a real tower on the hour). Thus, after 12 half hours, everyone is back in their original tower or its shadow tower by Kevan's argument, and since it is 6:00 on the hour, they are in the real towers, not the shadow towers.

Here's the argument with a little more detail. First, at half past any hour, each guard is at a shadow tower (which is easy to see if you think in terms of the positions of the hats, which pass between guards who bump and thus travel with constant speed and direction around the perimeter). Thus, each half hour there is a permutation and switch between real and shadow. Further, since guards do not pass each other, their order remains the same, so the permutation is a rotation. The directions a guard takes coming out of shadow tower X on the half hour is the same that the guard coming out of tower X took half an hour ago, which we see by following the hat (or the placard), so each half hour the permutation is the same rotation. After 6 hours, there have been 12 rotations and 12 flips between real and shadow, so the guards are back at the original, real tower where they started.

Starting with my earlier proof...

If you look at every pair of guards in which one guard is going clockwise and one is going counter-clockwise, then the two guards in each pair pass each other twice, meaning they change numbers twice.

That means that the permutation is even, since there are an even number of transpositions. Rotation by an odd number of an even number of elements is an odd permutation, which is impossible.

Therefore, each hour, the guard positions must rotate by an even number of towers, guaranteeing that they will return in six hours.

This logic doesn't hold for an odd number of towers, since rotation by an odd number of an odd number of elements is still an even permutation.

-Mev

And note, everyone returns at 12 no matter how irregular the positions of the towers are -- there are no shadow towers etc.

Note also that it would work even if you randomly shuffled the directions each hour, as long as the total # of guards going in each direction is constant.

What do you think of my proof that the rotation is even for even towers/guards?

-Mev

so guards do not pass each other twice.

This is a CLOSED system of wavelength P. Its behavior is quantized into 12 waves of differing frequency, wavelenght and direction but with constant wave velocity P/hr. The wave will not decay due to the No Pass Rule (lossless and frictionless collisions). Now anyone care to solve this mathematically. Hint Hint.

Mev's argument and Drewsil's argument give the same result, if my shadow towers argument is hard to follow.

1) All guards start in the same direction. In this case, after 12 hours of marching at the given pace, all guards will be back in their tower, having made 12 circuits.

2) Not all guards start in the same direction. In this case, there will be a (to look individually, but really, one or more) collision, that will result in the guard changing direction. In this case, it is not possible to achieve a state where all guards are travelling in the same direction, collisions will contine. These collisions will bound the guards' roaming to oscillate back and forth, but 'around' his own tower. I think there can be no hard math here, as the distances between the towers is not constant nor specified, thus ruling out numerical analysis. I wish I currently had the last insight to prove that every guard will be back in his tower 12 hours later -anyone got more insight? Somehow the oscillations will be exactly 0 twelve hours later - somehow tied into the fact that all guards will have travelled exactly the same distance, as they are all on the same pace.

Sorry for the confusion... In my earlier post (1:06pm), I described an equivalent problem that's easier to solve. My solution to Blar's problem was in terms of my equivalent problem.

-Mev

I always like to try asserting a negative, and then find a contradiction. So - after 12 hours, assume some guard(s) is not in his tower. Then this guard must have travelled more in one direction than the other. Is this possible? Somehow, the answer is no, but I haven't got the somehow yet...

Your proof that things-are-always even is correct. I was wrong that the guards don't get home after 6 hours. I missed the fact that N is always even. Another way to prove your result is that if CC=# clockwise and CL= # counterclockwise,

CL + CC is even implies CL - CC is also even.

Dread Pirate Roberts, you and I are both correct that N=#clockwise - #counterclockwise but that "the displacement is 2 stations when only 1 guard is moving counterclockwise." We are just counting in different directions. If 1 person is going counterclockwise, N=11 - 1=10. Moving 10 stations clockwise is the same as moving 2 stations counterclockwise.

As a corrollary to the extra credit problem what is the minimum number of hours needed for all guards to return to their original positions? (hint its less than 12). Provide a proof :) How about for arbitrary n?The minimum time to realign is 5 minutes for any P as long as the rate is P/hr. Minimum distance is P/12 at rate P/hr yeilds time = 1/12 hr.

1) Homgeneous. The guards all walk in unison. Thus after 12 hours they make 12 circuits and return to their respective initial towers. Easy.

2) Specific. Here the guards move initially in a randomly chosen direction. I consider this to be a "marking problem". Consider that each guard has a numbered batton (1-12) and that he hands off to the guard that collides with him. This guard travels at the same speed and direction as he was initially with no loss in time or distance had. If one models it as the movement of battons, not guards, since all the guards are identical, then (2) devolves into (1) for the movement of battons. Every batton is in its original tower every hour. Since every guard holds a batton, thus every guard must be in a tower every hour, but not necessarily his own tower. That is every guard does not necessarily hold his own batton every hour (Jesse showed this way above in his Lemma 1-3 by direct means).

(2)b. Now we must show that the guard's originally numbered batton is back in his hand in 12 hours or rotations (each numbered batton is always back at its tower every hour).

If any guard looses his batton to another and so on at the end of every rotation (1 hour) only one of the 12 will have it: either a) the original guard himself or b) one of the other eleven. If it is himself the process repeats and he has his batton back every hour and also at the end of twelve hours. If not, then his batton exchanges through the group of guards until, after 12 exchanges, he has it back again. This is necessary as a different guard gets the batton each hour (a condition of alternative (b) ) and the process repeats every hour.

Trivially 12*X MOD 12 = X.

QED.

The critical observation is remarking the movement as continuous and that ONLY the initial condition is random. All other events repeat in one of a few ways.

The proof that every tower has

aguard every hour on the hour is simple, from the observation that at every collission there isaguard at the same position and moving in the same direction as they were before the collision, so if the guards were indistinguishable it would be as if the guards didn't interact.However, the guards do interact, so they will be in the same order at any time as they are at the beginning.

That means after one hour if the guards aren't at their original posts they are at a rotation, and since the directions at each tower are the same as they were at the beginning then after two hours there will be a second rotation in the same direction of the same magnitude, etc. After twelve rotations the guards must be at their original posts.

-dk

Assume the perimeter is P=3600ft. That conveniently leads to a rate of R=1ft/sec. Some have already pointed out that when 2 guards hit each other, the net energy stays the same, ie someone is going right, someone is going left.

J=#of guards going right. K=#of guards going left.

The net feet to the right per guard is S=(J-K)*time_in_seconds*R/(J+K).

If J is less than K then it's net ft to the left.

The guards are back in their original posts when net ft S= n*P =n*3600 ft where n=1,2,3, etc

Hence if time=12*3600 (ie 12 hrs), then S=(J-K)*R*3600 which always is a multiple of 3600.

I encounter a problem when J=K=6, but I think that is because my formula implicitly takes the distance between the towers as a constant.

Its the same if you have four-thousand seven hundred and thirty-three guards and they make three revolutions in three hours. So long as in X hours they travel some whole number multiple of the length of the perimeter this problem is always trivially solvable with that one key insight.

A guard will start walking clockwise(or counterclockwise) from his post. At some point he will meet a second guard that is walking counterclockwise(or clockwise-- the second guard has to be walking in the other direction) from his post. At that point both guards will reverse direction and return to the guard station they they had started from. This will happen with all of the guards.

Once a guard meets another guard, they return to the post where they started. Even though different guards may walk different distances away from their individual posts, the distance and time each individual guard covers returning to their post will be exactly the same the each individual guard spends walking away from their original station. So over the course of the 12 hours each guard will spend 6 hours walking away from their post and 6 hours returning to their post.

The distances may not be the same. Guards 1 &2 may spend 30 minutes with one walking clockwise and the other walking counterclockwise until they meet each other.

They now spend another 30 minutes returning to their post. In that case they will make 1 roundtrip in an hour. Guards 3 &4 may spend 15 minutes with one walking clockwise and the other walking counter clockwise before they meet and return to their original post. In this case their round trip is 30 minutes and they will make 2 roundtrips in an hour as compared to guards 1 &2 that make one round trip in an hour.

It does not make any difference how long each roundtrip is or how long it takes to walk it. they will each spend 6 hours walking away from their original post and 6 hours returning to their original post. Because they are each walking at a rate of speed that allows them to make one round trip of the entire castle in 12 hours, at the end of the 12 hours they will all be back at their original post. But because the distances they walk are different, at any given time you can not determine where each guard is located.

The key to this is that each guard spends x time walking from his post and x walking towards his post. All of the round trips each guard takes will cover the same ground every round trip and they meet the same second guard every trip and return to their original post at the end of every round trip.

I think this renders inoperative your examples regarding the pairs of guards (1 and 2, 3 and 4) colliding and returning to their posts -- if guards 1 and 2 start out in opposite directons and meet after 30 minutes, that would have to mean they started from the same point on the wall.

Moreover, your examples seem to ignore the fact that the guards do not stop when they arrive at a tower, they continue in the same direction. Thus if guard 3 starts out going clockwise, collides with guard 4, starts walking counterclockwise, and arrives back at his starting tower, he will continue to walk counterclockwise -- he won't be walking back toward guard 4.

But, you are right, once 1 &2 reverse they do not stop at the post, but continue walking until they meet another guard. I do not think this changes it. They will now reverse, go past their post and walk until they meet the same guard they first encountered. They now reverse and retrace their exact steps until the meet the second guard they encountered.

So they still spend the 12 hours covering the same ground numerous times, spending half of their time walking from point A(where guard 1 &2 meet) to point B( where guard 1 &3 meet) and half of their time walking in the opposite direction from point B to point A.

I don't know any fancy math, so I'll just try some brute force algebra to see how this works in practice. I reduced it to 3 guards to make it simple. The guards are A, B, and C and the distance between A and B's towers is x, between B and C's tower is y, and C and A's towers is z. I like the 3600 feet total distance idea, so the guards all move 1 ft/sec. Assume x is 100, y is 200, and z is 3300.

Assume A and B head towards each other, and C goes the long way around. A and B meet after heading half the distance between them, x/2, i.e. after 50 seconds. The next collision is between A and C. A and C meet at T+x+1/2(z-x) (reduces to T+z/2+x/2, or after C has travelled 1700 feet -- half the distance between, not A and C, but *B* and C. I.e., the collision point for A and C is exactly as if B had kept going, and A was B (the baton or hat-switching point). I.e. the collision is between C(C) and A(B) (C playing the role of C and A playing the role of B). Now the next collision is between C(B) and B(A). That collision occurs at T+x+y+1/2(z-y) or T+z/2+x+y/2 = 1850 secs., and occurs at z/2+x/2-x/2-y/2 feet from C's tower, or 1550 feet from C's tower. So after that collision, C is effectively A, B is effectively B, and A is effectively C. The next collision is between A(C) and B(B), and occurs at T+x+y+(z-y)+1/2(y), or T+z+x+y/2 = 3500 secs. at 100 feet or halfway between B's tower and C's tower. At the end of the hour, 100 seconds later, C(A) is in A's tower, B(C) is in C's tower, and A(B) is in B's tower. I.e., they've all rotated one position.

If that's a general pattern, then rotation every hour means that for N guards, in N hours they are back where they started from.

The conclusion is actually that this math problem is false.Not a one of them

necessarilygets back to any tower, much less their own.It follows the guards second by second. The wall is divided into 3600 "steps" (the amount of distance a guard can walk in a second). The towers are randomly placed, but in order (Tower 2 is clockwise of Tower 1). The guards turn around if they are ever 1 or 2 steps away from another guard.

At each hour the program will report the locations of the guards and towers (the latter just for comparison).

http://www.rafb.net/paste/results/EjESzA44.html is the program

to use it just use the download text option, save it as a text file

run it from a terminal window:

ruby filename

You pretty much need to be on a Macintosh or a PC running Linux. If you don't know what Ruby is, and you are a Windows user, this won't work for you.

Also, the towers' placement is not totally random. No tower will ever be within 4 steps of another tower.

Final Locations:

You can see that Guard 4 is in Tower 5, Guard 9, 10 and 11 are in Towers 10, 11 and 12 respectively (well 10 is near it... 46 paces away really shouldn't count)...

the baton comparison is the *momentum* that continues steadily and unbroken at the rate of 1 rph.

if the gaurds are not all traveling the same direction then they will 'bounce' off each other and pass through their own tower stations to and fro but due to their rate of 1 rph they will be at their own stations each and every hour on the hour.

"The guards turn around if they are ever 1 or 2 steps away from another guard. "

I don't think that accurately models the problem. I think it should be 0 steps away. If they are 1 or 2 steps away, they haven't bumped into each other yet, so no 'transfer of momentum' has taken place, if you want to think of it that way.

Your assumption, I think, would only be true if all of the towers were equally spaced around the perimeter, and if the pattern of initial clockwise or counterclockwise movements were symmetric (and maybe not even then).

I deleted lines 68 through 73, the 'elif' constructs for detecting collisions with 'steps away' delta 1 and 2. I also trimmed the output to speed things up.

Now it gives proper results: