... at most. Because you might visit states multiple times.Originally Posted by 930913
Very nice. However, he doesn't only consider the states after each algo application but also the states visited during each algo application. And repeating for example RU' does visit both R and U (or even more trivially, take RR'U).
Last edited by Stefan; 06-17-2012 at 04:12 AM.
oops. should have looked up the meaning of "traverse"
Even if the algorithm wasn't traversing the cube, there is just a small flaw to your proof.
From your algebra, you assume that your "+" function, which does not add anything but rather composes two moves on the cube (g*a and g*b), is commutative. The only little mistake here is assuming that the composing functions has the same properties as the plus function, since you gave them the same symbol. If we let + be the function that composes two moves on the cube, as you have, then obviously U+R =/= R+U, regardless of them being g*a or g*b, so there still could be a Devil's/God's Algorithm.
EDIT: I was being stupid. You're right whauk and Stefan.
Last edited by calebcole203; 06-17-2012 at 10:16 PM.
No, his proof is alright. He didn't write
RU=(g*a)+(g*b)=g*b+g*a=UR,
he specifically wrote
RU=(g*a)+(g*b)=g*(a+b)=g*(b+a)=g*b+g*a=UR.
Yes, there is no full sequence g such that g^a=R and g^b=U for some a and b. This is a pretty clear result and there are a bunch of ways you can explain it - here's another:
- every sequence has a maximum order of 1260 (if the centers are fixed)
- g^a is always one of those 1260 positions (one of which is solved) for any integer a
- performing one of those positions and then another will always give one of those positions, since (g^a)(g^b) = g^(a+b)
- if both R and U are among those 1260 positions, then all sequences like RU, UR, UR2, RUR'URU2R', etc. are among those 1260 positions, and clearly there are more than 1260 of those, so we have a contradiction.
As far as I know, though, there's nothing theoretically stopping us from making a sequence that is about 1/1260 of the length of the full Devil's Algorithm, such that applying the sequence over and over will go through every position at some point (i.e. the sequence 1260 times is its own Devil's Algorithm). It wouldn't help much in practice, though, since it would still be over 10^16 moves long.
Thank you. Here's to many more.
Good point; I was thinking about a short sequence that doesn't come back on itself - no state can be repeated at either end, or infinite loops occur.
So the question remains, what's the shortest algorithm that we can come up with? (Can we fit it on a single piece of paper with the note "repeat many times"?)
Not in a useful way. Like qqwref said, it would still be over 10^16 moves long. You'd need reeeaaally good glasses.
I have seen this web site (http://anttila.ca/michael/devilsalgorithm/) that gives a definition for a Devil's Number and a Devil's algorithm that is similar or the same as what's being discussed in this thread.
What hasn't been stated clearly is if the last iteration of the sequence must execute the full sequence, or if the Hamiltonian circuit can be completed somewhere in the middle of the last iteration of the sequence. If we allow the Hamiltonian circuit to be completed somewhere in the middle of the sequence, we can find upper bounds for (this definition of) Devil's number below
43,252,003,274,489,856,000.
For example, we can let P=UR, and find a place in my Hamiltonian circuit where URUR occurs. We can start the cycle at that point, and then call the rest of the Hamiltonian circuit Q. So the Hamiltonian circuit is PPQ. Then we can cyclic shift to get the Hamiltonian circuit PQP. We can consider that we just need to repeat PQ, and after the P is executed the 2nd time, we will have done a Hamiltonian circuit. Since PQ has length 43,252,003,274,489,855,998, we have that number as an upper bound for Devil's number.
Of course, larger sequences that can be used for P are easy to find within my Hamiltonian circuit, reducing the upper bound even more.
I agree, annoying website. It just has to solve the cube at some point during or after an iteration of the algorithm. Of course, if it had to solve it after, (not just during), some number of iterations then the sequence would have to be 20 moves or less due to the fact that you can get from one state to any other you like in 20 moves or less. I think no such sequence exists to do that, it has to be really long, and go through many different states during it's execution.
No u
The site is alright. I doubt you even read it. And you apparently misunderstood Bruce. A lot.
As stated/explained in this thread aaand on that site that you find so annoying.
Posting Permissions
Reply With Quote
Bookmarks