wu :: forums - Print Page


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

        riddles >> medium >> marmelade jars 
        
(Message started by: Altamira_64 on Apr 17^th, 2012, 3:40pm)

Title: marmelade jars
Post by Altamira_64 on Apr 17^th, 2012, 3:40pm

There are 5 closed marmelade jars one next to the other. One of them contains a whole walnut, which you are trying to locate. You start by opening each jar. Once you find which jar it is in, you win the game. However, if you do not find the nut, it is somehow (in a magic, invisible way!) moved to one of the adjacent boxes (for example, if the walnut was initially in the jar No 2, it is then moved to jar No 1 or No 3). Is there any strategy by which you always win the game and what is the maximum number of tries it will take you?

Title: Re: marmelade jars
Post by MacNCheese on Apr 17^th, 2012, 4:20pm

"You start by opening each jar"

Does this mean we get to leave the jars open? Because then I would just corner the walnut by going in one direction :P

I'm guessing not, so one solution is obviously to repeatedly open a particular jar. It will eventually contain the walnut in it. I haven't put much thought in it yet, but I suppose it's like predicting a random walk.

Title: Re: marmelade jars
Post by SMQ on Apr 17^th, 2012, 6:30pm

Open the jars in the following order: [hide]2, 2, 3, 4, 5[/hide]. If you don't find it on the first guess, you know that [hide]jar 1 is now empty, since if the nut was in jar 1 it must have moved to jar 2, and the only place it could have moved into jar 1 from is jar 2 which you opened[/hide]. The next guesses rule out successive jars until you find the nut.

--SMQ

Title: Re: marmelade jars
Post by MacNCheese on Apr 18^th, 2012, 6:51am

@SMQ
I don't think that would work all the time. A counterexample:
[hide]Say the walnut is in jar 4. You open 2(empty), it goes to 5. You open 2 again(empty), it goes back to 4. You open 3(empty), it goes to 5. You open 4(empty), it goes to 4. You open 5 and it's empty.[/hide]

Title: Re: marmelade jars
Post by fieldazed on Apr 18^th, 2012, 6:59am

some thoughts - [hide]seven seems to be the obvious answer with several ways of going about it. think it can be done in six peeks - 2,3,4,2,3,4 but seems it should be doable in five[/hide].

Title: Re: marmelade jars
Post by SMQ on Apr 18^th, 2012, 12:48pm

With a bit more investigation, it appears the game with n jars (where n > 2) is minimally winnable in [hide]2(n - 2)[/hide] moves by playing [hide](2, 3, ..., n - 1, n - 1, n - 2, ..., 2)[/hide] (or its mirror image). Iff n is odd, you can alternately play [hide](2, 3, ..., n - 1, 2, 3, ..., n - 1)[/hide] (or its mirror) as fieldazed discovered.

(The games with 0, 1, and 2 jars are trivially winnable by playing _{http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/emptyset.gif}, 1, and (1, 1) respectively.)

--SMQ

Title: Re: marmelade jars
Post by MacNCheese on Apr 18^th, 2012, 1:16pm

Wow. Interesting. How would you go about proving it for n jars though?

Title: Re: marmelade jars
Post by rmsgrey on Apr 18^th, 2012, 2:45pm

on 04/18/12 at 13:16:54, MacNCheese wrote:

Wow. Interesting. How would you go about proving it for n jars though?

I'd switch it from a 1+1 dimensional problem to a 2 dimensional problem - rather than having a row of jars changing with time, have an array of jars where each row has a walnut in one jar, diagonally adjacent to the neighbouring rows'.

You can then label the jars with "black" and "white" chessboard-style and it should be obvious that the walnuts must either all be in black jars or all in white. If 2 starts off black, then going from there on the diagonal must find a walnut if they're on black - and do it by the time you reach (n-1) at the latest - the walnuts can't start to the left and still be black, can't cross your diagonal without you finding them, and can't still be to the right once you open (n-1) and still be black. (n-1) in the next row must be white and sweeping diagonally left eliminates the possibility of it being white in the same way.

Title: Re: marmelade jars
Post by rmsgrey on Apr 18^th, 2012, 2:57pm

An interesting extension I've encountered is to consider what other layouts the problem is solvable for - if, instead of putting the jars in a straight line, you scatter them and run strings between them to form some kind of web and the walnut only moves along the strings, always stopping at the first jar it reaches each time, for what webs can the walnut be guaranteed to be found within a finite number of moves?

Title: Re: marmelade jars
Post by SMQ on Apr 18^th, 2012, 3:09pm

on 04/18/12 at 14:45:55, rmsgrey wrote:

Or, equivalently, a single walnut moves from bottom to top of the chessboard, always moving diagonally forward (a chess pawn's attack), and you can place one fence piece in each row to attempt to stop it. I think that construction makes the minimality of the construction easier to visualize, as any fewer rows must leave a gap in the fence.

--SMQ