Author 
Topic: Catching Osama  the 2D case (Read 3039 times) 

JocK
Uberpuzzler
Gender:
Posts: 877


Catching Osama  the 2D case
« on: Nov 20^{th}, 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/cgibin/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 22^{nd}, 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.
x^{y}  y = x^{5}  y^{4}  y^{3} = 20; x>0, y>0.



Deedlit
Senior Riddler
Posts: 476


Re: Catching Osama  the 2D case
« Reply #1 on: Nov 26^{th}, 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 26^{th}, 2005, 3:34pm by Deedlit » 
IP Logged 



JocK
Uberpuzzler
Gender:
Posts: 877


Re: Catching Osama  the 2D case
« Reply #2 on: Dec 4^{th}, 2005, 1:09pm » 
Quote Modify

on Nov 26^{th}, 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.
x^{y}  y = x^{5}  y^{4}  y^{3} = 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 2^{nd}, 2015, 3:17am by Grimbal » 
IP Logged 



