Challenge: getting two Mars rovers to meet

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.

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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 - 7 years, 10 months 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.

Mitya Boyarchenko - 7 years, 10 months ago

Yeah, that makes sense.

Please edit the question. It's hard to understand.

Tetzki Ryutozume - 7 years, 10 months ago

Begin 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 C1 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 C1 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 - 7 years, 10 months ago

So here is the ingenious solution that my friend explained to me. I'll refer to the surface of Mars as "the sphere."

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.

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.

Well, I will still think it. It reminded me of yet another problem, but a more discreet one. It goes a bit like this.

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 – 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.

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 - 7 years, 10 months 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.)

in any case, they wouldn't help you

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 - 7 years, 10 months ago

@Vitalik Buterin – I'm not sure what this proves. If you are implying that this strategy will succeed after finitely many steps with probability 1, I could agree, but this is not the 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.

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.

Do your rovers have any instruments e.g. compasses?

Alex Schuster - 7 years, 10 months ago

It depends on what you mean. If you mean that there is some kind of fixed "North Pole" that the rovers could go to, then the answer is no: otherwise the question would be completely trivial. However, they have something like a compass in the sense that the rover always knows where it is 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.

I don't under stand the question properly

Debjyoti Chatterjee - 7 years, 10 months ago

Can the program change the speed of the rovers?

Ramon Vicente Marquez - 7 years, 10 months 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.

how about their initial direction? is it determined? or random?

Ghany M - 7 years, 10 months 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.)

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 - 7 years, 10 months ago

"the speeds must be more than x km/h where x is the circumfrence of mars"

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 - 7 years, 10 months 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.

@Tim Vermeulen – Moreover, 4km/h and 7km/h are not even allowed by the statement of the problem: the speeds have to be equal.

@Mitya Boyarchenko – They generate the speeds based on the time they land. OR based on a piece of radioactive rock. You get it.

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

They don't have compasses. See Alex's question here and Mitya's reply to it.

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$