wu :: forums - Print Page


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

        riddles >> hard >> HARD: MOUSE EATING CHEESE CUBES
        
(Message started by: srowen on Jul 28^th, 2002, 8:02pm)

Title: HARD: MOUSE EATING CHEESE CUBES
Post by srowen on Jul 28^th, 2002, 8:02pm

There is no way for the mouse to do this.

To illustrate, imagine that the 27 subcubes are made of cheddar and provolone cheese. Say that the center is cheddar, and that no two adjacent cheese cubes are the same type of cheese. So you have 13 cheddar cubes, and 14 provolone. The corners are provolone.

Any path this mouse takes must involve eating alternately cheddar and provolone cheese cubes. It starts on a corner (provolone), and because there are 14 provolone cubes vs. 13 cheddar, it must end on a provolone cube also. But the center is cheddar, so such a route from corner to center is not possible.

Title: Re: HARD: MOUSE EATING CHEESE CUBES
Post by bartleby on Jul 29^th, 2002, 10:59am

The funny thing is, mice don't really like cheese all that much.

Title: Re: HARD: MOUSE EATING CHEESE CUBES
Post by Nicodemus on Jul 29^th, 2002, 12:44pm

well done, srowen!

All this time I have been struggling with it as a graph problem... I had determined that it was impossible by examination of the graph (it's reminiscent of the common bridge traversal problem) but I was having no luck constructing a proof. I got as far as demonstrating that every time you eliminate a corner, you remove a path of access to a side; given the ratio of corners to sides, the graph gets too disconnected to be able to visit the remainders. (By "side" I mean the piece in the middle of an edge of the cube, connected to two face centers and two corners.)

But I much prefer your solution. :D

And, yes, mice (and rats) will eat cheese but it's far from their favorite food. It is also somewhat unhealthy for them.

Title: Re: HARD: MOUSE EATING CHEESE CUBES
Post by Gamer555 on Jul 29^th, 2002, 7:24pm

Yes, the same reason it is impossible to have a reentrant knight tour with the dimensions being both odd.

I think that is the proof I found, and the best one.

Title: Re: HARD: MOUSE EATING CHEESE CUBES
Post by Raja Reddy on Oct 28^th, 2005, 1:53pm

(I realise that the last post on this thread was 3 years ago, but I was recently asked this question on an interview and so it was on my mind).

Nicodemus, this problem actually turns out to be very easy if you use graph theory. This is because the graph is bipartite, with the two groups being the chedder nodes and the provolone nodes. Since there are 14 chedder nodes and 13 provolone nodes, this tells us two things.

1. You cannot start at a chedder node (corner, or middle of a face) and end at anything but a chedder node.

2. You cannot start at a provolone node at all. I.e. you cannot start in the middle of the cube or at a point adjacent to a corner.