Author |
Topic: Minimum no. of Guards needed (Read 809 times) |
|
inexorable
Full Member
Posts: 211
|
 |
Minimum no. of Guards needed
« on: Aug 28th, 2007, 2:16am » |
 Quote  Modify
|
Alice is being chased by Bob. She has shrunk herself to a point x in the unit square [0, 1]2. 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?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Minimum no. of Guards needed
« Reply #1 on: Aug 28th, 2007, 2:37am » |
Quote Modify
|
I assume neither Bob nor Alice know where the other is.
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.
|
| « Last Edit: Aug 28th, 2007, 2:38am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Minimum no. of Guards needed
« Reply #2 on: Aug 28th, 2007, 5:14am » |
Quote Modify
|
I will assume Alice knows where Bob is.
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.
|
| « Last Edit: Aug 28th, 2007, 5:27am by Grimbal » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
on Aug 28th, 2007, 5:14am, Grimbal wrote:
Consider this. How would you succeed with your guards?
Or, am I missing something?
|
| « Last Edit: Aug 28th, 2007, 9:56am by Barukh » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Minimum no. of Guards needed
« Reply #4 on: Aug 28th, 2007, 10:12am » |
Quote Modify
|
on Aug 28th, 2007, 9:55am, Barukh wrote:Consider this. How would you succeed with your guards?
Or, am I missing something?
|
|
| hidden: |
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.
|
|
| « Last Edit: Aug 28th, 2007, 10:15am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Minimum no. of Guards needed
« Reply #5 on: Aug 28th, 2007, 10:56pm » |
Quote Modify
|
Yes, I see. Very clever, Grimbal & towr!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print