wu :: forums
« wu :: forums - how long will bush take to catch laden? »

Welcome, Guest. Please Login or Register.
Nov 7th, 2024, 6:50pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: towr, Eigenray, ThudnBlunder, Grimbal, Icarus, william wu, SMQ)
   how long will bush take to catch laden?
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: how long will bush take to catch laden?  (Read 3910 times)
inexorable
Full Member
***





   


Posts: 211
how long will bush take to catch laden?  
« on: Nov 8th, 2005, 11:03pm »
Quote Quote Modify Modify

Bush is hot on the trail of Laden, who is hiding in one of 17 caves. The caves form a linear array, and every night Laden moves from the cave he is in to one of the caves on either side of it. Bush can search two caves each day, with no restrictions on his choice.
 
For example, if Bush searches (1 2), (2 3), ..., (16 17), then he is certain to catch Laden, though it might take him 16 days.
 
What is the shortest time in which Bush can be guaranteed of catching Laden?  
 
extending it further, Can this be generalised for n caves where Laden  can move to any of the k caves  on either side of his present cave and Bush can search M caves each day?
IP Logged
Joe Fendel
Junior Member
**





   


Posts: 68
Re: how long will bush take to catch laden?  
« Reply #1 on: Nov 17th, 2005, 5:23pm »
Quote Quote Modify Modify

Well, I could catch the varmint in 14 days.
 
Smoke 'im out on the even numbers only.  First two days, just check caves 2 and 4.  Next two days, check caves 4 and 6.  Keep going like that.  On day 1, you either find him or rule out caves 2 and 4.  After that, on day 2n, you either find him or rule out all caves less than 2n + 3 and on day 2n + 1 you can rule out all caves less than 2n + 5 (except cave 2n + 3).
 
Thus on day 13 you have either caught him or eliminated all caves except for caves 15 and 17.  So by checking caves 14 and 16 on day 14, you nab him.

 
As far as generalizing it, though, I'm at a loss.
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7527
Re: how long will bush take to catch laden?  
« Reply #2 on: Nov 17th, 2005, 9:27pm »
Quote Quote Modify Modify

My method:

x#xxxxxxxxxxxxx#x
.x#xxxxxxxxxxx#x.
x.x#xxxxxxxxx#x.x
.x.x#xxxxxxx#x.x.
x.x.x#xxxxx#x.x.x
.x.x.x#xxx#x.x.x.
x.x.x.x#x#x.x.x.x
.#.x.x.x.x.x.x.#.
..#.x.x.x.x.x.#..
...#.x.x.x.x.#...
....#.x.x.x.#....
.....#.x.x.#.....
......#.x.#......
.......#.#.......

 
Fendel's method

x#x#xxxxxxxxxxxxx
.#.#xxxxxxxxxxxxx
...#x#xxxxxxxxxxx
...#.#xxxxxxxxxxx
.....#x#xxxxxxxxx
.....#.#xxxxxxxxx
.......#x#xxxxxxx
.......#.#xxxxxxx
.........#x#xxxxx
.........#.#xxxxx
...........#x#xxx
...........#.#xxx
.............#x#x
.............#.#.

 
It seems 14 days is optimal.
« Last Edit: Nov 17th, 2005, 9:31pm by Grimbal » IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: how long will bush take to catch laden?  
« Reply #3 on: Nov 18th, 2005, 7:14am »
Quote Quote Modify Modify

To tell the truth, I am confused...  
 
