7
$\begingroup$

I am looking for a proof verification. I often find these concepts simple, but struggle to communicate them clearly. Communication in mathematics is very important to me: Examples could be:

  • Any mistakes or vagueness.
  • Comments to make my arguments shorter.
  • An alternative proof or reference to an alternative proof, I could not find this problem anywhere.

I want to prove that it is not possible to have a Rubik's cube in an arbitrary state for which there exists a set of moves $S$ that solves the Cube.

The restriction here is that we first look at a cube, if it's not solved, we close our eyes and apply that set of moves, look at it again, if it's not solved, repeat the same moves. We do this over and over again. Sure there is a very very long sequence of moves that goes through all possible configurations, but you might skip a solved cube if you have your eyes closed.

No single set of moves $S$ exist, such that is solves the cube from any given configuration.

We will show that there exists no set of moves $S$ that can solve the cube from any given starting position. We will argue by contradiction. Suppose it is possible to solve any state by repeating a certain set of moves. the moves then must cycle through every possible configuration, as every single configuration must lead to a solved cube, at some point. We then know that the Rubik's cube is cyclic and it has the single generator, namely this set of moves called $S$.

Lemma: Any cyclic group is Abelian

First observe that any element in a cyclic group can be represented in terms of the cycle generator $c$, so for $a,b \in \mathbb Z$ we know that some arbitrary elements in this cyclic group are given by $x=c^a$ and $y = c^b$. Now notice that for any cyclic group we have that the generator $c$ satisfies $$xy=c^a c^b= c^{a+b}=c^{b+a}=c^b c^a=yx$$ because addition in $\mathbb{Z}$ is commutative, it is a ring after all.
This means that if the group is cyclic it must also be Abelian, which it clearly isn't, we use $r^2 g^2 r^2 $ versus $r^2 r^2 g^2 $ as a counterexample. We reach a contradiction, hence no such set of moves $S$ exists. $\square$

$\endgroup$
  • 5
    $\begingroup$ So what exactly is your question? The proof looks fine to me. Is it <proof-verification>? $\endgroup$ – Babelfish Feb 18 at 9:02
  • 1
    $\begingroup$ added the tag* my bad $\endgroup$ – Wesley Strik Feb 18 at 9:21
  • 1
    $\begingroup$ proof also lgtm $\endgroup$ – timidpueo Feb 18 at 14:56
  • 1
    $\begingroup$ One might note that $c^{a+b} = c^{b+a}$ isn't so much about $\mathbb Z$, but more the associativity of the group. You have $c^{a+b} = \underbrace{c\cdot \ldots\cdot c}_{a+b \text{ times}} = \underbrace{c\cdot\ldots\cdot c}_{b \text{ times}} \cdot \underbrace{c\cdot\ldots\cdot c}_{a\text{ times}} = c^b \cdot c^a$. This implies that the cyclic group is isomorphic to $\mathbb Z/_n$ or $\mathbb Z$. $\endgroup$ – Babelfish Feb 18 at 15:00
  • 1
    $\begingroup$ Lol wesley nice huiswerk voor adm $\endgroup$ – QuestionMaker Feb 18 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.