wu :: forums « wu :: forums - how long will bush take to catch laden? » Welcome, Guest. Please Login or Register. Jan 31st, 2023, 12:34pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: william wu, ThudnBlunder, Grimbal, SMQ, Icarus, towr, Eigenray)    how long will bush take to catch laden? « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: how long will bush take to catch laden?  (Read 3752 times)
inexorable
Full Member

Posts: 211
 how long will bush take to catch laden?   « on: Nov 8th, 2005, 11:03pm » Quote 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 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:
Posts: 7522
 Re: how long will bush take to catch laden?   « Reply #2 on: Nov 17th, 2005, 9:27pm » Quote 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:
Posts: 2276
 Re: how long will bush take to catch laden?   « Reply #3 on: Nov 18th, 2005, 7:14am » Quote 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:
Posts: 13730
 Re: how long will bush take to catch laden?   « Reply #4 on: Nov 18th, 2005, 7:31am » Quote 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 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:
Posts: 2276
 Re: how long will bush take to catch laden?   « Reply #6 on: Nov 19th, 2005, 1:13am » Quote 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 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:
Posts: 2276
 Re: how long will bush take to catch laden?   « Reply #8 on: Nov 19th, 2005, 9:12am » Quote Modify

Inexorable, I must admit I haven't seen such an elegant solution for a long time!

 IP Logged
JocK
Uberpuzzler

Gender:
Posts: 877
 Re: how long will bush take to catch laden?   « Reply #9 on: Nov 19th, 2005, 9:59am » Quote 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 ...

 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 Modify

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

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

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

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:
Posts: 877
 Re: how long will bush take to catch laden?   « Reply #12 on: Nov 20th, 2005, 2:41am » Quote 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:
Posts: 877
 Re: how long will bush take to catch laden?   « Reply #13 on: Nov 22nd, 2005, 2:18pm » Quote 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:
Posts: 2276
 Re: how long will bush take to catch laden?   « Reply #14 on: Jan 3rd, 2015, 11:47am » Quote Modify

How did I forget this one?!

I've just posted another generalization here.
 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 »