Pyramid Ninja

Originally posted by talzamir
Let the intersections be A, B, C, and D. There are passages leading from each to all others.

Time 1: Guard1 A -> B Guard2 D->B Guard3 A->D
Time 2: Guard1 B -> C Guard2 B->D Guard3 D->C
Time 3: Guard1 C -> A Guard2 D->A Guard3 C->D
Time 4: Guard1 A -> B Guard2 A->D Guard3 D->B
Time 5: Guard1 B -> C Guard2 D->C Guard3 B->D
Time 6: Guard1 C -> A Guard2 ...[text shortened]... where guard 1 will eventually catch her. Not sure if it suffices for other starting locations.

Originally posted by JS357
I was thinking of this. It is easiest to visualize as a tetrahedron sitting on its base triangle BCD with the apex A at the top.

Time 0: G1, G2, G3 are at apex A (or near enough apex A on the three edges AB, AC, AD, to see N, if N is between any G and apex A). This is imatiger's start.

Time 1: G's split up and go to B, C, and D. N is forced to hide on B ...[text shortened]... . Repeat the above.

Any step in which N stays on the base circuit BCD, N is closed in on.

Interesting idea, but this does not work if the ninja starts in corridors DA or DC. The ninja then just follows the guard who goes away from D at each step. I wonder though, if we could use this to constrain the ninja to a few possible corridors, then switch strategies (after a sufficient amount of time) and catch him.

Edit: This is in reply to talzamir's idea

If the ninja only moves 1/2 of a side when the guards move 1 whole side they can catch him, one way is as follows:

All start at point A

i) 1 Guard moves to B and one to C, now corridors AB and AC are clear

ii) Now they all move to point D:
Because the ninja wasn't in AB or AC he now can't be in AD, and he can't be more than 1/2 way towards A down B->A or C->A

iii) Now 1 guard moves to C, and two guards move to B:
Because the ninja wasn't in AD and was only a maximum of 1/2 way towards A down BA or CA he can't be in BD or CD or DA

iv) Now one guard at B moves to C
Because the guard wan't in BD or CD or DA, now he cannot be in BC or BD or CD and can only be at most 1/2 way towards D from A

v) Now a guard at C moves to D. Because the Ninja could only by half way towards D (from A) he can't get past this guard into DB or CD, so now the guards are at the corners of triangle BCD, and all sides of that triangle are ninja-free. They can now all converge on point A, and the Ninja is caught!

Aha! I now think they can catch him even if they are only a tiny bit faster!
Have a look at the following plan - does it work?

We assume that when the guards move 1 side, the Ninja moves x metres less than 1 side.

Guards start on 1 point

2 guards move away on different paths, this clears ninja from those paths.
Now the guards are (say) on triangle ABC with AB and AC clear

All the guards move to D. Now AD is clear, and the Ninja is at no closer than x to point A along AB or AC

Two guards move to B, and 1 guard moves to C. Now DB and DC are clear, and the Ninja is no closer than 2x to D along AD.

The guards at the point with two guards split, one moving towards the lone guard, and one moving along the path that is NOT clear.

As this patrol is repeated the guards maintain 2 clear paths leading to a single point, with the ninja at least nx metres from the point along the third path. On each iteration of the patrol, n increases by 1. There are always 2 guards on one point, and 1 on another, and the common point of the clear paths is not occupied by any guards.

Eventually the guards must reach a state where 3 paths leading to a single point are completely clear, let us assume this happens when there are two guards on B, on guard on C, and all paths to point D are clear.

Now we split the guards on B along the two unclear paths reaching the position:
2 guards on C, one guard on A. Clear paths are AB, BC, BD, CD. Ninja can be anywhere in AC or at least x from D along AD

Now we go into another repeated patrol. There will always be 2 guards on one point and one on another, the Ninja can be between the guards, or on one other path but at least nx from one end. We maintain this state with the following move:
The doubled guards split, one goes to the single guard, and the other moves so that there will be an unclear path between him and the doubled guards when the move is finished.

