`pageok`
`pageok`
 `pageok` [Puzzleblogger Kevan Choset, September 7, 2005 at 12:27pm] Trackbacks The Castle Wall: 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. (link) Keith Wright (mail): Observation: When two guards bump into each other, each one takes on the path of the other, So it is guaranteed that every hour, some combination of guards will have walked the entire circle all the way around from the starting places and back again. Therefore, every hour some guard (not necessarily the original one) is in each of the towers. 9.7.2005 1:42pm (link) GMUSL 1L (mail): Other insights -- this seems like it would work for, 4 guards, 4 towers, and 4 hours, or even any other combination of N guards, towers, and hours where for all even N. This would not work for odd N. 9.7.2005 1:45pm (link) GMUSL 1L (mail): My last post also assumes that each guard can traverse the loop in 1 hour, and I should revise it to say for odd N > 1, as the trivial case works. 9.7.2005 1:46pm (link) Jesse (mail): Lemma 1: At the end of each hour, each guard is at a tower. 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. 9.7.2005 1:46pm (link) Jesse (mail): Sorry; I cross-posted with Keith Wright 9.7.2005 1:49pm (link) Goober (mail): Well... shoot, this is hard! 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 some tower 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"? 9.7.2005 1:50pm (link) jallgor (mail): I guess this is the easiest scenario. If all the guards start off walking in the same direction (which is possible given the random determination of their starting direction) they will all circle the castle 12 times and end up at their starting tower. So that's one way it would work. 9.7.2005 1:51pm (link) Dawg: Start by giving each guard a hat. Guard 1 has hat 1, guard 2 has hat 2, etc. Say that when guards bump into each other, they swap hats. 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. . . . 9.7.2005 1:51pm (link) Jesse (mail): Of course. The final step is easy. After 12 hours, the net step count is 12JK. If guard A ends up at tower M (where 1 is his original tower, 2 is the next tower clockwise, etc.), the net movement (mod 12K) is (M-1)K. But 12JK (mod 12K) is 0, so guard A must end up at M=1. 9.7.2005 1:54pm (link) Mike G (mail): Question: When the guard reaches his original tower, does he stop or keep going? 9.7.2005 1:54pm (link) Keith Wright (mail): Each hour the position of the guards may rotate some number of positions. If every hour they rotate the same number of positions in the same direction, then they are guaranteed to be back at their own tower at midnight, because 12*n is evenly divisible by twelve for all integers n. (zero works as well, though I don't know if 0 is technically evenly divisible by 12 or not.) 9.7.2005 1:57pm (link) Steve: A number of the posts so far seem to overlook the points that (1) the towers are not evenly spaced; and (2) while the case of "both guards turning around" is indistinguishable from the case of "both guards continuing onward" aside from the identity of the two guards, the identity makes all the difference, since the challenge is to prove that each guard ends up at his OWN tower after 12 hours. 9.7.2005 1:58pm (link) Mev: How about this... 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? 9.7.2005 2:06pm (link) Kevan Choset (mail): OK, seen some good things so far. The insights in Jesse's Lemma 1 and Lemma 2 (here) are important. 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. 9.7.2005 2:14pm (link) Goober (mail): Okay, since each guard is at a tower at the end of each hour (proved by many posters already), it's as though he is starting all over for the guard that was at that tower originally, and will follow the same direction as did the guard who started at that tower (since bumps merely replace the guard walking in that one direction, if any guard was leaving Tower X clockwise at hour zero, then the same or another guard will leave Tower X clockwise at each hour), ending up at the same tower after an additional hour as that original guard did at 1 o'clock. So all you're doing is replacing the guard from Tower X at noon with the same or another guard at 1:00, 2:00 and so on. 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. 9.7.2005 2:15pm (link) Kevan Choset (mail): Actually, Mev has addressed the direction issue here. 9.7.2005 2:16pm (link) GMUSL 1L (mail): Jesse, 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 9.7.2005 2:17pm (link) Jesse (mail): Kevan--I think we _do_ know that whoever leaves a given tower at the beginning of any hour is going the same direction as did the guard who left that tower at the beginning of the first hour. It follows from my Lemma 1, or from Dawg's hat argument. So that means that the same rotation happens each hour, and Mev's argument follows. (I think that my second post is an equivalent argument, but I'm not positive.) 9.7.2005 2:19pm (link) GMUSL 1L (mail): (that should be Jesse's first lemma.) Damn, twice in one day, and on the same post to boot. *hangs his head in shame* 9.7.2005 2:19pm (link) GMUSL 1L (mail): *sticks foot in mouth* OK, it's a walk around the perimeter in 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. 9.7.2005 2:20pm (link) Jesse (mail): GMUSL 1L: I think you are mis-reading the question. Each guard walks at a pace sufficient to cover the entire perimeter in one hour, not just 1/12 of it. 9.7.2005 2:21pm (link) Goober (mail): Kevan, Consider it this way: Irrespective of each guard, there is one pathway that continues in a continuous loop. That path is always occupied by a guard (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 into that guard, or the next guard who bumps into that guard, and so on---but in any event, a guard. So after each hour, there is a guard 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. 9.7.2005 2:24pm (link) DK: Jesse is correct, but it may be easier to follow if you look at each hour individually. It has already been proved above that the guards remain in the same order relative to each other, and that at the end of each hour each guard must be in a tower, so I will not discuss those points. 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. 9.7.2005 2:29pm (link) DK: To formalize this a little more, let the distances between towers 1 and 2=k(1), between 2 and 3=k(2), and so forth, so that the # of steps in the perimeter K is the sum of k(1)..k(11). 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. 9.7.2005 2:38pm (link) Kevan Choset (mail): DK, I think you've got a fencepost issue -- your 11's should all be 12's. k(12) is the distance from tower 12 back to tower 1. 9.7.2005 2:42pm (link) Cheburashka (mail): I don't find this that hard. 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 all guards 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. 9.7.2005 2:45pm (link) Goober (mail): 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. 9.7.2005 2:47pm (link) DK: oops, yes, it should be k(1)..k(12) 9.7.2005 2:47pm (link) Keith Wright (mail): Jesse has me convinced. Since a guard's momentum is maintained, not only is there some guard at each tower every hour, but that guard is also traveling in the same direction as the original guard. So each hour is a repeat of the previous, save for the identity of the guards. So each month should rotate the same number of positions, and after 12 rotations of the same size and direction, everyone is guaranteed to be back home. 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. 9.7.2005 2:49pm (link) HC: Guards will not necessarily be in a tower at the end of an hour due to irregular spacing, as noted above. 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. 9.7.2005 3:01pm (link) spencere (mail): After each guard turns around they will spend exactly the same time returning to their original post as they has previously spent walking away from their original post.. 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. 9.7.2005 3:05pm (link) HC: Well, that'll teach me to spend too much time writing - the point about momentum conservation (Jesse) and the points about overall rotation being determined by the net clockwise/counterclockwise number of guards(DK, Keith) seem dispositive, as there is no difference in the totals going each direction that is not a factor of 12 (e.g., 7/5 split, net advance is 2 clockwise). 9.7.2005 3:14pm (link) spencere (mail): As is typical with these type of questions, the secret is not in knowing the math. It is in having the insight to understand or visualize what is actually happening. That is why these type of quizes often provide insight into the way a person thinks and shows who can actually think outside the box. I just lucked out in immediately getting the right mental picture. 9.7.2005 3:16pm (link) Cheburashka (mail): 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. 9.7.2005 3:17pm (link) Cheburashka (mail): Just to expand on that - somewhere in 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. 9.7.2005 3:20pm (link) Jeffrey King (mail) (www): Consider the first hour. We know: 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. 9.7.2005 3:21pm (link) Jeffrey King (mail) (www): Consider the first hour. We know: 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. 9.7.2005 3:21pm (link) Kevan Choset (mail): Just to be clear, the problem has been solved. Jesse and Mev, above, posted what I consider the "cute" way of proving it, and DK provided a more mathematical approach. 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. 9.7.2005 3:23pm (link) Kevan Choset (mail): Jeffrey King, your summary leaves out the step that we need the guards traveling in the same direction at the beginning of each hour as they did at the beginning of the first hour, in order to guarantee that everything repeats itself. 9.7.2005 3:24pm (link) Drewsil (mail): Keith I think your extra credit is almost right. An easier way to see this is to go to a rotating frame, where people moving to the right are stationary and people moving left move twice as fast. 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? 9.7.2005 3:25pm (link) bob (www): Spencere writes:As is typical with these type of questions, the secret is not in knowing the math. It is in having the insight to understand or visualize what is actually happening. That is the math. The rest is arithmetic. 9.7.2005 3:31pm (link) CitizenZ (mail): Observations but not proofs: 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. 9.7.2005 3:40pm (link) Dread Justice Roberts: So to sum up: 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. 9.7.2005 3:49pm (link) Blar (mail) (www): Bonus question: Will each guard be back at his own tower at 6 pm? I have an answer which I'll give soon. 9.7.2005 4:00pm (link) Blar (mail) (www): Now I see that this bonus is just a corollary to the Keith/Drewsil extra credit. The answer is yes, and the answer to Drewsil's general question is that n/2 hours are required to get all guards back in their original tower when n is even, and n hours when n is odd. 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. 9.7.2005 4:16pm (link) Mev: Blar- 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 9.7.2005 4:25pm (link) DK: It is not true that you get back to your orig. tower at n/2 or n hours. Consider what happens if every hour, each guard moves 1 tower clockwise (n=1). since there are 12 towers, it will take 12 hours. More generally, the guards move n*h towers in h hours, and they return home whenever n*h is a multiple of 12. if n is 2,3,4, or 6, they will return home some time before 12. otherwise, 12 is the first return. 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. 9.7.2005 4:33pm (link) Mev: DK- What do you think of my proof that the rotation is even for even towers/guards? -Mev 9.7.2005 4:37pm (link) spencere (mail): Mev -- your solution starts with each guard passing each other twice. But the original problem states that as soon as a guard meets a guard they turn around. so guards do not pass each other twice. 9.7.2005 4:45pm (link) slammer (mail): The geometrical math approach is misleading you'll. This is a harmonics problem! 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. 9.7.2005 4:51pm (link) Blar (mail) (www): DK, the "shadow towers" are imaginary constructs that make it easier to think about the problem, like Dawg's hats, Kevan's clockwise/counterclockwise placards, and Drewsil's extra spinning. My argument works for any positioning of the 12 real towers. My point is that a rotation happens every half hour, it's just that the rotations at half past the hour are less obvious to us because the guards are each halfway around the perimeter from a real tower, rather than being at the real towers. Mev's argument and Drewsil's argument give the same result, if my shadow towers argument is hard to follow. 9.7.2005 4:52pm (link) spencere (mail): For those still working on the question, what was wrong with my solution at 2:05 PM? 9.7.2005 4:59pm (link) Blar (mail) (www): Spencere, how do you know that each guard will spend just as long walking towards their post as they spend walking away from it? Why is this true over a 12-hour period, but not over a 2-hour period, or a 9-hour period, or a 3.62-hour period? 9.7.2005 5:06pm (link) Brian Tucker (mail): This falls into two cases: 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. 9.7.2005 5:09pm (link) Mev: spencere- 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 9.7.2005 5:11pm (link) Kevan Choset (mail): Spencere, I think the problem with your solution is that your first statement ("After each guard turns around they will spend exactly the same time returning to their original post as they has previously spent walking away from their original post") has no justification. Remember, these guards may be bouncing back and forth many, many times each hour. And you want to be careful about the notions of "toward" and "away" their post, since we're on a circle. If all the guards start by moving clockwise, then would you say that for the first half hour they're all moving away from their post and then in the second half hour they're moving toward it, even though they never change direction? 9.7.2005 5:13pm (link) Brian Tucker (mail): OK, I like the switching hats proof for a guard in every tower on the hour. So how do we get from there to all guards back in their tower at midnight? We know all guards will travel enough to cover 12 circuits of the castle (individually, 144 circuits together), but how to prove that any possible distribution of tower intervals and guard starting directions will result in the same end result? 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... 9.7.2005 5:29pm (link) DK: Mev: 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. 9.7.2005 5:32pm (link) slammer (mail): 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. 9.7.2005 6:16pm (link) The Legal Thespian (www): As stated above the problem properly devolves into two solutions spaces: 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. 9.7.2005 7:07pm (link) Dick King: This isn't that hard. The proof that every tower has a guard every hour on the hour is simple, from the observation that at every collission there is a guard 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 9.7.2005 8:12pm (link) Brendon (mail): Solution: 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. 9.7.2005 9:14pm (link) Michelle Dulak Thomson (mail): I think Dick King gets the prize for "clearest and shortest summary of the solution." Nicely done. 9.7.2005 9:16pm (link) Patrick McKenzie (mail): The key insight is that the guards are effectively phantoms. Allow them to pass through each other, because its essentially the same effect as the bumping, since they're all identical (one takes on the direction of the other, both continue moving at the same speed). After that, the problem is trivial. Every phantom completes twelve full revolutions around the castle in either direction, no more and no less, and ends exactly on a guard tower, because twelve revolutions from any guard tower is a guard tower (the same one the phantom started from, although it may be a different guard). If the phantom idea displeases you, give the guards numbered batons and have them exchange the batons every time they meet and bump off each other, and track the batons, not the guards carrying the batons. Every baton makes its way home. 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. 9.8.2005 2:47am (link) Patrick McKenzie (mail): Oh, and after that insight I reread the problem. Appears you actually do care about which guards are which. D'oh. Well, since guards can't pass each other their order is static. Hmm, have to do some more thinking about this... 9.8.2005 3:04am (link) Bruce Hayden (mail) (www): Very interesting watching the solution to the problem come together. 9.8.2005 4:11am (link) Jonathan Burdick (mail) (www): Spock: "Fascinating". 9.8.2005 8:49am (link) spencere (mail): If I express it as moving clockwise you get the same answer i got yesterday. 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. 9.8.2005 10:36am (link) sodium11 (mail): But Spencere, they walk at a rate of speed that allows them to circumnavigate the wall once every *hour*, not every 12 hours. 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. 9.8.2005 10:51am (link) spencere (mail): Yes - if rate of speed allows them to circumnavigate the castle in one hour it does not make any difference, the time to do it over 12 hours will just be 12 times the time to do it in 1 hour. 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. 9.8.2005 2:51pm (link) Bruce: OK, so the baton-switching thing shows us that at every hour every guard is in a tower. Also, no guard can pass by another guard, so the guards must all be in the same order. 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. 9.8.2005 4:42pm (link) slowilly (mail): a gaurd walking one hour at a steady rate puts him back in his tower, regardless of which direction or direction changes he makes. 1 hour walking = original position. 12 hours walking = original position. 9.8.2005 10:48pm (link) Bruce: Kevin, this thread seems to have died off. What's the answer? 9.9.2005 12:51pm (link) Rahul Sinha (mail): If any of you want to test out your various hypotheses, I have written a program to simulate the movement of the guards around the wall. The conclusion is actually that this math problem is false. Not a one of them necessarily gets 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. 9.9.2005 6:14pm (link) Rahul Sinha (mail): I should say, sometimes some of them do get back to their towers (or close enough; you have to give them +/- 24 steps or so, from errors cropping up due to the fact that the guards sometimes turn around a step prior to collision. Also, the towers' placement is not totally random. No tower will ever be within 4 steps of another tower. 9.9.2005 6:20pm (link) Rahul Sinha (mail): A sample run of the program: Final Locations:```Tower Tower Location Guard Guard Location 1 1 1 3 2 292 2 292 3 600 3 600 4 740 4 890 5 892 5 1030 6 1464 6 1176 7 1548 7 1260 8 1560 8 1272 9 2348 9 2422 10 2436 10 2638 11 2684 11 2726 12 2716 12 2974 ``` 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)... 9.9.2005 6:24pm (link) slowilly (mail): the original speed, direction, *momentum* of each gaurd is continued around the circuit and returns to the original tower/gaurd after one hour. one revolution per hour. 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. 9.10.2005 11:06am (link) Shadow Merchant (mail): Rahul, you said: "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: Tower 1 is 1 seconds walk away from Tower 1, going clockwise Tower 2 is 884 seconds walk away from Tower 1, going clockwise Tower 3 is 908 seconds walk away from Tower 1, going clockwise Tower 4 is 980 seconds walk away from Tower 1, going clockwise Tower 5 is 1264 seconds walk away from Tower 1, going clockwise Tower 6 is 1436 seconds walk away from Tower 1, going clockwise Tower 7 is 1464 seconds walk away from Tower 1, going clockwise Tower 8 is 2904 seconds walk away from Tower 1, going clockwise Tower 9 is 2932 seconds walk away from Tower 1, going clockwise Tower 10 is 2996 seconds walk away from Tower 1, going clockwise Tower 11 is 3004 seconds walk away from Tower 1, going clockwise Tower 12 is 3168 seconds walk away from Tower 1, going clockwise Guard 1 reports for duty at Location 1 Guard 2 reports for duty at Location 884 Guard 3 reports for duty at Location 908 Guard 4 reports for duty at Location 980 Guard 5 reports for duty at Location 1264 Guard 6 reports for duty at Location 1436 Guard 7 reports for duty at Location 1464 Guard 8 reports for duty at Location 2904 Guard 9 reports for duty at Location 2932 Guard 10 reports for duty at Location 2996 Guard 11 reports for duty at Location 3004 Guard 12 reports for duty at Location 3168 Hour 1: Tower Tower Location Guard Guard Location 1 1 1 3003 2 884 2 3168 3 908 3 3600 4 980 4 884 5 1264 5 908 6 1436 6 980 7 1464 7 1264 8 2904 8 1436 9 2932 9 1464 10 2996 10 2904 11 3004 11 2932 12 3168 12 2996 Hour 2: Tower Tower Location Guard Guard Location 1 1 1 2931 2 884 2 2996 3 908 3 3004 4 980 4 3168 5 1264 5 3600 6 1436 6 884 7 1464 7 908 8 2904 8 980 9 2932 9 1264 10 2996 10 1436 11 3004 11 1464 12 3168 12 2904 Hour 3: Tower Tower Location Guard Guard Location 1 1 1 1465 2 884 2 2904 3 908 3 2932 4 980 4 2996 5 1264 5 3004 6 1436 6 3168 7 1464 7 3600 8 2904 8 884 9 2932 9 908 10 2996 10 980 11 3004 11 1264 12 3168 12 1436 Hour 4: Tower Tower Location Guard Guard Location 1 1 1 1263 2 884 2 1436 3 908 3 1464 4 980 4 2904 5 1264 5 2932 6 1436 6 2996 7 1464 7 3004 8 2904 8 3168 9 2932 9 3600 10 2996 10 884 11 3004 11 908 12 3168 12 980 Hour 5: Tower Tower Location Guard Guard Location 1 1 1 907 2 884 2 980 3 908 3 1264 4 980 4 1436 5 1264 5 1464 6 1436 6 2904 7 1464 7 2932 8 2904 8 2996 9 2932 9 3004 10 2996 10 3168 11 3004 11 3600 12 3168 12 884 Hour 6: Tower Tower Location Guard Guard Location 1 1 1 1 2 884 2 884 3 908 3 908 4 980 4 980 5 1264 5 1264 6 1436 6 1436 7 1464 7 1464 8 2904 8 2904 9 2932 9 2932 10 2996 10 2996 11 3004 11 3004 12 3168 12 3168 Hour 7: Tower Tower Location Guard Guard Location 1 1 1 3003 2 884 2 3168 3 908 3 3600 4 980 4 884 5 1264 5 908 6 1436 6 980 7 1464 7 1264 8 2904 8 1436 9 2932 9 1464 10 2996 10 2904 11 3004 11 2932 12 3168 12 2996 Hour 8: Tower Tower Location Guard Guard Location 1 1 1 2931 2 884 2 2996 3 908 3 3004 4 980 4 3168 5 1264 5 3600 6 1436 6 884 7 1464 7 908 8 2904 8 980 9 2932 9 1264 10 2996 10 1436 11 3004 11 1464 12 3168 12 2904 Hour 9: Tower Tower Location Guard Guard Location 1 1 1 1465 2 884 2 2904 3 908 3 2932 4 980 4 2996 5 1264 5 3004 6 1436 6 3168 7 1464 7 3600 8 2904 8 884 9 2932 9 908 10 2996 10 980 11 3004 11 1264 12 3168 12 1436 Hour 10: Tower Tower Location Guard Guard Location 1 1 1 1263 2 884 2 1436 3 908 3 1464 4 980 4 2904 5 1264 5 2932 6 1436 6 2996 7 1464 7 3004 8 2904 8 3168 9 2932 9 3600 10 2996 10 884 11 3004 11 908 12 3168 12 980 Hour 11: Tower Tower Location Guard Guard Location 1 1 1 907 2 884 2 980 3 908 3 1264 4 980 4 1436 5 1264 5 1464 6 1436 6 2904 7 1464 7 2932 8 2904 8 2996 9 2932 9 3004 10 2996 10 3168 11 3004 11 3600 12 3168 12 884 Hour 12: Tower Tower Location Guard Guard Location 1 1 1 1 2 884 2 884 3 908 3 908 4 980 4 980 5 1264 5 1264 6 1436 6 1436 7 1464 7 1464 8 2904 8 2904 9 2932 9 2932 10 2996 10 2996 11 3004 11 3004 12 3168 12 3168 Final Locations: Tower Tower Location Guard Guard Location 1 1 1 1 2 884 2 884 3 908 3 908 4 980 4 980 5 1264 5 1264 6 1436 6 1436 7 1464 7 1464 8 2904 8 2904 9 2932 9 2932 10 2996 10 2996 11 3004 11 3004 12 3168 12 3168 9.10.2005 7:31pm `pageok` `pageok`