Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Imagine that you have a cube skeleton, like so:
Skeleton

Further imagine that you have three rubber bands that you can loop through any of the faces. However, only one rubber band may go through any particular face at any time. In addition, all 6 faces must be occupied, although any number of rubber bands may be used. I have found 16 solutions, not counting reflections and rotations.

12
34
56
78
910
1112
1314
1516

Well...did I get all of the solutions? Also, how would I go about this analytically, preferably with graph theory?

share|improve this question
    
I'm pretty sure you got all the solutions with more than one loop. I don't see an easy way of doing this except by simply enumerating all the possibilities systematically, which I discovered is rather tedious. Interesting question! Next you can try this for the other platonic solids. –  Grumpy Parsnip May 17 '11 at 1:03
    
@Jim Conant: Extending it to other solids is precisely why I asked for an analytical method... :P To be more accurate, any polyhedron with an even number of faces can be done this way. –  El'endia Starman May 17 '11 at 1:05
    
By the way, if you want to interpret this in a graph theory context, you are really counting the number of ways to put a disjoint union of cycles onto the 1-skeleton of an octahedron, the dual of the cube, so that every vertex is covered exactly once, up to graph isomorphism. This helps a little bit in the enumeration, but it is still a tedious case analysis. –  Grumpy Parsnip May 17 '11 at 1:08
    
@Jim Conant: By 1-skeleton, you mean an octahedron with opposite vertices also connected, yes? Also, I'm actually more concerned with the number of solutions; enumeration is more easily accomplished with a computer program. –  El'endia Starman May 17 '11 at 1:13
    
I just meant the edges and vertices and not the faces. I guess you could also think of your problem as connecting the opposite vertices of an octahedron by a different color edge. Then you are looking for disjoint unions of cycles that cover every vertex, up to graph isomorphism that preserves edge color. By the way, I think the fact that you are dividing by the automorphisms of the cube is what makes this count difficult. –  Grumpy Parsnip May 17 '11 at 1:21

1 Answer 1

In general we need to combine two perfect matchings on the faces, one for the inside and one for the outside. For the cube in particular, we have just 6 faces, and each of the three edges in a perfect matching connects either adjacent or opposite faces. There can be either 0, 1, or 3 pairs of opposite faces matched.

number of matched opposite faces

                   inside
              3      1          0
         3   3a     [1]        [1]        [n] means that n configurations
outside  1   4b   3b,4a,7a    7b,8b           are missing from the pics
         0   6b    1b,6a   2a,5a,1a,5b

(btw, note that pic 2b is not valid, and 7a=8a reflected)

So I agree that there are 16 solutions. But each of the 9 cases in the table above required some geometrical reasoning, so let's also try the cycle-decomposition approach to see if it is any more tractable.

As described in the comments above, a rubber band arrangement is equivalent to a decomposition of the faces into even-length cycles, where the cycle is the sequence of faces taken by the rubber band oriented so that it enters the polyhedron through the first face (according to some fixed ordering of the faces) in the cycle, then alternates exiting and entering for the rest of the cycle.

There can be 1 cycle of length 6, or 1 of length 4 and one of length 2, or 3 of length 2.

1 cycle of length 6:
    (top, bottom, front, back, left, right)          6b
    (top, bottom, front, left, back, right)          6a
    (top, bottom, front, left, right, back)          7a
    (top, front, bottom, back, left, right)          6a again
    (top, front, bottom, left, back, right)          5b
    (top, front, bottom, left, right, back)          8b
    (top, front, back, bottom, left, right)          7a again
    (top, front, back, left, bottom, right)          8b again
    (top, front, back, left, right, bottom)          2nd missing case
    (top, front, left, bottom, back, right)          5a
    (top, front, left, back, bottom, right)          5b again
    (top, front, left, back, right, bottom)          8b again again
    (top, front, left, bottom, right, back)          5b again again
    (top, front, left, right, bottom, back)          6a again again
    (top, front, left, right, back, bottom)          7a again again
1 cycle of length 2 and 1 cycle of length 4:
    (top, bottom), (back, left, front, right)        4a
    (top, bottom), (back, left, right, front)        1st missing case
    (top, bottom), (back, front, left, right)        4b
    (back, bottom), (left, right, top, front)        1b
    (back, bottom), (left, top, right, front)        1a
    (back, bottom), (left, top, front, right)        7b
3 cycles of length 2:
    (top, bottom), (front, back), (left, right)      3a
    (top, bottom), (front, left), (back, right)      3b
    (top, front), (left, bottom), (back, right)      2a

Well, this one required geometrical reasoning at each step also, so the most we can say is that we are more sure about the cube now, since we got the same 16 solutions again.

For the general case, perhaps something like Pólya's counting method could be adapted to these decompositions into even-length cycles (as opposed to colorings), to handle the symmetries of the polyhedron in question, but it doesn't look straight forward.

share|improve this answer
    
Ah, progress! :D –  El'endia Starman May 30 '11 at 21:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.