The first few moves in this are:
Guards on C split, one to Lone guard at A, other to D
Now there are two guards on A, one on D: Ninja can be anywhere on AD or at lest 2x from C along CD.

Guards on A split, one to lone guard at D, other to B. Ninja can be anywhere along DC or at least 3x from B along BC

Guards on D split, one to lone guard at B, other to C. Ninja is anywhere along BC or at least 4x from A along AC.

This continues until the Nx that the ninja is from the end of a path is equal or greater than the length of the path. At that point the ninja is confined to a single path between two guards, and they move together, catching him!

I think that can be made simpler.

Guards start on 1 point

2 guards move away on different paths, this clears ninja from those paths.
Now the guards are (say) on triangle ABC with AB and AC clear

All the guards move to D. Now AD is clear, and the Ninja is at no closer than x to point A along AB or AC

Two guards move to B, and 1 guard moves to C. Now DB and DC are clear, and the Ninja is no closer than 2x to D along AD.

The guards now repeat the move below:
The guards at the double point split, with one guard moving to the lone guard, and the other guard moving so that the path between him and the other 2 guards guards is not guaranteed clear of the ninja (the guard prefers to move along a non-clear path do this if he has a choice).

If they follow this pattern they will eventually get him. The idea is that he falls shorter and shorter of being able to be at the end of one of the paths, eventually he can't be in that path at-all, and another path begins to diminish, and so his possible positions slowly crunch up until at the end he has to be between the double guards and the lone guard, and the next move gets him.

@iamatiger : can you walk us through the next move in this sequence? I agree that conceptually you will need two guards at one intersection (given 3 guards at 3 points will never work unless you can corner the ninja, which we know you can't), but I cannot get the logic to work.

Per your post:
1) G1, G2, G3 start at A
2) G1 stay, G2 to B, G3 to C
3) All G move to D; N was in BC,and is now either part way to A on either AB or AC, or is still in BC.
4) G1, G2 to B, G3 to C; N in either AB, AC, part way to D on AD or still in BC.
5) G1 to A, G2 to C, G3 stay; N in either AD, AC or part way to B in BD or part way to C in CD
and then what - something like this?
6) G1 stay, G2 to A, G3 to D; N was in AD or BD, now in AD, BD, BA or part way to C in BC. The number of possible locations for N is increasing.

No matter how I simulate this, the N can stay out of trouble given he is all-knowing and all-seeing and predicts all G moves. No sooner have you moved G off an intersection, the N could have been say 10 metres away and then follows the G past the intersection no longer controlled. Given N can double back into an unsecured pathway, I can't see how the guards trap N if they move in one direction only to take advantage of their speed. From point 6 above, the 2nd G at point A cannot make it back to point B faster than the N and even if he could, pathway AD has still not been cleared. Pathway AD cannot be cleared without making another pathway unsecured.

Edit : For this example I have envisaged an equilateral triangle BCD, with a central point A as if I were looking down on the tetrahedron.

1) G1, G2, G3 start at A
2) G1 stay, G2 to B, G3 to C

Now we know the ninja is not on AB or AC

3) All G move to D; N was in BC,and is now either part way to A on either AB or AC, or is still in BC.

True, but we know AD is clear
Also, the ninja can't be exactly at A, he must be short of it, let us assume he falls behind by 1/10th of a corridor length, so he is at most 9/10ths of the way to A

4) G1, G2 to B, G3 to C; N in either AB, AC, part way to D on AD or still in BC

Hmm, now we know DB and DC are clear and the ninja is at most 8/10ths towards D from A (he wasn't quite at A at the start of this move, so to go towards D he has to go the leftover 10th towards A and therefore has only 8/10ths of a move left towards D)

5) G1 to A, G2 to C, G3 stay; N in either AD, AC or part way to B in BD or part way to C in CD
The ninja is not in BA or BC, and can be at most 7/10ths of the way towards B from D

