Rubik’s Cube Conversation over Breakfast

If you read my previous post then you know that I’m at HCSSiM for the second half of the second half, teaching a mini on the Fundamental Theorem of Algebra. I’m very impressed with everything, from the teaching faculty to the students, and am really enjoying soaking in interesting mathematics every day. There is really high level mathematics going on here, and the students are truly immersed in mathematical knowledge and culture.

Conversation at breakfast with Lucas and Gabe.

I walked into a conversation about Rubik’s Cube records this morning at breakfast. Talking about new cube records, Lucas complained about kids who ask him if he solves the cube by just doing the same sequence of moves over and over again. Of course not! This would only work in a cyclic group!

However, I argued that it is possible, if you look at it another way. Suppose that g is a long sequence of moves that traverses through all possible cube positions. Then you only have to do the sequence g once, and somewhere along the way, you’ll have solved the cube. Notice that the end result of performing the moves in sequence g is the identity permutation on the cube.

We can improve this by finding a cube permutation g that generates a large cyclic subgroup of the cube group. Let G be the cyclic subgroup generated by g. If we can express g as a long sequence of cube moves that traverses through a complete set of coset representatives of G, then we have the cube neophyte’s dream: a sequence of cube moves, that it you do over and over again, will eventually solve the cube (of course, in the worst case scenario you’ll move through all possible configurations of the cube, but I’m not making any claim about the efficiency of this method!)

We finished our breakfast conversation by posing a more reasonable problem: try this for a small group.

1. Show that g = (1, 2, 3)(4, 5) is an element of S_5 of maximal order.
2. Find a sequence of 120/6 = 20 permutations s_1, s_2, …, s_20 whose product is g, and whose partial products (s_1), (s_1 s_2), (s_1 s_2 s_3), …, (s_1 s_2 s_3 … s_20) is a set of coset representatives of the cyclic subgroup .
3. Solve problem 2, where each s_i is a transposition.
4. Solve problem 2, where each s_i is a transposition of adjacent elements.

This seems like a good start to investigating the breakfast conversation problem. Let me know what you think!