bonanova Posted September 20, 2008 Report Share Posted September 20, 2008 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? Quote Link to comment Share on other sites More sharing options...
0 Guest Posted September 20, 2008 Report Share Posted September 20, 2008 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.. Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted September 20, 2008 Author Report Share Posted September 20, 2008 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. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted September 20, 2008 Report Share Posted September 20, 2008 (edited) 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 Quote Link to comment Share on other sites More sharing options...
0 Yoruichi-san Posted September 21, 2008 Report Share Posted September 21, 2008 (edited) 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 Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted September 21, 2008 Author Report Share Posted September 21, 2008 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? Quote Link to comment Share on other sites More sharing options...
0 Guest Posted September 21, 2008 Report Share Posted September 21, 2008 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. Quote Link to comment Share on other sites More sharing options...
0 Yoruichi-san Posted September 21, 2008 Report Share Posted September 21, 2008 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. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted September 21, 2008 Report Share Posted September 21, 2008 (edited) 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 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted September 21, 2008 Report Share Posted September 21, 2008 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. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted September 21, 2008 Report Share Posted September 21, 2008 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. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted September 21, 2008 Report Share Posted September 21, 2008 spider could just build loads of webs and wait for the ant to get trapped.. no need for help so free!. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted September 22, 2008 Report Share Posted September 22, 2008 3 Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted September 22, 2008 Author Report Share Posted September 22, 2008 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? Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted September 25, 2008 Author Report Share Posted September 25, 2008 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. Quote Link to comment Share on other sites More sharing options...
0 Prime Posted September 26, 2008 Report Share Posted September 26, 2008 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? Quote Link to comment Share on other sites More sharing options...
Question
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?
Link to comment
Share on other sites
15 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.