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.
2 comments:
Boring, now generalize to n-robots on an n-dimensional circle (what is that called again? S^n? like how a sphere is S^2?). Although I'm wondering if you can even search such a thing in finite time.
Yeah, its called S^n, though I'm not sure if you want n robots on S^n or m robots on S^n. Anyway, with robots on S^1, you fail, because the argument about antipodal points actually kills you there, the fact that the argument fails in S^2 is connected to the fact that all continuous transformations on S^2 have a fixed point. That statement is not true in S^1 or S^3, so it think you won't be able to work things out there (maybe three robots on S^3 can manage, I'm not sure).
There is some issue of if you have enough robots they will have too easy of a time finding a unique point because they have so many flags to work with, I'm not sure where that would happen, and really have no idea how to visualize this problem for the higher spheres.
Post a Comment