Puzzle time - chase on a cube
-
Three spiders are trying to catch an ant. All are constrained to the edges of a transparent cube. Each spider can move one third as fast as the ant can. Can the spiders always catch the ant, regardless of starting positions?
When you shake someone's deep sense of self-worth, leaving a scar in their ego, they will persistently try to diminish you through petty arguments & obsessive captious criticism of your actions, just to soothe the wound.
- Nassim Nicholas Taleb
-
I know next to nothing about graph theory. I suspect there’s some clever matrix that can solve this.
-
@jon-nyc said in Puzzle time - chase on a cube:
Three spiders are trying to catch an ant. All are constrained to the edges of a transparent cube. Each spider can move one third as fast as the ant can. Can the spiders always catch the ant, regardless of starting positions?
if the cube is huge, let alone infinite, I don't see how.
Also, I don't think spiders are predatory and coordinated pack hunters....
-
-
Just some observations, with three spiders you can have a single cube state which minimizes the available paths, after considering symmetry. It's easiest to imagine this as a two story square building with four elevators, one at each corner. Spider A is on the first level southwest corner, B on the second level northeast corner, and C at any of the remaining six corners. C will always be one move away from one spider and two moves away from the other.
The ant is then most safely placed such that it is one move away from one spider, two moves from another, and three from another. This single initial state (after symmetry) allows the spiders to dictate what they can, while assuming the ant has moved to the safest spot available. From there, it's a matter of proving the spiders can trap the ant.
Also, the spiders are named Red, Green, and Blue, and the ant is named Grayscale. It's no wonder who will ultimately be eaten at the end of the puzzle.
-
@klaus said in Puzzle time - chase on a cube:
I think I got it. The answer is yes.
I'll elaborate later on, but I think you can use two of the spiders to basically disrupt all cycles in the graph. Then the third one can just calmly follow the ant and is guaranteed to catch it eventually.
A spider can "guard" two adjacent corners by being near one of the corners whenever the ant gets close.
That means one can block four corners with two spiders. If you pick corners on the opposite end of the block, you can destroy all cycles that way. When there's no cycle, a single spider can easily catch the ant by just walking in its direction.
-
@klaus said in Puzzle time - chase on a cube:
@klaus said in Puzzle time - chase on a cube:
I think I got it. The answer is yes.
I'll elaborate later on, but I think you can use two of the spiders to basically disrupt all cycles in the graph. Then the third one can just calmly follow the ant and is guaranteed to catch it eventually.
A spider can "guard" two adjacent corners by being near one of the corners whenever the ant gets close.
That means one can block four corners with two spiders. If you pick corners on the opposite end of the block, you can destroy all cycles that way. When there's no cycle, a single spider can easily catch the ant by just walking in its direction.
Yeah that works.
I didn't think about blocking two corners with one spider, but the ant can't be one edge away from both corners a spider is guarding. The spider can stand guard 1/3 edge distance away from whichever of its two corners the ant is closest to. The ant can never get to either of its corners that way. So, two spiders blocking two parallel opposite edges then trap the ant along one edge. -
I was wondering, if that chase would take place on a sphere instead of a cube, with no restrictions on movement (except that it's on the sphere), how many spiders would one need to catch the ant? It's not even clear whether any finite number of spiders would suffice (assuming of course that they are all mathematical points with no extension).
-
I think you have it Klaus.
FWIW todays hint wants you te realize that a single spider suffices if you can break the cycles.
HINT: This puzzle is basically a chase on a graph. Show that if the graph were a tree (connected, but with no cycles), one spider would suffice to catch the ant.
