wu :: forums
« wu :: forums - Catching Osama - the 2-D case »

Welcome, Guest. Please Login or Register.
Apr 18th, 2024, 4:09pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: Grimbal, SMQ, towr, william wu, Eigenray, ThudnBlunder, Icarus)
   Catching Osama - the 2-D case
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Catching Osama - the 2-D case  (Read 3009 times)
JocK
Uberpuzzler
*****






   


Gender: male
Posts: 877
Catching Osama - the 2-D case  
« on: Nov 20th, 2005, 2:11pm »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 877
Re: Catching Osama - the 2-D case  
« Reply #2 on: Dec 4th, 2005, 1:09pm »
Quote Quote Modify 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: male
Posts: 7526
Re: Catching Osama - the 2-D case   Catch_the_thief_5x1.pdf
« Reply #3 on: Jun 27th, 2015, 8:35am »
Quote Quote Modify Modify

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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board