First of all, I am not sure Grimbal's demonstration corresponds to Joe's description (or I don't understand the signs).
 
Secondly, Joe: how your method catches Laden if it finds the asylum in caves 1 and 2 only?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: how long will bush take to catch laden?  
« Reply #4 on: Nov 18th, 2005, 7:31am »
Quote Quote Modify Modify

on Nov 18th, 2005, 7:14am, Barukh wrote:
Secondly, Joe: how your method catches Laden if it finds the asylum in caves 1 and 2 only?
Either he gets caught the first day, in cave 2, or the second day when he moves to cave two, where you're waiting.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Joe Fendel
Junior Member
**





   


Posts: 68
Re: how long will bush take to catch laden?  
« Reply #5 on: Nov 18th, 2005, 7:33am »
Quote Quote Modify Modify

on Nov 18th, 2005, 7:14am, Barukh wrote:
Secondly, Joe: how your method catches Laden if it finds the asylum in caves 1 and 2 only?

 
I checked cave 2 on both the first and second day.  If OBL is in cave 2 on day 1, I catch him.  If OBL is in cave 1 on day 1, then he must move to cave 2 on day 2, and I catch him.
 
A follow-up question: suppose GWB can only check 1 cave each day.  Now how many days will it take?  Seems like 30 unless I'm mistaken.
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: how long will bush take to catch laden?  
« Reply #6 on: Nov 19th, 2005, 1:13am »
Quote Quote Modify Modify

Thanks, towr and Joe! I overlooked the fact that the same pair of caves is inspected 2 days in a row.
 
Nice solution!
IP Logged
inexorable
Full Member
***





   


Posts: 211
Re: how long will bush take to catch laden?   s914.gif
« Reply #7 on: Nov 19th, 2005, 9:00am »
Quote Quote Modify Modify

GWB can catch laden in 10 days. This is a little surprising, since in the easier problem, where GWB searches only one cave per day, he might require 30 days . One expects to do twice as well with two caves per day, but 10 is well under 15.  
    10-day Solution:

Day   Caves
 1     2  4
 2     5  7
 3     8 10
 4    11 13
 5    14 16
 6     2  4
 7     5  7
 8     8 10
 9    11 13
10    14 16

To see why this works, use a checkerboard interpretation (as in the gif attached)with a board having 17 columns and 10 rows and a white square in lower left. laden's  location as he changes caves can be thought of as the path a checker may take moving up the board. Consider the caves that GWB checks as being checkers that block laden's path. If laden starts in an even (resp., odd) cave, he will always be on a black (resp., white) square as the days progress.
 
IP Logged

Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: how long will bush take to catch laden?  
« Reply #8 on: Nov 19th, 2005, 9:12am »
Quote Quote Modify Modify

Inexorable, I must admit I haven't seen such an elegant solution for a long time!
 
 Cheesy Cheesy Cheesy
IP Logged
JocK
Uberpuzzler
*****






   


Gender: male
Posts: 877
Re: how long will bush take to catch laden?  
« Reply #9 on: Nov 19th, 2005, 9:59am »
Quote Quote Modify Modify

Wow... beautiful use of Feynman's checkerboard!
 
Pitty you gave away the solution Inexorable, a hint like "for 6n-1 caves you need no more than 4n-2 days" would have kept the forum community buzy for a while ...  Grin
 
 
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.
inexorable
Full Member
***





   


Posts: 211
Re: how long will bush take to catch laden?  
« Reply #10 on: Nov 20th, 2005, 12:13am »
Quote Quote Modify Modify

ahh.. but it still remains to be proven that 10 is the minimum possible days for this case. Wink and a generalisation need to be done yet Smiley. I hope someone comes up with it soon Roll Eyes
IP Logged
JocK
Uberpuzzler
*****






   


Gender: male
Posts: 877
Re: how long will bush take to catch laden?  
« Reply #11 on: Nov 20th, 2005, 1:41am »
Quote Quote Modify Modify

on Nov 20th, 2005, 12:13am, inexorable wrote:
[..] a generalisation need to be done yet Smiley. I hope someone comes up with it soon Roll Eyes

 
One can generalise to arbitrary number of caves (N) and also to arbitrary number of inspections (k) possible on each day.
 
The total number of inspections required (I) does not seem to be capturable in a straightforward expression I(N,k). However, the general result for very large numbers of caves is easy. We fid for the number of inspections required per cave (I/N):
 
lim N -> [Infty]  I/N  =  2k/(2k-1)
 
 
« Last Edit: Nov 20th, 2005, 1:51am 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.
JocK
Uberpuzzler
*****






   


Gender: male
Posts: 877
Re: how long will bush take to catch laden?  
« Reply #12 on: Nov 20th, 2005, 2:41am »
Quote Quote Modify Modify

Hmm... on 2nd thought:
 
  I  >=  2k(N-2)/(2k-1)  
 
 
 
 
« Last Edit: Nov 20th, 2005, 3:03am 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.
JocK
Uberpuzzler
*****






   


Gender: male
Posts: 877
Re: how long will bush take to catch laden?  
« Reply #13 on: Nov 22nd, 2005, 2:18pm »
Quote Quote Modify Modify

With the 1D case solved, let's move to the 2D case:
 
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_med ium;action=display;num=1132524701
 
 
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.
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: how long will bush take to catch laden?  
« Reply #14 on: Jan 3rd, 2015, 11:47am »
Quote Quote Modify Modify

How did I forget this one?!
 
I've just posted another generalization here.
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