wu :: forums - Print Page


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

        riddles >> medium >> Catching Osama - the 2-D case
        
(Message started by: JocK on Nov 20^th, 2005, 2:11pm)

Title: Catching Osama - the 2-D case
Post by JocK on Nov 20^th, 2005, 2:11pm

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_hard;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?

Title: Re: Catching Osama - the 2-D case
Post by Deedlit on Nov 26^th, 2005, 3:27pm

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.

Title: Re: Catching Osama - the 2-D case
Post by JocK on Dec 4^th, 2005, 1:09pm

on 11/26/05 at 15:27:38, Deedlit wrote:

Well, to kick things off: n policemen suffice [..]

Correct. Who can do with less?

Title: Re: Catching Osama - the 2-D case
Post by Grimbal on Jun 27^th, 2015, 8:35am

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.