wu :: forums - Print Page


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

        riddles >> hard >> how long will bush take to catch laden?
        
(Message started by: inexorable on Nov 8^th, 2005, 11:03pm)

Title: how long will bush take to catch laden?
Post by inexorable on Nov 8^th, 2005, 11:03pm

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?

Title: Re: how long will bush take to catch laden?
Post by Joe Fendel on Nov 17^th, 2005, 5:23pm

Well, I could catch the varmint in 14 days.

[hide]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.[/hide]

As far as generalizing it, though, I'm at a loss.

Title: Re: how long will bush take to catch laden?
Post by Grimbal on Nov 17^th, 2005, 9:27pm

My method:
[hide]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.#...... .......#.#.......[/hide]

Fendel's method
[hide]x#x#xxxxxxxxxxxxx .#.#xxxxxxxxxxxxx ...#x#xxxxxxxxxxx ...#.#xxxxxxxxxxx .....#x#xxxxxxxxx .....#.#xxxxxxxxx .......#x#xxxxxxx .......#.#xxxxxxx .........#x#xxxxx .........#.#xxxxx ...........#x#xxx ...........#.#xxx .............#x#x .............#.#.[/hide]

It seems [hide]14 days[/hide] is optimal.

Title: Re: how long will bush take to catch laden?
Post by Barukh on Nov 18^th, 2005, 7:14am

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?

Title: Re: how long will bush take to catch laden?
Post by towr on Nov 18^th, 2005, 7:31am

on 11/18/05 at 07:14:22, 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.

Title: Re: how long will bush take to catch laden?
Post by Joe Fendel on Nov 18^th, 2005, 7:33am

on 11/18/05 at 07:14:22, 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 [hide]30[/hide] unless I'm mistaken.

Title: Re: how long will bush take to catch laden?
Post by Barukh on Nov 19^th, 2005, 1:13am

Thanks, towr and Joe! I overlooked the fact that [hide]the same pair of caves is inspected 2 days in a row[/hide].

Nice solution!

Title: Re: how long will bush take to catch laden?
Post by inexorable on Nov 19^th, 2005, 9:00am

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:
[hide]
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
[/hide]
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.

Title: Re: how long will bush take to catch laden?
Post by Barukh on Nov 19^th, 2005, 9:12am

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

:D :D :D

Title: Re: how long will bush take to catch laden?
Post by JocK on Nov 19^th, 2005, 9:59am

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 ... ;D

Title: Re: how long will bush take to catch laden?
Post by inexorable on Nov 20^th, 2005, 12:13am

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 ::)

Title: Re: how long will bush take to catch laden?
Post by JocK on Nov 20^th, 2005, 1:41am

on 11/20/05 at 00:13:58, 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)

Title: Re: how long will bush take to catch laden?
Post by JocK on Nov 20^th, 2005, 2:41am

Hmm... on 2nd thought:

I >= 2k(N-2)/(2k-1)

Title: Re: how long will bush take to catch laden?
Post by JocK on Nov 22^nd, 2005, 2:18pm

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_medium;action=display;num=1132524701

Title: Re: how long will bush take to catch laden?
Post by Barukh on Jan 3^rd, 2015, 11:47am

How did I forget this one?!

I've just posted another generalization here (https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1420227591;start=3#3).