wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Minimum no. of Guards needed
        
(Message started by: inexorable on Aug 28^th, 2007, 2:16am)

Title: Minimum no. of Guards needed
Post by inexorable on Aug 28^th, 2007, 2:16am

Alice is being chased by Bob. She has shrunk herself to a point x in the unit square [0, 1]². Not to be out-done, bob has shrunk himself to a point y!=x in the same square. He has the latest laser camera and would love to get a picture of Alice in her reduced state. He points his camera and it emits a zero thickness light ray. If it hits a wall it will be reflected. He wants to shoot the ray so that it reaches Alice. She however, can place guards that are points Z1,Z2, . . . , in the square and if the beam tries to go through one of the guards it is blocked. How many guards does Alice need so that no beam from Bob can reach her?

Title: Re: Minimum no. of Guards needed
Post by towr on Aug 28^th, 2007, 2:37am

I assume neither Bob nor Alice know where the other is.

[hide]Bob might be right next to Alice, so there would have to be a guard between them; but Bob could be on any side of Alice, so there have to be guards all around Alice.
If we have a circle of guards around Alice, Bob might still be within that circle, so we need guards covering a whole area around Alice.

Since it seems implicit that Alice has only countably infinitely many guards, she can't protect her privacy with certainty from Bob.[/hide]

Title: Re: Minimum no. of Guards needed
Post by Grimbal on Aug 28^th, 2007, 5:14am

I will assume Alice knows where Bob is.
[hide]If A places a guard midway between A and B, the ray from A to B will hit that guard for a direct aim or for any ray that bounces 4·m times horizontally and 4·n times vertically. To protect from all the rays that bounce 4·m+i times horizontally and 4·n+j times vertically you need 15 more. It is difficult to explain. But the point is that the middle point of any ray aiming at A or an image of A is equal to the middle point of a ray that aims at an image of A at most 0 to 3 squares north or east.

So my answer is: 16. [/hide]

Title: Re: Minimum no. of Guards needed
Post by Barukh on Aug 28^th, 2007, 9:55am

on 08/28/07 at 05:14:16, Grimbal wrote:

[hide]So my answer is: 16. [/hide]

Consider this. How would you succeed with your guards?

Or, am I missing something?

Title: Re: Minimum no. of Guards needed
Post by towr on Aug 28^th, 2007, 10:12am

on 08/28/07 at 09:55:38, Barukh wrote:

Consider this. How would you succeed with your guards?

Or, am I missing something?

[hideb]
Suppose we have

B at (u,v)
A at (x,y)

We find reflections of A appearing at:

(2n+x, 2m+y)
(2n+x, 2m+1-y)
(2n+1-x, 2m+y)
(2n+1-x, 2m+1-y)

for all integers n,m

Midpoints of (u,v) and the reflections are:

1/2 (2n+x+u, 2m+y+v)
1/2 (2n+x+u, 2m+1-y+v)
1/2 (2n+1-x+u, 2m+y+v)
1/2 (2n+1-x+u, 2m+1-y+v)

Since we only need to take the fractional part of the coordinates, it's the same as taking

1/2 (x+u, y+v)
1/2 (x+u, 1-y+v)
1/2 (1-x+u, y+v)
1/2 (1-x+u, 1-y+v)

So there's only 4 such midpoints; but we need their reflections as well to get a complete covering, so times 4.

[/hideb]

Title: Re: Minimum no. of Guards needed
Post by Barukh on Aug 28^th, 2007, 10:56pm

Yes, I see. Very clever, Grimbal & towr!