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!
3 comments:
Seems like the broad goal is to find a Hamilton circuit through the Cayley graph?
As for the specific method, is there a reason to believe problems 3 and 4 will have solutions?
Right! That about sums up the question. We'd like to find a Hamilton circuit through the Cayley graph of the group (the Rubik group / the symmetric group, ...).
The specifics are that:
* We're talking specifically about the Cayley graph of group G whose directed edges correspond to cube moves or to (specific) transpositions.
* The circuit should first traverse a complete set of coset representatives of subgroup H and then step into the next set of coset representatives.
* Subgroup H should be a fairly large cyclic subgroup, hopefully largest possible, so that the set of coset representatives is kept "small".
* The result is that we can repeat a specific sequence of |G|/|H| moves exactly |H| times to traverse the entire Cayley graph.
By the way, did you hear that it is now known that God's number is 20? http://cube20.org/
One of LZ's former students set the lower bound of 20 and upper bound of 29 in 1995.
Awesome! I didn't even know it was called "God's number."
In a way it's sort of nice that this project didn't find optimal solutions for every position; there's still some mystery left to the cube. At Williams somebody told me Checkers had been completely solved and there is an online computer program that plays it perfectly; this is cool but also sort of sad to me. All the mystery has been exhausted.
Post a Comment