[bonanova]

A spider is trying to catch an ant.

They are constrained to walk on the edges of a cube.

The ant can move up to three times as fast as the spider can.

After trying, and failing, to catch the ant, the spider text-messages

some of his buddies for help. The cube becomes swarmed with spiders,

and eventually the ant becomes dinner. Poor ant.

But suppose his buddies were to charge him $10 each [in spider currency,]

and the spider was trying to minimize his expenditures.

What is the least the spider would have to spend to ensure the ant is caught?

[Guest]

A spider is trying to catch an ant.

They are constrained to walk on the edges of a cube.

The ant can move up to three times as fast as the spider can.

After trying, and failing, to catch the ant, the spider text-messages

some of his buddies for help. The cube becomes swarmed with spiders,

and eventually the ant becomes dinner. Poor ant.

But suppose his buddies were to charge him $10 each [in spider currency,]

and the spider was trying to minimize his expenditures.

What is the least the spider would have to spend to ensure the ant is caught?

You need 3 to catch the ant when those 3 are "set up".. Not sure how many to set up..

[bonanova]

You need 3 to catch the ant when those 3 are "set up".. Not sure how many to set up..

I like answers; I love proofs.

[Guest]

Maybe this isn't the minimum, but I can catch the ant with 5 spiders.

Let the cube's bottom corners be named A, B, C and D. Place a spider at each of them. Place the fifth spider at corner A and let it walk in a square path ABCD. This catches the ant if it's on any of the bottom edges. The five spiders then climb up the vertical edges to the top four corners and the fifth spider repeats the square path with those corners.

Edited September 20, 2008 by flowstoneknight

[Yoruichi-san]

You need 3 to catch the ant when those 3 are "set up".. Not sure how many to set up..

Well, you can do it with that number by...

The ant is constrained to travel along a particular edge until reaches a corner. Then it has 3 choices: turn around and go back on the same edge or go along one of the two other edges.

So if you have 3 spiders, one traveling towards the incident corner on each of those edges, you will catch the ant. The original spider should call in it's buddies when it is on the same edge as the ant.

You might be able to do it with less...have to think about it...

Edited September 21, 2008 by Yoruichi-san

[bonanova]

In certain set-up configurations, Y-san and taliesin

can catch the ant with 2 helper spiders for a cost of $20.

With complete generality, flowstoneknight can catch the

ant with four helpers for a cost of $40.

Is that the cheapest solution?

BTW, if you want to set things up, why not just wait until Spidey is on one

end of the edge the ant is on and then have him call a buddy to come

sit on the other end? That costs only $10.

OK, so much for set-ups. General case now.

How deep does Spidey have to dig to get that ant?

[Guest]

3 helpers for a total of 4 spiders.

Let's start from the beginning - you know you have the ant caught if you ever have the ant between two spiders on an edge. It's easy to do this with four spiders - start with the spiders on four corners of one square. If the ant is on that square, he is caught. If the ant is anywhere else, each spider can go up away from the square until it gets to the other square, forcing the ant to that square along the way. This then leaves the ant trapped on that square.

That is easy enough that I think there must be a 2 helper solution, but I can't prove it.

Yet.

I guess this leads me to one question - can the spiders see the ant from anywhere on the cube, and vice versa? If not, my solution may not work.

[Yoruichi-san]

I guess this leads me to one question - can the spiders see the ant from anywhere on the cube, and vice versa? If not, my solution may not work.

3 helpers for a total of 4 spiders.

Let's start from the beginning - you know you have the ant caught if you ever have the ant between two spiders on an edge. It's easy to do this with four spiders - start with the spiders on four corners of one square. If the ant is on that square, he is caught. If the ant is anywhere else, each spider can go up away from the square until it gets to the other square, forcing the ant to that square along the way. This then leaves the ant trapped on that square.

That is easy enough that I think there must be a 2 helper solution, but I can't prove it.

Yet.

Actually...if the spiders can see the ant...

There are a total of 12 edges, and putting a spider on a corner means he can span 3 edges, so if you put the spiders on opposing corners, you can span all 12 edges with 4 spiders, and eventually trap the ant in the 3-spider corner set-up discussed earlier.

[Guest]

In certain set-up configurations, Y-san and taliesin

can catch the ant with 2 helper spiders for a cost of $20.

With complete generality, flowstoneknight can catch the

ant with four helpers for a cost of $40.

Is that the cheapest solution?

BTW, if you want to set things up, why not just wait until Spidey is on one

end of the edge the ant is on and then have him call a buddy to come

sit on the other end? That costs only $10.

OK, so much for set-ups. General case now.

How deep does Spidey have to dig to get that ant?

I was thinking of doing it on a edge with two, but I worked out that as long as the Ant knows what he is doing, and never gets tired than this situation will never occur

I can do it for certain with 4 spiders ( fo 30$ )

Place one spider on each corner on one face. If the and is on a edge on that face, close in on him. If on the other face, then just walk the spiders up each edge trapping the ant on the face with 4 spiders..

A simular thing could happen with 3 but I think the ant will be able to escape through the gap..

Edited September 21, 2008 by taliesin

[Guest]

Lets flatten the cube so that all the edges lie on a plane. the diagram would look something like this.

now since the ant can move 3 times as fast as the spiders, lets assume for each step the ant makes along the edge of the cube, the spiders can make 1/3d of a step. Lets also assume that one step corresponds to movement from one corner of the cube to one of the adjacent corners.

Lets place 3 spiders as in the diagram below

Now the ant can be placed at any of the remaining 5 corners.

the solution if the ant were placed at the inner top right corner of the diagram is trivial.

heres a diagram of how the ant would be caught if it were placed at the inner bottom left corner of the diagram.

I'll get the diagrams for the other positions in my next post. I am not sure if the ant can decide to wait i.e pass when it is its turn to move.

[Guest]

He would need to get 5. He would put 4 on all of the edges, then there would be 2 to chase him into a corner for the corner ant to catch.

[Guest]

spider could just build loads of webs and wait for the ant to get trapped..

no need for help so free!.

[Guest]

3

[bonanova]

Lets flatten the cube so that all the edges lie on a plane. the diagram would look something like this.

now since the ant can move 3 times as fast as the spiders, lets assume for each step the ant makes along the edge of the cube, the spiders can make 1/3d of a step. Lets also assume that one step corresponds to movement from one corner of the cube to one of the adjacent corners.

Lets place 3 spiders as in the diagram below

Now the ant can be placed at any of the remaining 5 corners.

the solution if the ant were placed at the inner top right corner of the diagram is trivial.

heres a diagram of how the ant would be caught if it were placed at the inner bottom left corner of the diagram.

I'll get the diagrams for the other positions in my next post. I am not sure if the ant can decide to wait i.e pass when it is its turn to move.

Congrats for a $20 solution.

Can the $20 strategy be worded to show it works for every case?

[bonanova]

Spidey calls two helpers [$20 solution] to patrol two opposite and parallel edges of the cube.

Note that any path [other than the edge itself] between the ends of those edges is at least 3 times longer than the edge.

So the ant can be kept off those two edges.

Now note that removing those two edges also removes any looped paths in the rest of the cube.

Make a rough sketch, and this becomes clear.

Therefore Spidey may now simply track down the ant at a dead end.

Dinner is served.

[Prime]

That sounds very appetizing. I disagree, however, with posting answers to own problems. Different people come upon them (puzzles) at different times. And what's wrong with leaving it unanswered, anyway?