Friday, May 29, 2009

A few days ago when Thomas was toying with the Rubik's Cube a interesting question came up. Will a set series of moves repeated eventually bring the Cube back to the origin arrangement? I thought about the question for a bit, and responded that it would. I'm curious if anyone also had any thoughts on the subject-- and if you're not interested, I'm not surprised in the least.

My thoughts about the problem were as follows, and for simplicity's sake I will refer to the origin arrangement as "solved."

Hypothesis(1): That any set of moves of an arbitrary size will, upon repetition, bring the cube back to solved.

Proof:

Assume(1): That there is a set of moves that will, upon repetition, never solve the cube.
Assume(2): This set of moves will never find a non-solved arrangement a second time.
Fact: There is a finite number of states for the cube.
Fact: If that move set was done more times than that number, it would find a non-solved arrangement a second time.
Conc(1): Assume(2) is false.

Assume(3): This set of moves can visit a non-solved arrangement any amount of times without visiting the solved state a second time.
Fact: If we treat this non-solved arrangement as the origin and do the move the proper amount of times, it will visit this arrangement again.
Conc(2): Assume(1) is false.

Fact: If Assume(1) is false, Hypothesis(1) is true.
Conc(3): Hypothesis(1) is true.


Conclusion:
Any given set of moves, upon repetition, will bring the state of the cube back to the origin state. It just might take a very, very long time.

More interesting questions, some of which beyond my level.
1. What is the set of moves which takes the shortest to terminate?
2. The longest?
3. What is the set of moves which visits the smallest amount of permutations before termination?
4. The largest amount?

The first and third I can answer. The set of moves for both cases is any one face-turn repeated four times, it only requires one application (1) and only visits one state (3).

Any thoughts on questions 2 and 4? Criticisms of my logic? Random comments?

1 comment:

  1. Not of general interest indeed! Honors Programming has gone to your head, man. . . ;)

    ReplyDelete