Rubik's cube problem

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ilikejam

34 posts

ilikejam

#1 h Mar 28, 2025, 12:58 AM

Y by

If I have a solved Rubik's cube, and I make a finite sequence of (legal) moves repeatedly, prove that I will eventually resolve the puzzle.

(this wording is kinda goofy but i hope its sorta intuitive)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jkim0656

500 posts

jkim0656

#2 h Mar 28, 2025, 1:02 AM

Y by

if u say "eventually," doesn't that mean an infinite number of moves?
I mean all rubik's cubes can be solved from any position in 20 moves, so with luck and infinite time you will get those 20 or less moves all correct.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

aidan0626

1810 posts

aidan0626

#3 h Mar 28, 2025, 1:04 AM

Y by

oh i've thought about this before
imagine all possible rubik's cube positions as vertices, and put them on a directed graph, with an edge from one position to another if the sequence turns the first position into the second
note that every vertex has an indegree of 1 and outdegree of 1
now assume you can't resolve the puzzle, that means you get stuck in a cycle not containing the original position
but to get into such a cycle without the original position, there must be a vertex with an indegree greater than 1 (not sure how to rigorously show this, but inuitively makes sense), which is a contradiction

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kred9

1015 posts

kred9

#4 h Mar 28, 2025, 1:11 AM

Y by

By the Pigeonhole Principle, there must be some state of the cube that is achieved twice after applying this algorithm arbitrarily many times. Therefore, repeating the algorithm some number of times brings a state back to itself, and hence it will bring the solved state back to itself.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jkim0656

500 posts

jkim0656

#5 h Mar 28, 2025, 1:13 AM

Y by

kred9 wrote:

By the Pigeonhole Principle, there must be some state of the cube that is achieved twice after applying this algorithm arbitrarily many times. Therefore, repeating the algorithm some number of times brings a state back to itself, and hence it will bring the solved state back to itself.

dang well said
that's smart

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jasperE3

11149 posts

jasperE3

#6 h Mar 28, 2025, 4:29 AM

Y by

Theorem 4.2.2 provides an upper limit with only face turns (standard HTM) of $1260$ moves.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

fruitmonster97

2430 posts

fruitmonster97

#7 h Mar 28, 2025, 6:17 PM

Y by

kred9 wrote:

By the Pigeonhole Principle, there must be some state of the cube that is achieved twice after applying this algorithm arbitrarily many times. Therefore, repeating the algorithm some number of times brings a state back to itself, and hence it will bring the solved state back to itself.

I must be missing something, but what if(theoretically) every position except the solved state is in a loop? Yes, the first unsolved position will repeat, but that yields no insight on why the solved face should repeat?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Coolmanppap3

1 post

Coolmanppap3

#8 h Mar 28, 2025, 6:31 PM

Y by

fruitmonster97 wrote:

kred9 wrote:

By the Pigeonhole Principle, there must be some state of the cube that is achieved twice after applying this algorithm arbitrarily many times. Therefore, repeating the algorithm some number of times brings a state back to itself, and hence it will bring the solved state back to itself.

I must be missing something, but what if(theoretically) every position except the solved state is in a loop? Yes, the first unsolved position will repeat, but that yields no insight on why the solved face should repeat?

In theory, that solution would take a long time, but it will happen, right? Imagine it like a circle. Every time you bend the circle to make another, the start still remains, even though there is a detour. In a sense, it would loop back, after many loops. (I have no idea btw)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

greenturtle3141

3541 posts

greenturtle3141

#9 h Mar 28, 2025, 8:07 PM

Y by

The generalization of this is phrased in terms of group theory: "in a finite group, every element has a finite order". Here the group is the permutations you can make on a rubiks cube through legal moves. the order of a certain combination of moves is how many times it needs to be repeated to go back to the "nothing happened" outcome (called the "group identity").

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mpcnotnpc

44 posts

mpcnotnpc

#10 h Mar 28, 2025, 9:58 PM

Y by

kred9 wrote:

By the Pigeonhole Principle, there must be some state of the cube that is achieved twice after applying this algorithm arbitrarily many times. Therefore, repeating the algorithm some number of times brings a state back to itself, and hence it will bring the solved state back to itself.

Wait is this true? This only implies that some state might repeat, doesn't mean that the initial state will.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

vincentwant

1282 posts

vincentwant

#11 h Mar 28, 2025, 10:18 PM

Y by

mpcnotnpc wrote:

kred9 wrote:

By the Pigeonhole Principle, there must be some state of the cube that is achieved twice after applying this algorithm arbitrarily many times. Therefore, repeating the algorithm some number of times brings a state back to itself, and hence it will bring the solved state back to itself.

