The pirate ship question reminded me of a puzzle I learnt from a friend of mine a couple of years ago.

You are programming two rovers that are going to be sent to Mars. Assume that Mars is a perfect sphere and that you know its radius. Now here are some fairly unrealistic assumptions (but they are what make the problem interesting):

The two rovers will land in different places on the surface, and you have no control over where they will land or how far apart they will be initially.

The programs with which you will equip the two rovers must be

*identical*to each other (more on this below).The rovers have no way of communicating with Earth, and they cannot communicate with each other if they are more than 1 kilometer apart (their radios are very weak). Your goal is to program the rovers in such a way that they will be

*guaranteed*to come within 1 kilometer (or less) of each other at some point.

Here are some additional details that make this a well-formulated mathematical problem. When a rover lands on the surface, it has a well-defined initial location and a well-defined direction in which it is facing. Its instruments allow it to track its position and direction relative to the initial position at any time, so for example, you can program the rover to traverse a straight path from its initial landing to the opposite point on the surface of Mars. Again, remember that the programs for the two rovers are completely identical (in particular, you can't have the two rovers make some independent random choices and then follow trajectories that depend on those random choices).

Note 1. Your program can include instructions for the rover to turn at any given time by any given angle (again, the angle will be relative to whatever direction the rover is currently facing).

Note 2. This is not a "trick question" or anything like that.

Note 3. Since there seem to be a lot of questions about what is or isn't allowed, here is a more precise definition of what constitutes a valid program. Your program can be an arbitrary sequence of statements of the following two kinds: 1) move the rover forward (i.e., in whatever direction it is facing) by X meters with speed Y, where you specify X and Y; 2) turn the rover by Z degrees (relative to the direction it is currently facing), where you specify Z.

## Comments

Sort by:

TopNewestBegin with \( \epsilon\) equals \( 360/n \) with a big \( n\). While not close enough, turn epsilon degrees and advance \( \pi r^2\). That is, a whole turn.

Why would this work? Let C be the great circle that the two robots are in. If by some crazy coincidence, one robot makes an angle of \( \theta\) with C and the other does the same angle but in the other direction, then C, the great circle C

1 resulting from the point and direction of the first robot and the great circle C2 resulting from the point and direction of the second robot would form an isosceles triangle.In particular, let P be (a?) the point of intersection of C

1 and C2. Then P is equidistant from both robots, and if they both advance at the same speed, eventually they will collide in P.If instead of being an exact isosceles is a kindof isosceles, then they will almost collide with P, with a small error (that is, the smallest distance between the robots when advancing) that tends to zero when the kindof isosceles tends to an actual isosceles.So we choose an adequate \( n\) so that is big enough so that \( 2\epsilon\) is small enough for making the kindof isosceles give an error of less than half kilometer. And then try every possible outcome (that is why we turn \( \epsilon\) degrees each time) until one is sufficiently isosceles.

If the existence of \( n\) is not enough, you could double it each time a full turn is completed and eventually it would be enough. – Diego Roque · 4 years ago

Log in to reply

There exists a rotation of the sphere that takes the initial position and direction of Rover1 to the initial position and direction of Rover2 (you can get it as the composition of two rotations in the obvious way). Because of the assumption about identical programming, this rotation also takes the entire trajectory of Rover1 to the trajectory of Rover2.

The rotation has two fixed points (the intersection of the axis of rotation with the sphere); choose one of them and call it P. Because rotations preserve distances, if at some point Rover1 happens to be within half a kilometer of P, then so will Rover2. Of course, you don't know where P is, but this argument shows that it's enough to program your rovers so that their trajectory passes within half a kilometer of every point on the surface. – Mitya Boyarchenko · 4 years ago

Log in to reply

– Mitya Boyarchenko · 4 years ago

This is pretty interesting. Your approach is very similar to the solution that my friend came up with (I myself couldn't solve the problem). But then my friend also told me another absolutely amazing solution that only takes a couple of sentences to explain (if you think about it the right way, it becomes almost obvious). If no one else comes up with it, I will post this other approach in a couple of days.Log in to reply

A pair of lovers married yesterday, but in the craziness of the after party, they wake up in different houses (A house would be a point in the lattice grid Z*Z). The groom knows well that the wife is an anxious person, and will walk A streets North, B streets East and sleep there (A and B can be negative, and -4 north is 4 south for example), each day with constant A and B. "Woe is me!" He exclaims because he does not know where is she, and he does not know A nor B.

The groom is very fast so he can move from any house to another in a matter of seconds, but he can only check a house per day because he is a slow searcher. (That means, you can ask each day one house "Is the bride here?"). Can the groom, with complete certainty, catch the bride? – Diego Roque · 4 years ago

Log in to reply

– Mitya Boyarchenko · 4 years ago

Aha! I actually know the answer to this one: I heard a different formulation, but based on exactly the same idea, only a few weeks ago. If you want, you could post your question on the general discussion forum so that more people would see it. I think the solution is also very nice.Log in to reply

I think I don't completely understand the question. If the landing places of the rovers are opposites, and they point in the same direction (i.e. if they both travel one meter forward, they're still opposite to each other), then they can't do anything that changes that, right? – Tim Vermeulen · 4 years ago

Log in to reply

– Mitya Boyarchenko · 4 years ago

They can: for instance, suppose you program each of them to first turn 90 degrees clockwise (clockwise being relative to their own initial direction). After that they will no longer point in the same direction. So if next they each move one meter forward, they will no longer be opposite to each other. Does this make sense? I'm going to edit my question to explain this more clearly.Log in to reply

– Tim Vermeulen · 4 years ago

Yeah, that makes sense.Log in to reply

– Tetzki Ryutozume · 4 years ago

Please edit the question. It's hard to understand.Log in to reply

Can we pseudocode fixed-length loops for brevity? And is this in terms of spherical coordinates? Also, as per "if you like, your program for the rover's actions can depend on its entire past trajectory up to its current location and direction." does that mean we are allowed more complex constructs such as loops with dynamic length(such as each outer iteration we set the number of inner iterations to fibonacci sequence values/etc)? Any other internal state allowed? – Andrei Akhmetov · 4 years ago

Log in to reply

– Mitya Boyarchenko · 4 years ago

I should also add that internal state is not actually necessary. You are the programmer, so at any point in time you already know all the steps that the rover took previously. Keeping track of something other than the current position could become relevant if you used a random number generator, but the problem does not allow this.Log in to reply

– Mitya Boyarchenko · 4 years ago

Yes, all of these are fine. Let's just say that you are not allowed to pick random numbers to control the movement (in any case, they wouldn't help you). Otherwise, any kind of algorithm is fair game. Also, you don't even have to provide explicit pseudocode: a verbal description of the algorithm is OK, too, as long as it's clear that the description can be turned into a computer program. (For example, you can begin the algorithm by saying: go once around Mars in a great circle. You don't need to compute the exact equations to describe this movement.)Log in to reply

Random numbers would solve the problem easily. Let \( T \) be any trajectory that passes within 1km of every point on Mars and gets you back to the original position/direction, and let \( t \) be the time it takes to complete it. Whenever \( time = kt\), flip a coin. If the coin lands 0, do nothing, if the coin lands 1 follow T. The chance of success is at least 50% per round. – Vitalik Buterin · 4 years ago

Log in to reply

notthe same thing as succeeding unconditionally.Example: if you choose a point in \([0,1]\) uniformly at random, then with probability 1, this point is not equal to \(\frac{1}{2}\). However, that doesn't mean that \(\frac{1}{2}\) is not in the interval. – Mitya Boyarchenko · 4 years ago

Log in to reply

Do your rovers have any instruments e.g. compasses? – Alex Schuster · 4 years ago

Log in to reply

relative to its initial location, and if you like, your program for the rover's actions can depend on its entire past trajectory up to its current location and direction. – Mitya Boyarchenko · 4 years agoLog in to reply

– Debjyoti Chatterjee · 4 years ago

I don't under stand the question properlyLog in to reply

how about their initial direction? is it determined? or random? – Ghany M · 4 years ago

Log in to reply

– Mitya Boyarchenko · 4 years ago

It's random, in the sense that you don't have any information about the relation between the directions of the two rovers. (In other words, you could fix your coordinate system so that the first rover lands at the "North Pole", and it has some specified direction in your coordinates. However, once you made this choice, both the position and the direction of the second rover are completely arbitrary.)Log in to reply

Can the program change the speed of the rovers? – Ramon Vicente Marquez · 4 years ago

Log in to reply

– Mitya Boyarchenko · 4 years ago

Yes, you have you have complete control over how fast the rovers move and where they go. I'll add another note to explain this in more detail.Log in to reply

Get both of them to move at coprime speeds forever. Sooner or later they will meet. BTW, the speeds must be more than x km/h where x is the circumfrence of mars – Daniel Leong · 4 years ago

Log in to reply

Does \(x\) have dimensions of length, or speed, or is it unitless? Either way, your condition is inconsistent.

Regardless, if you decrease the speed of both rovers by a factor of \(k\), it will increase the time to meet up by a factor of \(k\), so there is no minimum speed for a method to work. – Jimmy Kariznov · 4 years ago

Log in to reply

– Tim Vermeulen · 4 years ago

Right. Also, coprimeness doesn't make sense either, because if \(4\) km/h and \(7\) km/h work, then \(8\) km/h and \(14\) km/h will work as well.Log in to reply

– Mitya Boyarchenko · 4 years ago

Moreover, 4km/h and 7km/h are not even allowed by the statement of the problem: the speeds have to be equal.Log in to reply

– Daniel Leong · 4 years ago

They generate the speeds based on the time they land. OR based on a piece of radioactive rock. You get it.Log in to reply

– Daniel Leong · 4 years ago

If they have compasses, then just keep them going north and stop them at the north pole.Log in to reply

here and Mitya's reply to it. – Jimmy Kariznov · 4 years ago

They don't have compasses. See Alex's questionLog in to reply