Author |
Topic: 3 Spiders and a Psychic Fly (Read 8788 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
3 Spiders and a Psychic Fly
« on: Oct 29th, 2003, 9:53am » |
 Quote  Modify
|
Three spiders and a fly are constrained to walking along the edges of a regular tetrahedron. The spiders want to catch the fly, and have the advantage that the fly walks very slightly slower than the spiders (their exact speeds can be specified if needed). The fly has the advantage that it is invisible, so the spiders will never know exactly where it is unless one of them walks over it. The fly also has psychic powers, so it knows exactly what the spiders plan to do. In effect the game is:
1. Spiders decide on starting positions and a strategy for movement (no randomized strategies since the fly is psychic and spiders, like humans, cannot make truly random choices)
2. Fly decides on its starting position and where it will move
Can the spiders devise a strategy to always catch the fly?
Source: Henry Segerman; relayed from rec.puzzles
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
Man, that's got to be the world's most annoying fly.
I think this strategy might get it though. (answer image has been zipped to avoid spoiling)
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #2 on: Nov 2nd, 2003, 9:36am » |
Quote Modify
|
An idea,
::
Spider's starting position : Base vertices
Spider's Movement Strategy :
if Vs = n*Vf
(where Vs = velocity of spider, Vf = velocity of fly)
then spiders will move along the base edges only 2*n times.
After 2*n rounds of the base edges, the spiders would have come to their original positions.
If fly is not caught yet, each of these spiders would move towards the apex.
::
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #3 on: Nov 2nd, 2003, 9:42am » |
Quote Modify
|
It's a psychic fly, so it knows when the leave the standing edges, and walk behind a spider to a base edge..
So when the spiders then move to the apex the psychic fly is allready sound and safe on the base..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #4 on: Nov 2nd, 2003, 12:09pm » |
Quote Modify
|
Well that couldn't be the case i feel,
since the fly walks n times slower than the spider's .... during the 2*n rounds the spider's make, the fly is sure to come below one of the spiders.
However if the fly acts intelligently and stays at the apex or the edges adjacent to the apex then it would be caught in the last step anyhow.
i think this works! ( someone has to talk me out of this soon!!  )
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #5 on: Nov 2nd, 2003, 12:21pm » |
Quote Modify
|
The fly can just stay at an edge while the spiders work around on the base, and whe they are on their last edge of their walk on the base, the fly can slip behind them..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #6 on: Nov 2nd, 2003, 12:42pm » |
Quote Modify
|
on Nov 2nd, 2003, 12:21pm, towr wrote:| The fly can just stay at an edge while the spiders work around on the base, and whe they are on their last edge of their walk on the base, the fly can slip behind them.. |
|
hmm!! slip behind them (They taught the fly circus tricks too!) BTW, its a fly , why doesn't it simply fly away? 
i still don't think it can escape  .
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
redPEPPER
Full Member
Posts: 160
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #7 on: Nov 2nd, 2003, 2:18pm » |
Quote Modify
|
Slip behind them:
Let's say the base is ABC, the apex is D. Spider a (=spa) starts on A, spider b (=spb) on B and spider c (=spc) on C. The fly is, say, on AC (close to A). The spiders do their 2*n turns, the fly doesn't move. The last segment for spa is CA. The last segment for spb is AB. Right after spb leaves A, the fly goes down to A and follows spb towards B. When the spiders reach A, B and C, they'll start going up towards the apex, while the fly is safely on AB.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #8 on: Nov 2nd, 2003, 11:43pm » |
Quote Modify
|
TenaliRaman, another question: in your approach, the spiders must make exactly 2*n rounds on the base, or at least 2*n rounds?
If the former, there is a problem that n may not be commensurable with 2.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #9 on: Nov 3rd, 2003, 6:40am » |
Quote Modify
|
yeap redPepper!! i realised that while i was on my train to college this morning. (i was pretty much half asleep when i posted that lost post  )
Basically my approach was to eliminate the case of the fly being on the base edges and trap it at the apex. But i don't seem to be implementing the approach properly. After a few hair scratching moments ,i came to the exact same question Barukh asks "is 2*n enough??"
i thought of this modification,
start:
1> perform 2*n base rounds
2> if fly not caught, move to apex.
3> if fly still not caught, move to base vertex
4> goto start
However it din't take me long to realise that this could very well be an "infinite quest to capture the fly" (Hmm this could be a nice movie name!)
I thought of increasing the 2 in 2*n to some other k, but this still does not avoid the fly from escaping  . Can the fly be really caught ? 
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #10 on: Nov 3rd, 2003, 6:58am » |
Quote Modify
|
If the fly can be caught it will involve the spiders doing a little dance around the tetrahedron that is escapable by the fly, but requires the fly to be constantly moving. In any scenario that requires constant movement by the fly it will lose ground, so after enough repititions it can be caught. The trick is to figure out a repeatable spider motion that requires constant fly motion. If the fly is ever given time where it is not being forced to run, it can reposition itself for a "slip behind" like we saw before.
It does not look like the current "box it in" strategies are going anywhere.
|
| « Last Edit: Nov 3rd, 2003, 7:05am by aero_guy » |
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #11 on: Nov 3rd, 2003, 7:05am » |
Quote Modify
|
Another point: The solution must involve the spiders meeting at vertices periodically. If not, the fly can always escape by hiding near a single vertex. Whenever a spider approaches it will sit on the one edge of the three that the spider will not use.
|
| « Last Edit: Nov 3rd, 2003, 8:12am by aero_guy » |
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
Damn, I had a great solution all worked out and posted and then I noticed the zip attachment by Rezyk. ARGGGHH! Here, I have zip attached mine now too.
Actually I think mine may be a bit different. What are you doing with the power of ten thing Rezyk?
For mine you follow the pattern until you have gone through floor(2*L/[epsilon])+1 iterations where L is the length of an edge. After that you change the pattern and have only two iterations until you catch the fly.
|
| « Last Edit: Nov 3rd, 2003, 11:01am by aero_guy » |
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #13 on: Nov 3rd, 2003, 2:39pm » |
Quote Modify
|
It appears that we have the same base loop. I'd be interested in knowing how you came up with it. Here's how I did -- I aimed to force the fly into a continuous chase around the base, so I had one runner doing constant rounds around the base triangle and 2 sentries sweeping out the upper edges. It seemed to work best if the sentries were timed to meet the runner at the vertices, and with 2 of them I could have one doing so at each step. This approach isn't reflected in my final answer though; I swapped some colors to make a 3-way symmetry more obvious.
The power-of-ten thing is how I dealt with the leftover safe-havens. It doesn't directly capture a fly who uses them, but is enough to push the fly out into the death chase once in a while. By doing it this way, the spiders also don't need to know the value of [epsilon], as the death chase length will eventually get as long as it needs to be. Any other sequence that occured with increasing separation would have worked as well, such as "is a perfect power of 2" or "is a perfect square".
Quote:| After that you change the pattern and have only two iterations until you catch the fly. |
|
I'm not sure how that works -- can you be more specific about how you change the pattern?
|
| « Last Edit: Nov 3rd, 2003, 2:40pm by Rezyk » |
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #14 on: Nov 4th, 2003, 10:46am » |
Quote Modify
|
Dang, I thought I had it, but I do not. This is friggin hard. I also do not see how your pattern will force a capture.
|
|
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #15 on: Nov 4th, 2003, 5:58pm » |
Quote Modify
|
Well, I invite any flies out there to try surviving on my tetrahedron.
Once my "loop number" > L/[epsilon], place a new fly anywhere and my spiders will catch it within the next 3 perfect-powers-of-10.
|
| « Last Edit: Nov 4th, 2003, 5:59pm by Rezyk » |
IP Logged |
|
|
|
chetangarg
Newbie
Gender:
Posts: 30
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #16 on: Oct 9th, 2007, 2:18am » |
Quote Modify
|
I still can't understand how the fly can be caught....
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #17 on: Oct 9th, 2007, 11:33am » |
Quote Modify
|
on Oct 9th, 2007, 2:18am, chetangarg wrote:| I still can't understand how the fly can be caught.... |
|
Great bump, been a long while seeing this.
Well the basic approach to the solution is,
1. let the spiders go through all the edges of the tetrahedron
2. the above is done in an iterative fashion (mindless algorithmic fashion, because tricky movements are useless against a pychic fly)
3. since the fly is slower than the spiders, we should (might?!) be able to predict its movements
4. if you can predict its movement, a good iterative movement should be able to catch the spider after some time (whatever that time is)
So what does the problem ask you? It asks you
1. to find a good movement pattern for the spiders
2. show that your movement pattern will catch the fly in time <= T (finite)
(Also, as a bonus, once you find the answer, you can try reducing T as much as possible)
Reading Rezyk's last post, i could happily assume that he had a proof for his movement pattern. Unfortunately, i haven't seen him around for quite some time, so we may not see his proof for now. That means the problem is still open somewhat. (I wonder if we should add it to the list of unsolved problems?!)
-- AI
|
| « Last Edit: Oct 9th, 2007, 11:34am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
chetangarg
Newbie
Gender:
Posts: 30
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #18 on: Oct 10th, 2007, 1:08am » |
Quote Modify
|
on Oct 9th, 2007, 11:33am, TenaliRaman wrote:
That means the problem is still open somewhat. (I wonder if we should add it to the list of unsolved problems?!)
-- AI |
|
seems the same to me....
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #19 on: Oct 10th, 2007, 4:04am » |
Quote Modify
|
Very nice puzzle.
I first tried to catch a fly 3 times slower than spiders are ... after success I increased its speed to half the spiders speed. And finaly I increased its speed to (1-eps) spiders speed. After all I studied the pattern and found an easy reasoning why are the spiders successfull.
Now I can refolmulate the puzzle in the following sense: Both the spiders and the nonflying fly can accumulate some amount of energy. This energy can be used to increase its actual speed temporarily. In this way the average speed is what cannot be exceeded. What is the maximal ratio of fly to spiders average speed such that the fly can be catched?
(Accumulated energy is bounded so the increased speed cannot be used for long distances and the maximal speed can be bounded, too. But making exact wording degenerates the puzzle )
Of course who knows the solution to the original puzzle, knows the solution to the modified one.
The catching strategy is such that the fastest spider runs around the cycle of length 4 edges and the slower spiders are the guards of hiding on the two shortcuts. The fast spider always meet the guard on the shortcut start during the run. In average scenario the spiders change their roles during meetings. The spider runs 2 units in time 3 ...
Wow, now I have read both the attachments ... they have a problem with fly "dancing around one of vertices" ... it seems that I showed the first proved solution. We can discuss the catch time when fly runs (1-eps) times the spiders speed, spider traverses an edge in time 1:
From any position In time t0<=0.5 two spiders can be on the same edge, in time t0+1 the edge is cleaned and the spiders are on their oposite ends. In time t1<=1.5 the third spider is on one of the edge ends. Now the run starts on the cycle long 4 edges, spider leads 1 length. In additional time 3/eps the spider will lead by full lap so the fly is catched. So the 1.5+3/eps is the catch time.
[edit](1-eps) changed to eps[/edit]
BTW: There is another interesting question: How the catching will end with another number of spiders ... what the relative speed of fly and spiders should be for 4 spiders, for 2 spiders and for 1 spider (the 2 spiders are the most challenging, but even the problem with one spider is nice).
If a fly runs s times the spider speed and s<1/5, one spider can clean vertex neighbourhood (one edge clean upto distance s, one upto distance 3s and one upto distance 5s, spider sitting on the vertex) ... to be continued
|
| « Last Edit: Oct 17th, 2007, 11:12pm by Hippo » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #20 on: Oct 13th, 2007, 11:55am » |
Quote Modify
|
With 4 spiders, things look rather trivial - unless the fly can teleport, there's a pattern that always catches the fly in no more than the time it takes the spiders to traverse 2.5 edges.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #21 on: Oct 13th, 2007, 12:07pm » |
Quote Modify
|
Of course  I have said the other variants are more interesting . ... BTW: Can your spiders catch the fly from arbitrary starting positions in "2.5" time, or you need 3 of them starting at the same vertex? ... My can catch the fly in time "3" from arbitrary position.
|
| « Last Edit: Oct 13th, 2007, 12:15pm by Hippo » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #22 on: Oct 13th, 2007, 12:40pm » |
Quote Modify
|
it was 2.5 from a specific starting position. I've since improved the solution to time 2 from a specific starting configuration. There is, of course, a trivial lower bound on 4-spider solution time of time 1.5 - the time it would take the spiders to traverse all the edges, which is provably unattainable - when a spider arrives at a vertex, it has to meet another spider there or else the fly it was chasing can wait on the third edge for it to leave, and get onto the spider's backtrail - forcing the spiders to overpaint some stretch. If two spiders do meet at a vertex, then their arriving and departing paths combined are 4 edges out of the three available, so, again, overpainting must happen.
|
|
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
Here's a more detailed proof for my old proposal (the 2nd post in this thread).
I've labeled the potential fly position in the main steps as state A, B, C, or X. Each label spans a full side length.
1. These are the only potentially survivable transitions for any step within the main loop:
* A -> A (not indefinitely maintainable)
* A -> B
* A -> C
* A -> X
* B -> B (not indefinitely maintainable)
* B -> C
* C -> C (not indefinitely maintainable)
* X -> X (indefinitely maintainable)
* X -> C
2. Some of the same-state transitions are not indefinitely maintainable -- in other words, the fly cannot keep them up for a sequence of more than 1/epsilon steps. When factoring that in, any long-enough sequence (>3/epsilon) in the main loop has only these possible overall transitions:
* A -> X
* A -> C
* X -> X
* X -> C
3. The "perfect powers of 10" 2-step detour has only these potentially survivable transitions:
* A -> A
* A -> B
* A -> C
* B -> A
* B -> B
* B -> C
* C -> B
* C -> C
By inspection, there are no survivable transition chains for: (2) long-enough sequence in the main loop followed by a (3) 2-step detour followed by (2) a long-enough sequence in the main loop.
Idea in a nutshell: Once long enough, the main loop would clear all except for flies that dance in state X. The detour then forces those out into B or C, where there is no escape from being chased down.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 3 Spiders and a Psychic Fly
« Reply #24 on: Oct 15th, 2007, 12:58am » |
Quote Modify
|
Rezyk: OK, now I understand the perfect power of 10 branch. It's the 1st correct solution of the original puzzle (but it seems is not the best for the average speed puzzle mutation). ... the idea was explained well in your previous posts ... I haven't read it carefully enough ... sorry.
I have computed 1 spider variant recently if spider is 7 times faster than the fly, the spider can catch the fly. Probably slower spider cannot be successfull.
|
| « Last Edit: Oct 19th, 2007, 11:17am by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
spiders.zip