Has it been proven (or disproven) that, from a solved state, there exists a number “x” for any algorithm, such that you can perform said algorithm x times to get back to a solved state. I feel like this is something any cuber will tell you is true, but I am a mathematician first and a cuber second. I want to prove (or disprove) this mathematically if it hasn’t been done.
$\begingroup$
$\endgroup$
6
-
$\begingroup$ Are you asking if there are impossible non-solvable combinations, that no matter what you do, you won't go back to a solvable state? (there are) $\endgroup$– Quora FeansJul 16, 2020 at 8:33
-
$\begingroup$ @QuoraFeans - Are these non-solvable combinations reachable from a solved state? In other words - can you get to them only with legal moves, without taking the cube apart and reassembling it incorrectly? I'd think that's impossible since every move is reversible. $\endgroup$– G0BLiNJul 16, 2020 at 10:17
-
$\begingroup$ Yes, indeed, the unsolvable positions imply taking a physical cube apart. @G0BLiN $\endgroup$– Quora FeansJul 16, 2020 at 10:28
-
$\begingroup$ What do you mean by "algorithm": a sequence of fixed moves, or an algorithm in the usual sense that can branch based on details of the cube's state? If the latter, then the answer is simply x=1 for any solving algorithm. $\endgroup$– Greg MartinJul 16, 2020 at 21:13
-
4$\begingroup$ If you are a mathematician, then you should know the basics of group theory... $\endgroup$– qwrJul 17, 2020 at 5:40
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
13
The question is a bit unclear - it sounds like you're asking "Given a sequence of moves A, is there always some number of repetitions of A that will get you back to the start state?"
This is relatively easy to prove - it's just basic group theory.
Imagine you have a bunch of Rubik's cubes -- one in every possible state. Given an algorithm A, you can draw a sequence of arrows from one cube to the next: if you start at cube 1, apply A, and end at cube 2, then you draw an arrow from cube 1 to cube 2.
Every cube has only one arrow pointing out of it. Similarly, since you can just "undo" A, every cube can only have one arrow pointing into it.
So, if you start at the solved cube, and keep following the chain, what happens? There are a finite number of cubes, so you can't keep going forever. And you can't first repeat in the middle of your chain, because then the repeated cube would have two different cubes pointing to it. So you must hit the solved state again.
If "algorithm" does not mean "sequence of moves, independent of the current state of the cube", then the answer is easily 'no'. The algorithm "Always turn the right face, unless that would solve the cube - then turn the left face instead" will never solve the cube, no matter how many times you apply it.
-
1$\begingroup$ Great answer, also includes alternative definitions of algorithm. Hopefully you'll reach 100k soon! $\endgroup$– justhalfJul 16, 2020 at 3:05
-
5$\begingroup$ You can find a list of the orders of the permutations here, together with how many permutations have each order. The worst case is $1260=2^2\cdot3^2\cdot5\cdot7$. The LCM of these orders is $55440$, so every move sequence repeated $55440$ times has no effect. $\endgroup$ Jul 16, 2020 at 5:12
-
4$\begingroup$ For what it's worth, the term "algorithm" as used by cubers always means a fixed sequence of moves rather than the mathematical/computer definition of algorithm which could include branching. (Still worth it though to include that final caveat though since not everyone is a serious cuber.) $\endgroup$– theoszaJul 16, 2020 at 10:02
-
$\begingroup$ Another implication, incidentally, that might be worth noting explicitly: since the overall cube group isn't cyclic, there's no single move sequence $A$ such that every position is attainable by simply iterating $A$ some finite number of times (and so equivalently, there's no single move sequence $A$ such that every position can be solved back to the start state by just repeating $A$ until you reach a solved cube). $\endgroup$ Jul 16, 2020 at 20:17
-
$\begingroup$ İ don’t know much about group theory yet but you make a lot of sense. by algorithm İ mean stuff like “L R U2 B’” etc. algorithm can be any length of operations but the idea is you do the exact same turns every time. İ guess the only way you couldn’t get back to a solved state is if you some how got stuck in a loop, but this would imply that there is a state the cube can be in, which is accessible by the same algorithm, but from two different states. $\endgroup$ Jul 16, 2020 at 21:18