Author |
Topic: Catching Osama - the 2-D case (Read 3045 times) |
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
 |
Catching Osama - the 2-D case
« on: Nov 20th, 2005, 2:11pm » |
 Quote  Modify
|
OBL is hiding in one of his many caves. Every night, OBL moves from the cave where he spent the night, to one of his nearest neighbour caves. At daytime he sleeps.
Each team of marines that GWB sends to catch OBL can search one cave per day. There are no restrictions to the selection of the caves to inspect. GWB wants to minimise the number of marines who risk their lives in searching for OBL, but also wants to be 100% sure that he catches OBL.
In http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_har d;action=display;num=1131519823 it is shown that if the caves are arranged in a linear array (i.e. two nearest neighbours to each cave) of N caves, GWB needs to send only one team of marines, who are guarenteed to catch OBL in no more than 2N - 4 days (N > 2).
If the caves are arranged in a square grid (i.e. four nearest neighbours to each cave) of size N x N, how many teams of marines does GWB need to send in order to be 100% certain that OBL gets caught? What is the maximum time this might take? If the number of teams of marines increases above the minimum requirement, how does the maximum time for catching OBL decrease?
|
| « Last Edit: Nov 22nd, 2005, 2:22pm by JocK » |
 IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Catching Osama - the 2-D case
« Reply #1 on: Nov 26th, 2005, 3:27pm » |
Quote Modify
|
Well, to kick things off: n policemen suffice, and they can catch Osama in at most 4n - 6 days. (although probably less) On the first day put 2 policemen on the second diagonal, on the second day put 3 policemen on the third diagonal, and so on, until on the (2n - 3)rd day we put two policemen on the second to last diagonal. This eliminates Osama from all squares of one parity. Now simply repeat the process, and he should be caught within 4n - 6 days.
|
| « Last Edit: Nov 26th, 2005, 3:34pm by Deedlit » |
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Catching Osama - the 2-D case
« Reply #2 on: Dec 4th, 2005, 1:09pm » |
Quote Modify
|
on Nov 26th, 2005, 3:27pm, Deedlit wrote:| Well, to kick things off: n policemen suffice [..] |
|
Correct. Who can do with less?
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
The 3x3 case can be solved with 2 policemen in 10 days.
The 4x4 with 3 policemen in 12 days.
And the 5x5 with 3 policemen in 30 days.
See attached solution for 5x5. It shows a search for half of the grid in 15 days. The other half can be searched by repeating the procedure, totalling 30 days. (PS: actually, you have to add a day between the searches because of the parity. That gives a 31 day solution)
This suggests that a MxN grid with N<=M can be searched with only N/2+1 policemen. N/2 to create a barrier across the grid, and one to progress in the search.
|
| « Last Edit: Oct 2nd, 2015, 3:17am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Catch_the_thief_5x1.pdf