wu :: forums - Print Page


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

        riddles >> medium >> How can you meet Mr. Bin Ladden
        
(Message started by: wonderful on Aug 12^th, 2008, 4:31pm)

Title: How can you meet Mr. Bin Ladden
Post by wonderful on Aug 12^th, 2008, 4:31pm

From CIA's report you know that Bin lives in one of 13 caves. These caves can be considered as 13 points on a circle. Everyday, Bin move to one the two caves that are adjacent to the case he lived in the day before. Each day, you can also visit 2 caves.

What is the optimal strategy for you to find out what cave Bin is in?

Have A Great Day!

Title: Re: How can you meet Mr. Bin Ladden
Post by towr on Aug 13^th, 2008, 1:50am

Variations here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1131519823) and here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1132524701)

Here's my attempt, with 16 days:
[hide]#x#xxxxxxxxxx #.x#xxxxxxxxx #x.x#xxxxxxxx #.x.x#xxxxxxx #x.x.x#xxxxxx #.x.x.x#xxxxx #x.x.x.x#xxxx #.x.x.x.x#xxx #x.x.x.x.x#xx #.x.x.x.x.x#x #x.x.x.x.x.#. #.x.x.x.x.#.. .#.x.x.x.#... ..#.x.x.#.... ...#.x.#..... ....#.#......[/hide]

Title: Re: How can you meet Mr. Bin Ladden
Post by towr on Aug 13^th, 2008, 1:57am

in 13 12 days:
[hide]xxxxx#x#xxxxx[/hide]
~~[hide]xxxxx#.#xxxxx[/hide]~~
[hide]xxxx#x.x#xxxx xxx#x.x.x#xxx xx#x.x.x.x#xx 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]

Title: Re: How can you meet Mr. Bin Ladden
Post by SMQ on Aug 13^th, 2008, 8:19am

I can do you one better, based on inexorable's solution in the first thread linked above:
[hide]x#x#xxxxxxxxx xx.x#x#xxxxxx xxx.x.x#x#xxx xxxx.x.x.x#x# #x#xx.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]

Edit: or, more simply, just drop the top line from your diagram, towr, you don't need it. ;)

--SMQ

Title: Re: How can you meet Mr. Bin Ladden
Post by Eigenray on Aug 13^th, 2008, 10:47am

For N caves, N>2, it can be done in [hide]N-1, if N odd; N-2, if N even[/hide] days. Can you prove this is optimal? (It is so for N http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 20. But for N>20, it can be done in just [hide]segfault[/hide] days.)

Title: Re: How can you meet Mr. Bin Ladden
Post by wonderful on Aug 13^th, 2008, 8:23pm

Thanks guys! Great discussion as always.

Have A Great Day!

Title: Re: How can you meet Mr. Bin Ladden
Post by towr on Aug 14^th, 2008, 12:15am

on 08/13/08 at 08:19:04, SMQ wrote:

Edit: or, more simply, just drop the top line from your diagram, towr, you don't need it. ;)

The second line, you mean. Darn, that I didn't see that before.