6) G1 stay, G2 to A, G3 to D; N was in AD or BD, now in AD, BD, BA or part way to C in BC.
The ninja is not in CA or CD, and is at most 6/10ths of the way towards C from B.

The number of possible locations for N is increasing.
On the contrary, there are always two corridors he cannot be in (wherever he started) , and a third corridor that he can be in less of each time, eventually he falls too far behind and can't be in that third corridor at all (at which point we get a 4th corridor for free) and then he starts to not be in 4 corridors and fall behind in a 5th corridor. Once he can't be in that 5th corridor at-all he is confined to a single corridor and then we get him, see?

I think the locations appear to increase because you have assumed a single starting location for the ninja.

can you walk us through the next move in this sequence?
The next move we do G1 to D, G2 to B
Now the ninja can't be in AD or AB, and can be at most 5 10ths of a move towards A from C.

It seems to me to be simpler to keep track of the corridors he can't be in, rather than the corridors he can be in. That means we don't have to worry about where he started.

Thinking of this again I've found it useful to adjust this to lawnmowers and weed. Start with a system filled with weed across all paths, and where ever any is left, it starts spreading again, but it can't pass through a lawnmower and none is left in a lawnmower's wake - which makes the question of whether all the weed can be mowed or not.

Weed spread at speed v_w and the lawnmowers move at speed v_l > v_w. The area covered by weed decreases whenever it is clipped in at least as many places as where it grows. That means that a guard / lawnmower has the edge if there are 1 or 3 filled corridors leading to the intersection where he stands, and the ninja / weed has the edge if there are exactly 2, as that means the guard can't move without making the situation worse, and when he doesn't move no ninja is getting pushed tighter / no weed is getting clipped.

The only arrangement where no guard can move, I think, is having the guards on some triplet ABC and the ninja in the triangle ABC, the rest of the system clean. Does the way the guards move necessarily lead to that?

Originally posted by iamatiger
1) G1, G2, G3 start at A
2) G1 stay, G2 to B, G3 to C

Now we know the ninja is not on AB or AC

3) All G move to D; N was in BC,and is now either part way to A on either AB or AC, or is still in BC.

True, but we know AD is clear
Also, the ninja can't be exactly at A, he must be short of it, let us assume he falls behind by 1/ han the corridors he can be in. That means we don't have to worry about where he started.

Agreed. Nice work. =)

Yes, it does repeat every 4 (if you don't label the guards), but on an individual guard basis I think it take 12 moves to repeat. The pattern is:

ADD
ABA
BBC
DCC
DAD
AAB
CBB
CDC
DDA
BAA
BCB
CCD

Each guard walks two corridors and then gets a rest. In this arrangement the rest rooms and the rooms with only one guard in both go ABCDABCD (but offset by one)

By the way, you don't need the first two odd moves, although it takes a bit longer to catch the ninja if you don't do them.

Would anyone like me to write a perl simulation of this? Or is that over the top? We could perhaps use it to find the fastest strategy.

Originally posted by talzamir
Thinking of this again I've found it useful to adjust this to lawnmowers and weed. Start with a system filled with weed across all paths, and where ever any is left, it starts spreading again, but it can't pass through a lawnmower and none is left in a lawnmower's wake - which makes the question of whether all the weed can be mowed or not.

Weed spread at e ABC, the rest of the system clean. Does the way the guards move necessarily lead to that?

I'd love to see it perlified. The duel of lawnmowers and weed would make a fascinating screensaver too. And yes, naturally lawnmowers need to be able to cross clean corridors too.

Originally posted by talzamir
I'd love to see it perlified. The duel of lawnmowers and weed would make a fascinating screensaver too. And yes, naturally lawnmowers need to be able to cross clean corridors too.