Jump to content
BrainDen.com - Brain Teasers
  • 1

Mouse & Cheese Cube


rocdocmac
 Share

Question

Hopefully this one has not appeared before...

Suppose 27 identical cubical chunks of cheese are piled together to form a cubical stack, as illustrated below. What is the maximum number of these cheese chunks through which a mouse of negligible size could munch before exiting the stack, assuming that the mouse always travels along the grid of 27 straight lines that pass through the centers of the chunks parallel or perpendicular to their sides, always makes a 90 degree turn at the center of each chunk it enters, and never enters any chunk more than once?

Figures.jpg

Edited by rocdocmac
Figures didn't show!
  • Upvote 1
Link to comment
Share on other sites

14 answers to this question

Recommended Posts

  • 2

(Sorry I don't know how to make spoiler on iPhone, but it seems Thalia is the winner, so I'm not surprising anyone)

Here's why 25 is max: 

Spoiler

 

Lets label a corner C, Edge Center E, Face Center F, and the hidden Center X.

There are 12 E, 8C, 6F, and 1X.

Because of the required 90 degree turn at each cell, CE can only be followed by EF (or Exit). All possible moves are:

CE : EF

FE : EC or EF

EC: CE

EF : FE  or FX

FX : XF

FE : EC

Notice only F can reach X, so the Sequence of moves must include FXF, if the Center is to be reached at all.

Also notice that once you have moved from C to E, you can only move from E to F.

For each C, you can pass through one F. (In CEFE sequence).  But while there are 8 C, there are only 6 F, so the total sequence can have only 6 C, and the maximum is only 25.

Good news is, there are enough E to join all the C and F, so the sequence could look like

ECEF ECEF ECEF

X

FECE FECE FECE

A path that avoids X would have to have an E between two Fs, which would waste an E, leaving only 24.

 

 

Edited by bonanova
Spoilered CaptainEd's answer
Link to comment
Share on other sites

  • 1

 

The answer should be 25. My "proof" is a brute force programming solution. I have a psuedocode c++ bruteforce solution. I can give the full version

if requested. It takes a few seconds to brute force all possible paths.  This might count as a proof, depending on if you trust the computer 

to be reliable.

 

Basically what it does is it generates all possible paths, and then prunes as it goes along so the program dosen't take basically forever, or 6^27 moves.

Now a proof will involve some theorems in graph theory, which I don't yet know all that well.

 

 

Assume the XYZ plane
void recursive_dumb_solution( A 3D cube,Position of X, Y, and Z of current spot,direction it went twice ago, direction it went to get here){

if traveled along a direction twice in a row, return to the above function.

   else if( x<0 || x > 2 || y < 0 || y > 2 || z < 0 || z > 2)   AKA if it exited the cube, return.
    else if(cube[x][y][z] == 1)  AKA if visited spot already visited, then return.
    else{
        //mark the current position of the cube as visited.
            cube[x][y][z] = 1; 

   /////Moves in every direction possible.  
            recursive_dumb_solution(cube,  x+1,  y,  z, length+1,'x',prev_dir);
            recursive_dumb_solution(cube,  x-1,  y,  z, length+1,'x',prev_dir);
            recursive_dumb_solution(cube,  x,  y+1,  z, length+1,'y',prev_dir);
            recursive_dumb_solution(cube,  x,  y-1,  z, length+1,'y',prev_dir);
            recursive_dumb_solution(cube,  x,  y,  z+1, length+1,'z',prev_dir);
            recursive_dumb_solution(cube,  x,  y,  z-1, length+1,'z',prev_dir);

             cube[x][y][z] = 0;
            return;
    }
}

Edited by Lemony Syrup
Duplicate Post
  • Like 1
Link to comment
Share on other sites

  • 0
1 hour ago, hutchman said:

wow Thalia that's more than I got! I'm giving up now. can you tell your details?

Well, I seem to have forgotten the detail about having to exit the cheese so there goes that!

2 hours ago, hutchman said:

wow Thalia that's more than I got! I'm giving up now. can you tell your details?

Revised attempt. Don't know how to spoiler a photo but since it's wrong anyway, here it is. 

20170514_230429.jpg

Link to comment
Share on other sites

  • 0
Spoiler

You'll get 25 if you start with the middle of an edge. Remember, however, there are 8 corners plus 6 faces (total 14), but 12 corners and a single center (total 13). Thus, to obtain the maximum one has to start at a corner or middle of a face and end with a corner or middle of a face.

59196d08aab5f_BW.jpg.e8a31f0c65aee25aac5b81a7b046be92.jpg

Link to comment
Share on other sites

  • 0

My analysis was incomplete. If you skip the Center X, then a string of alternating C and F (with E between) is constrained by the number of E. With 12 E, at most 13 (C,F) can be interleaved with them. And, because there are only 6 F, that means the upper limit on a path would use 7 Cs and 6Fs. So as Rocdocmac says, if it's possible without touching X, it must start and end with C: CEFECEFECEFECEFECEFECEFEC. Either way, with or without the X cell, 25 appears to be the upper bound, and Thalia found one.

Link to comment
Share on other sites

  • 0

...I interpreted "have another go" as meaning more was possible... Guess I should have tried harder to spoiler.

For spoilers on phone, use (spoiler)your text here(/spoiler) but use [ ] instead of ( ).

...I interpreted "have another go" as meaning more was possible... Guess I should have tried harder to spoiler.

For spoilers on phone, use (spoiler)your text here(/spoiler) but use [ ] instead of ( ).

Link to comment
Share on other sites

  • 0

Spoiler

I've done this exercise before (round about 2005), working through each and every possible move, which naturally took a long time. I saw my solution that I printed out at that time about three months ago, but now I can't find it anywhere! I'm almost certain that the mouse's path went through all 27 cubes, but so far I couldn't replicate that! Till I find that printed solution again, we'll have to accept 25 as the maximum and Thalia was indeed the winner. So, apology for the "have another go"!. Incidentally, if the center is omitted, you still get 25 of the 26 remaining cubes.

 

 

No center.jpg

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...