seven planets riddle

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.