Can you solve the seven planets riddle? - Edwin F. Meyer
Your interstellar police squad
has tracked a group of dangerous rebels
to a cluster of of seven small planets.
Now you must apprehend them quickly
before their reinforcements arrive.
Of course, the rebels won’t just stay put.
They’ll try to dodge you
by moving from planet to planet.
But you have one major advantage.
Every hour, your state-of-the-art cruiser
can warp between any two planets,
while their beat-up smuggling ship
can only jump to an adjacent planet
in that same time.
These rebels don’t like to stay put.
Every time they can relocate, they will.
Your scouts tell you that the approaching
rebel fleet is 10 hours away.
You can’t risk letting the rebels escape.
Can you devise a sequence
for searching the planets
that’s guaranteed to catch them
in 10 warps or less,
no matter what moves they make?
Rounding up the rebels won’t be easy.
For one, you have no way of knowing which
planet they’re on to begin with.
And without that information, it’s hard
to determine where they’ll move next.
So where do you begin?
When tackling problems of this kind
it often helps to simplify things,
so you can better understand
their dynamics.
Let’s imagine that this cluster
has the same arrangement
but no outermost planets,
leaving only the four in the center.
We still don’t know which planet
the rebels start on.
But there’s one key feature:
the third planet
is adjacent to all others,
which means the rebels either start there
and move somewhere else,
or start on one of the other planets
and have no choice
but to move to planet three.
Simply checking planet three
twice in a row would do the trick.
Adding the three outer planet
adds a bit more complexity,
but the same strategy remains.
We want to check the planets in an order
that will eventually corner the rebels.
And there’s another insight
that can help us:
each hour, the rebels move from
an even-numbered planet
to an odd-numbered planet,
or vice versa.
This gives us a way
to simplify the problem
by dividing the planets into two subsets,
and tackling each one separately.
For starters, let’s assume the rebels
begin on an even-numbered planet:
either two,
four,
or six.
So we’ll search planet two first.
If they’re not there, they must have
started on either four
or six.
which means they can move to three,
five,
or seven.
Planet three at the center gives them
the most options for their next move,
so we’ll want to check there next.
If we don’t find them, they must have been
at planet five
or seven,
meaning they’ll next move to four
or six.
Let’s now search planet four.
If they’re not there, they must have gone
to the sixth planet
and can only flee to three
or seven.
If we next scour planet three
and don’t find them,
we know they went to planet seven
and are now cornered.
They can only move to planet six, where
we’ll apprehend them on our fifth search.
Of course, this plan only works
assuming that the rebels were on
an even-numbered planet in the first hour.
But what if that assumption was wrong?
In that case, they must’ve started
on an odd-numbered planet.
And because they move to an adjacent
planet every hour,
their location must alternate between
odd and even-numbered planets.
This means that if they were on
an odd-numbered planet to start,
after five moves, they'd be
on an even-numbered planet.
So if our first five searches missed them
because our assumption that they started
on an even-numbered planet was wrong,
all we have to do now
is repeat the sequence!
Searching the planets in order
two,
three,
four,
three,
six,
two,
three,
four,
three,
six,
leaves the rebels nowhere to run.
Thanks to your deductive reasoning,
order is restored to the galaxy.
