Author |
Topic: HARD: MOUSE EATING CHEESE CUBES (Read 5130 times) |
|
S. Owen
Full Member
Gender: 
Posts: 221
|
 |
HARD: MOUSE EATING CHEESE CUBES
« on: Jul 28th, 2002, 8:02pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
bartleby
Guest
|
|
Re: HARD: MOUSE EATING CHEESE CUBES
« Reply #1 on: Jul 29th, 2002, 10:59am » |
Quote Modify
 Remove
|
The funny thing is, mice don't really like cheese all that much.
|
|
IP Logged |
|
|
|
Nicodemus
Guest
|
|
Re: HARD: MOUSE EATING CHEESE CUBES
« Reply #2 on: Jul 29th, 2002, 12:44pm » |
Quote Modify
Remove
|
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. 
And, yes, mice (and rats) will eat cheese but it's far from their favorite food. It is also somewhat unhealthy for them.
|
|
IP Logged |
|
|
|
Gamer555
Newbie
Posts: 19
|
|
Re: HARD: MOUSE EATING CHEESE CUBES
« Reply #3 on: Jul 29th, 2002, 7:24pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Raja Reddy
Guest
|
|
Re: HARD: MOUSE EATING CHEESE CUBES
« Reply #4 on: Oct 28th, 2005, 1:53pm » |
Quote Modify
Remove
|
(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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print