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 Help Search Members Login 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 Notify of replies Send Topic Print
 Author Topic: Catching Osama - the 2-D case  (Read 3009 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: 7526
 Re: Catching Osama - the 2-D case   Catch_the_thief_5x1.pdf « Reply #3 on: Jun 27th, 2015, 8:35am » Quote 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 Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »