Robots On A Circle

Alright, time for the solution to the robots on a sphere problem.

It is something of a neat problem, because many people get tripped up right away with the following idea:

If both robots start on opposite sides of the planet facing opposite directions, they will stay that way forever, always mirroring eachothers moves and never finding eachother, no matter what their program is.

This argument actually seems pretty rock-solid, and I spent some time wondering why this problem has such a blatant hole in it, but there is a way out, if you know that the robots are going to start in such a configuration, the solution is this:

Each robot takes a 90 degree turn right, and then moves forward.

This will cause the robots to turn and face eachother, and move forward until they meet 'halfway' (grab a convenient sphere and try it out if you don't believe me). It becomes clear that any solution that is going to cover the extreme case of robots on the opposite side of the planet is going to need to refer to handedness somewhere, using the word 'right' or 'left'.

Now, we may assume that the robots drop off their flags as soon as they land (waiting will not really help anything), and it is easy to see that any two distinct points on the sphere uniquely define a circle on that sphere. The circle can be found by taking the set of points that are equal distance from each of the two points. In the case where the two points are antipodal, the circle that results is the 'equator'. Now that the robots have found a circle that they agree upon (they can find eachothers flags easily, given their own size and the radius of the planet), we just need them to get walking along that circle in opposite directions. Have them travel along the circle with their own flag on the right, this will result in the going opposite directions along the circle, they will meet up eventually.

Robots On A Sphere

So, the blog seems to be reverting to a semi-weekly thing (where semi-weekly means every other week, not twice a week, which is apparently semi-standard english (where semi-standard means half standard, not twice standard, at least I'm consistent)). Anyway, I first found this puzzle on the xkcd forums:

Two robots are being sent to a planet, and you will have to write an algorithm for the robots to find eachother. The planet is a perfect, featureless sphere of known radius, and the robots are of a size epsilon (epsilon is small compared to the size of the planet). The robots each have a single flag that they can place anytime at their location that cannot be moved once placed. The robots have no sight range and can only find something by bumping into it, but they can tell the difference between their own flag, the other robots flag, and the other robot. Each robot must be given the exact same deterministic program, the robots will land somewhere randomly on the planet and will them just follow their program. Find an algorithm that guarantees that the robots can find eachother.

The hardest part is dealing with the fact that both robots must be given the same program. You may assume for simplicity that the robots already have a simple program for searching out an area (were you able to keep one robot stationary while the other moves, this problem would be trivial, as it is easy to search the entire planet surface given its radius and the robots size) so you don't need to write out such an algorithm explicitly.

Logicians Are Crazy

Time for the solution to the pirates problem from last time. The comments section last time gave away the essentials of the solution, so odds are nobody is going to be surprised by anything in the answers here, but whatever.

I guess I'll solve the four problems in the order I gave them in. For notation, the pirates will be labeled in order of ages as 1,2,3,4, and 5, with 5 being the oldest. First:

The proposing pirate gets a vote, and ties result in the motion passing.

Alright, so if only pirates 1 and 2 are left, then pirate 2 can propose to take all the gold, and the motion will pass. Thus, if 1,2,3 are all left, pirate 3 can offer just 1 gold to pirate 1 and pirate 1 will accept. So then, for 1,2,3,4, pirate 4 can offer 1 gold to pirate 2 and it will pass. Finally, with 1,2,3,4,5 all there, pirate five simply offers 1 gold to pirates 3 and 1.

Pirate 5 gets 98 gold, pirate 3 and pirate 5 both get 1, motion passing 3-2.

Inductioning this up is fairly easy, and will stop when the proposing pirate runs out of gold (Inductioning is a word, right?). Moving on to the next case:

The proposing pirate does not get a vote, and ties result in the motion passing.

Now, if there are only 2 pirates left, pirate 2 is dead no matter what he proposes (as pirate 1 would rather kill him and take all the money than just take all the money. Thus, pirate 2 will accept anything pirate 3 proposes, so pirate 3 will take all the gold himself if 3 pirates are left. With 4 pirates left, pirate 4 can propose 1 gold to pirates 1 and 2 to get their support. In the 5 pirate case, pirate 5 will have to offer 1 gold to pirate 3 to get his support, and will have to offer 2 gold to either pirate 1 or 2, it does not matter which.

Pirate 5 gets 97 gold, pirate 3 gets 1 gold and one of pirates 1 or 2 get 2 gold, the other getting zero, motion passing 2-2.

This is a bit harder to induction up, since at 6 pirates, pirates 1 and 2 do not know who pirate 5 will choose if he gets the chance. Next:

The proposing pirate gets a vote, and ties result in the motion failing.

This problem actually comes out exactly the same as the last one, as if there are 2N pirates left in this case, then N votes of support besides the proposing pirate are needed to pass, just like in the last one (as only 2N-1 votes are actually cast in the last one). If there are 2N+1 pirates left, then N votes of support are needed outside of the proposing pirate, just like the last one.

Pirate 5 gets 97 gold, pirate 3 gets 1 gold and one of pirates 1 or 2 get 2 gold, the other getting zero, motion passing 3-2.

Again, hard to induction up (induction is a verb, right?).
Final case:

The proposing pirate does not get a vote, and ties result in the motion failing.

This one is a bit different, now if there are 2 pirates left, pirate 2 is just dead as before. If 3 pirates are left, pirate 3 is just dead though, as pirate 1 will vote down anything still. So with 4 pirates left, pirates 2 and 3 will support anything, as they are dead otherwise. Finally, with 5 pirates, pirate 5 will offer 1 gold to pirates 1, 2, and 3 to get their support.

Pirate 5 gets 97 gold, pirate 1, 2, and 3 each get 1, motion passing 3-1.

This will induction up to 6 pirates, but no further because at 6 the pirate must choose if he offers 2 gold to two of {1,2,3}, but he does not care which ones.

In conclusion, the oldest pirate wins, alot. Also, logicians are crazy.