wu :: forums - Print Page


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

        riddles >> hard >> The mouse in the cheese cube
        
(Message started by: Bitrot on Jul 20^th, 2004, 8:39pm)

Title: The mouse in the cheese cube
Post by Bitrot on Jul 20^th, 2004, 8:39pm

So there's a mouse on a 3x3x3 compound-cheese-cube. He starts at a corner and works his way through, eating blocks of cheese. In the original problem, we were asked if a mouse could eat all the subcubes and end at the center; this was actually on my graph theory final! But that mouse is not very interesting; let us consider the plight of his mentally deficient sibling.

This mouse was the runt of the litter, and he didn't turn out too bright (but he's very nice). As a result, he must make a ninety-degree turn after each block of cheese that he eats. He still can't backtrack into where he's already been. How many cubes of cheese out of the 27 can he eat before he has to stop? What about for n>3? Non-cubes?

Can you prove optimality without brute-force?