Author |
Topic: how long will bush take to catch laden? (Read 3880 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: 7526
|
|
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.
|
|
|
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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print