2
$\begingroup$

Echidna and Numbat are friends, so they decide to go on vacation together to visit Central American caves and volcanos. But these two friends have very different traveling philosophies. Numbat prefers to make careful reservations and plans. Echidna, on the other hand, sees a random train arriving, and jumps on the train, leaving poor Numbat alone! Not expecting this, Numbat needs to catch Echidna.

At the start of the chase, Numbat is in Guayabo and knows that Echidna has taken a series of trains to the Masaya Volcano caves site. Numbat moves first and can travel along one edge of the train network shown below per hour. After seeing where Numbat is headed, Echidna jumps on a train. If Numbat can land at the same site as Echidna, then the vacation plans can be saved! If Echidna can avoid Numbat for at least 25 moves, then the hotel reservations will expire and ruin all of Numbat's plans.

attached is a picture of map the question refers to

$\endgroup$
1
  • 2
    $\begingroup$ Welcome to Puzzling, take our tour! Could you please provide proper attribution for this question? $\endgroup$
    – bobble
    Commented Jul 5 at 13:41

2 Answers 2

3
$\begingroup$

Following PattuX's remark, I have to do the following assumptions: Echidna and Numbat move alternately, moving only after the other friend arrived at destination. And each one always know the position of the other one.

OK. Let's redraw the train network map.

simplified train network map

This map reflects the topology of the train network ignoring actual distances and positions. This is all we need.

N and E are the starting points of Numbat and Echidna.

You notice that...

... the network is suspiciously made of square cells.

This makes it possible to color the network nodes in black and white, chessboard-like. This coloring reveals a parity between the nodes: from a black node you can only go to a white node and vice-versa.

If this parity were respected everywhere, Echidna would have it easy. Numbat, starting on a white node, moves to a black node. Then Echidna, also starting on white, moves to a black node. After that, Numbat moves to a white node before Echidna moves to a white node. Whenever Echidna stands on a black node, Numbat moves to a white node and vice-versa. It is clear that Numbat can never land on Echidna's node. Unless Echidna moves intentionally to Numbat's node, Numbat will never meet Echidna. Echida only needs to avoid the dead-end at Okra Bank.

If Echidna and Numbat started on different colors, the parity would be on Numba's side. Numbat could eventually corner Echidna threatening all the nodes where Echidna can go.

Unfortunately, the parity is against Numbat. Is it hopeless, will Echidna winning?

No, because there is Bladen. Bladen breaks the parity by connecting to a black and a white node. Going thru Bladen, one can go from a black node to a white node in two moves. This reverses the player's parity.

The strategy for Numbat is therefore to first run up to Bladen and reverse the parity (travel Caracol-Bladen-Chiquibul). Now, at Chiquibul, Numbat is on a black node just like Echidna. In that situation Numbat can chase Echidna down and corner him in El Farallón or so. Thanks to the parity Numbat can threaten the nodes where Echidna could go upwards, forcing Echidna down.

Could Echidna counter-attack and change parity also? If he does so before Numbat, the parity would be on Numbat's side and he could chase Echidna back to Bladen. And after Numbat changed parity, Echidna will have no opportunity to go back to the top of the network.

A simpler way to see this is that once Numbat is at Bladen he can chose either black or white, matching Echidna's color, and choose the parity that works for him.
How long will the chase take?

It takes Numbat 10 moves to go up to Chiquibul via Bladen. Then 8 more moves to corner Echidna in El Farallón. On his 18th move Echidna must go to a node that Numbat controls and Numbat catches Echidna on his 19th move.

$\endgroup$
2
  • $\begingroup$ With how nicely this works out, I feel like this is indeed the intended solution. However, I'm not happy with the wording of the puzzle then. Echidna clearly moves after Numbat by the description. You say "Numbat could corner Echidna controlling all the nodes where Echidna can go." which only works if Echidna was forced to move first. Also, it is not even clearly stated whether Numbat even knows Echidna's position, and as such Numbat cannot even know whether Echidna perhaps reversed parity herself. $\endgroup$
    – PattuX
    Commented Jul 7 at 16:03
  • $\begingroup$ You are right, I misplaced Echidna when untangling the map and at the same time reversed the order between the two, the two error cancel each other. So, I'll fix that. $\endgroup$
    – Florian F
    Commented Jul 7 at 21:51
2
$\begingroup$

This general kind of problem is known as a pursuit-evasion games. When you read on it, take note that there are different variants (e.g. whether the two moving past each other is a capture, or whether staying where you are is a legal move)

Your example is rather restricted because therre is only one chaser and by the formularion of the problem I would not count them passing by each other a successful catch.

A helpful strategy is to work backwards and check where Numbat could actually catch Echidna. Whenever Numbat takes a train to a destination, if Echidna has at least two options she can avoid Numbat by going on any route that ends up at a different destination. This means the only way for Numbat to catch Echidna is when Echidna only has one possible move which is only the case if Echidna is at Okra Bank. On the flipside, if Echidna can manage to never go to Okra bank, she can always evade Numbat. The only way for Echidna to go to Okra Bank is via Talgua Caves. If she is at Talgua Caves however, she can always choose to go to Ayasta caves, or the Bosawa Biosphere Reserve (whichever of the two Numbat is not at). Therefore Echidna can always evade Numbat.

To me this seems like a boring variant of the pursuit-evasion game since the only graphs on which Numbat can win here are the ones that are more or less just a line. As soon as Echidna can reach a cycle, she can always evade. Perhaps you missed some detail when paraphrasing the question or I misinterpreted something in the description?

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.