Wait is this true? This only implies that some state might repeat, doesn't mean that the initial state will.

correct me if im wrong but if its not the initial state then its not a group (im rusty at group theory tho so)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joeym2011

469 posts

joeym2011

#12 h Mar 28, 2025, 10:38 PM

Y by

Redacted, misinterpreted problem

This post has been edited 1 time. Last edited by joeym2011, Mar 28, 2025, 11:18 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kred9

1015 posts

kred9

#13 h Mar 28, 2025, 11:10 PM

Y by

fruitmonster97 wrote:

kred9 wrote:

By the Pigeonhole Principle, there must be some state of the cube that is achieved twice after applying this algorithm arbitrarily many times. Therefore, repeating the algorithm some number of times brings a state back to itself, and hence it will bring the solved state back to itself.

I must be missing something, but what if(theoretically) every position except the solved state is in a loop? Yes, the first unsolved position will repeat, but that yields no insight on why the solved face should repeat?

mpcnotnpc wrote:

kred9 wrote:

By the Pigeonhole Principle, there must be some state of the cube that is achieved twice after applying this algorithm arbitrarily many times. Therefore, repeating the algorithm some number of times brings a state back to itself, and hence it will bring the solved state back to itself.

Wait is this true? This only implies that some state might repeat, doesn't mean that the initial state will.

I'll address these two concerns with my solution. Write the algorithm as $g$ . Then suppose $g^a$ and $g^b$ correspond to the same state (some distinct values of $a$ and $b$ must satisfy this by PHP). Therefore, applying the algorithm $b-a$ times to a state returns that state back to itself. This is true no matter what state we are currently at, since every piece is unique on the cube. This means that after $b-a$ algorithms at the beginning, we will return to the solved state.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ilikejam

34 posts

ilikejam

#14 h Mar 28, 2025, 11:30 PM

Y by

my solution was that every square (the small ones, there are 9 on each side) moves to a certain position, and the square that was in that position moves to a new one, etc. this will eventually become a cycle, and even though there may be more than one such cycle, given enough repetitions, all the cycles will eventually loop back to the starting, and thus solved, state.

This post has been edited 1 time. Last edited by ilikejam, Mar 28, 2025, 11:46 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ilikejam

34 posts

ilikejam

#15 h Mar 28, 2025, 11:50 PM

Y by

jkim0656 wrote:

if u say "eventually," doesn't that mean an infinite number of moves?
I mean all rubik's cubes can be solved from any position in 20 moves, so with luck and infinite time you will get those 20 or less moves all correct.

no i mean i have a certain sequence of moves, maybe like ULU that i repeat until it solves itself

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mpcnotnpc

44 posts

mpcnotnpc

#16 h Mar 29, 2025, 12:59 AM

Y by

oop im not familiar with rubik's cube rules, but "legal" moves don't incorporate like turning a side back and forth right; cuz that's like a finite sequence?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jasperE3

11149 posts

jasperE3

#17 h Mar 29, 2025, 2:38 AM

Y by

If you turn a side back and forth by $90^\circ$ and then $-90^\circ$ then trivially the puzzle gets resolved after applying this finite sequence of legal moves.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

wuwang2002

1196 posts

wuwang2002

#18 h Mar 30, 2025, 1:40 AM

Y by

jasperE3 wrote:

Theorem 4.2.2 provides an upper limit with only face turns (standard HTM) of $1260$ moves.

when i was small i counted all 1260 moves and surprisingly didn’t mess up (so much dedication)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mpcnotnpc

44 posts

mpcnotnpc

#19 h Mar 30, 2025, 5:15 AM

Y by

jasperE3 wrote:

If you turn a side back and forth by $90^\circ$ and then $-90^\circ$ then trivially the puzzle gets resolved after applying this finite sequence of legal moves.

:skull: mb

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ilikejam

34 posts

ilikejam

#20 h Mar 30, 2025, 1:51 PM

Y by

some clarifications:

mpcnotnpc wrote:

oop im not familiar with rubik's cube rules, but "legal" moves don't incorporate like turning a side back and forth right; cuz that's like a finite sequence?

no i mean like no breaking the cube, only twisting the sides, back and forth is ok.

jasperE3 wrote:

If you turn a side back and forth by $90^\circ$ and then $-90^\circ$ then trivially the puzzle gets resolved after applying this finite sequence of legal moves.

yes, however the problem is to prove that every sequence eventually solves the cube, not to find just one.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jasperE3

11149 posts

jasperE3

#21 h Mar 30, 2025, 5:46 PM

Y by

I was responding to #16 not the original post.

Z K Y