Looping or Repeating Algorithms?

[Stefan]

However, if you assume he was only talking about 3x3 algs (or even NxN algs), his post was in fact correct

No it wasn't. Let me quote him again:

Yep, all algorithms repeated enough times will return to its original position.
If it didn't, then that [would] mean the rubik's cube has infinite positions

The highlighted part is the problem. Because not-returning-to-start alone isn't sufficient. And if you argue that he can leave part of the proof out because it's true in the context of the 3x3x3, then I argue that he could leave the *whole* proof out. If you write a proof, don't omit crucial non-obvious parts and pretend it to be a proof. That's wrong.

Plus, looking at his latest post makes me think he still didn't quite understand the problem yet. I mean, why else would he elaborate on the boring cases but not even mention the one crucial case (let alone show that it can't occur)?

By the way, Think-a-Dot actually doesn't violate the invertible condition, ...

Ah yes, I see it now. Thanks once more.

 

[Stefan]

But if you were repeating an algorithm and eventually got back to the original state, or start cycling between positions you've already encountered then it doesn't have infinite positions.

You mean the path created by the algorithm. The puzzle could have infinite positions.

And again that's not true in general. You need determinism for that. Otherwise this is a counter-example:
StartState -> StateA -> StartState -> StateA -> StateB -> StateA -> StateB -> ... (toggling between StateA and StateB)

Gah, that last paragraph was wrong, sorry. Fixed it now:

And if you don't have determinism, then even the path can have infinitely many positions despite getting back to the original state:

Original state
NEW
Original state
NEW
NEW
NEW
NEW
NEW
NEW x infinite

 

[Stefan]

Yep, all algorithms repeated enough times will return to its original position.
If it didn't, then that [would] mean the rubik's cube has infinite positions

[...] If you write a proof, don't omit crucial non-obvious parts and pretend it to be a proof. [...]

Btw, note that I didn't complain about him stopping at "would mean rubik's cube has infinite positions". Because stating (or even proving) that the cube only has finitely many positions I'd say *is* obvious. So I *did* allow him to take advantage of the context ("allow" is of course a bad word but I can't think of a better one and need to leave right now).

 

[AndyRoo789]

But if you were repeating an algorithm and eventually got back to the original state, or start cycling between positions you've already encountered then it doesn't have infinite positions.

You mean the path created by the algorithm. The puzzle could have infinite positions.

And if you don't have determinism, then even the path can have infinitely many positions despite getting back to the original state:

Original state
NEW
Original state
NEW
NEW
NEW
NEW
NEW
NEW x infinite

Okay, I see how I was wrong.
Under those circumstances, the puzzle might have infinite positions, but it also might not.

If you were repeating an alg and you always encountered a new position, it would look like this...

But if you were repeating an alg and eventually came back to the original position, it would looks like this...

Yeah. So? What about the crucial third case? If you want to argue that there are no black swans, stop showing me white swans.

For the third case, I'm not completely sure that I understood it properly, but this is what I think it would look like...

Original state
State A
State B
State C
State A
State B
State C
etc.

I think that's how it is, because it's cycling between a number of different states (State A, B, C).
From how I look at it, this is impossible on a 3x3 rubik's cube because...

For state C to lead back to State A, State C would have to be the same as the original state since the original state also leads to State A.
Things might be different on other puzzles though.

 

[AndyRoo789]

However, if you assume he was only talking about 3x3 algs (or even NxN algs), his post was in fact correct

No it wasn't. Let me quote him again:

Yep, all algorithms repeated enough times will return to its original position.
If it didn't, then that [would] mean the rubik's cube has infinite positions

The highlighted part is the problem. Because not-returning-to-start alone isn't sufficient. And if you argue that he can leave part of the proof out because it's true in the context of the 3x3x3, then I argue that he could leave the *whole* proof out. If you write a proof, don't omit crucial non-obvious parts and pretend it to be a proof. That's wrong.

It may have been an insufficient proof, but what I said was true. I think there's nothing wrong with my post only mentioning 3x3x3 because he was only asking about the 3x3x3.

Plus, looking at his latest post makes me think he still didn't quite understand the problem yet. I mean, why else would he elaborate on the boring cases but not even mention the one crucial case (let alone show that it can't occur)?

Look at my previous post, I think it shows my thoughts on that case.

 

[AndyRoo789]

Yep, all algorithms repeated enough times will return to its original position.
If it didn't, then that [would] mean the rubik's cube has infinite positions

[...] If you write a proof, don't omit crucial non-obvious parts and pretend it to be a proof. [...]

Btw, note that I didn't complain about him stopping at "would mean rubik's cube has infinite positions". Because stating (or even proving) that the cube only has finitely many positions I'd say *is* obvious. So I *did* allow him to take advantage of the context ("allow" is of course a bad word but I can't think of a better one and need to leave right now).

Yes, I agree that it IS quite obvious that a rubik's cube has finite positions, but that isn't what I said. I wasn't trying to prove that the rubik's cube has finite positions, I was trying to prove that when algorithms are repeated enough times, the cube will return to its original position.

 

[Stefan]

Original state
State A
State B
State C
State A
State B
State C
etc.

I think that's how it is, because it's cycling between a number of different states (State A, B, C).
From how I look at it, this is impossible on a 3x3 rubik's cube because...

For state C to lead back to State A, State C would have to be the same as the original state since the original state also leads to State A.

Yeah, that's it (and now it's almost like rjohnson_8ball's explanation earlier).

It may have been an insufficient proof, but what I said was true.

Contradiction right there. Let me abstract. Your post looked like this:

Statement. "This is why:" Explanation.

The Statement was correct, the the Explanation was correct, but saying "This is why" was wrong.

Also, let me try an analogy to show the implications:

Imagine you have a young son and he asks you "Daddy, what is a grocery store?". And you answer "Well, son, it's a place where you get food". Next day he brings a lot of food home and you ask "Son, where did you get that?" and he says "At the grocery store" and you ask "But how did you pay for it?" and he replies "What do you mean, pay?".

Even if *you* know that one should pay, teaching your son insufficiently about the grocery store was a mistake.

Same here with cubing, when you tried to explain why algs return to start. Even if you're aware of the general possibility of "entering a cycle" and that it's not possible on the 3x3x3 (and I'm not exactly sure you were aware of it), it's bad to leave it out of the explanation. Because the person you taught most certainly didn't realize that your proof was incomplete, and thinks it's complete. You made him think something wrong. That is not good.

I think there's nothing wrong with my post only mentioning 3x3x3

Um... I never said there's something wrong with that?

Btw, note that I didn't complain about him stopping at "would mean rubik's cube has infinite positions". Because stating (or even proving) that the cube only has finitely many positions I'd say *is* obvious.

I wasn't trying to prove that the rubik's cube has finite positions

I know. Sorry, let me fix it:

Btw, note that I didn't complain about him stopping at "would mean rubik's cube has infinite positions", not stating that we have reached a contradiction (because the cube only has finitely many positions).

If you go to university or so, be prepared to get score subtractions if you leave out the punch line of a proof like that. At least in Germany, where we don't buy our grades like they do in North America.

 

[AvGalen]

If you go to university or so, be prepared to get score subtractions if you leave out the punch line of a proof like that. At least in Germany, where we don't buy our grades like they do in North America.

That last sentence would have made a good (and funny) punchline if it wasn't grammatically incorrect. Where is the verb?

 

[elcarc]

you guys turned an easy question into a mathematical argument:fp

 

[Stefan]

If you go to university or so, be prepared to get score subtractions if you leave out the punch line of a proof like that. At least in Germany, where we don't buy our grades like they do in North America.

That last sentence would have made a good (and funny) punchline if it wasn't grammatically incorrect. Where is the verb?

What do you mean?

you guys turned an easy question into a mathematical argument:fp

Yeah, and I started it with a single word! (I should've just shut up after that)

 

[hawkmp4]

you guys turned an easy question into a mathematical argument:fp

And what's wrong with that?

 

[Toad]

I love to be right and prove others wrong but I'm sure Stefan must get bored of it all the time...

I only wish I was as clever as him.

 

[qqwref]

If you go to university or so, be prepared to get score subtractions if you leave out the punch line of a proof like that. At least in Germany, where we don't buy our grades like they do in North America.

This hasn't been my experience. Are you talking about a different North America than the one I go to college in?

 

[Stefan]

This hasn't been my experience. Are you talking about a different North America than the one I go to college in?

What I meant was: I've studied and been teaching assistant both in Germany and in North America. In North America I was given points easily and was instructed to give points easily. In Germany my experience is the exact opposite. In North America it felt like teachers are supposed to let everybody pass, whereas here in Germany it's no big deal if let's say 2/3 fail. Granted, I generalized a lot from my experience with only two universities, but I believe it has to do with university in Germany being almost free and being very expensive in North America. That's what I meant with "buying grades". I got the impression that the North American mentality is "They pay so much, we can't let them fail". But again, I acknowledge my possibly false generalization.

Some examples:

In a North America course I once had four homework questions, each worth one point. I answered one question with "Sorry, no time". I got half a point for that. WTF?

As teaching assistant in North America I once had to grade students proving something. The proof required two parts (set equality, showing A<=B and B<=A). One part was trivial, could be done in one sentence. The other part was tricky and interesting and even the concise professor's solution was a paragraph with about 10 lines. Guess what - the trivial part was worth three points, the hard part only two. Many students only did the trivial part, didn't even attempt the hard part, and I still had to give them 60% of the points! WTF? Even worse, some students turned in a two-page solution for the trivial part and I had to f-ing read it all. Yeah, I graded in the empty compsci library in the evening so nobody could hear my screams of mental pain and anger (true story, not kidding).

In Germany, there once was an exam question showing a short computer program and students were asked what the program would print. It printed five squares: 1, 4, 9, 16, 25. How did we have to grade it? Four points for the fully correct answer, zero (!) points if *anything* was wrong. Even if you did realize it printed squares but started with 0 or 4 instead of 1, or forgot 25 and wrote 36 instead, that was worth *nothing*.

These are extreme examples, but I've never seen that forgiving grading in Germany or that harsh grading in America. And in general, it was way harder to get good grades in Germany. And failing a course in America seemed almost impossible.

 

[qqwref]

That doesn't mean the mentality in America is "they've paid us so we have to give them an A", though. I think the difference is in the mentality of why people are going to college. In America you basically can't get any above-minimum-wage job without having gone to college, so you pretty much have to go. I don't know what the situation is like in Germany but I think in America there is an incentive against giving people terrible grades because most people really have no choice but to graduate from college.

Also, you do have to take into account that the situation is different depending on the college and even on the teacher. At my school some teachers will give you no points if the final answer is wrong or if your proof misses some cases, while others will give you almost full credit if you make some mistakes but still clearly know what's going on. There's also a big difference between "good" colleges and the so-called "party schools" - some colleges are intended to be academically rigorous, whereas others (most of the big state universities for instance) are intended to be just places to get a degree, and are full of drinking and parties. Workplaces do know the difference, though, and while a degree from a party school is significantly better than a high school diploma a degree from a good college is much more valuable.

 

[brunson]

In case they don't teach you this in German school, the US is a very big country, bigger even than all of Europe. We have many different institutions of academic study and they are governed individually. I have a degree from a US university and your generalization is insulting at best.

 

[(R)]

I like M2 U2 M2 U2 M2 U2 M2 U2 M2 U2 M2 U2 great for ring finger exersizes and right pointer workouts

 

[elcarc]

I like M2 U2 M2 U2 M2 U2 M2 U2 M2 U2 M2 U2 great for ring finger exersizes and right pointer workouts

yesh.. on topicness

i also like an algorithm sort of like that

i use M U for a long time to practice my m slicecs. it gets solved after 8 times, but i keep going anyway

 

[Stefan]

I think in America there is an incentive against giving people terrible grades because most people really have no choice but to graduate from college.

Good point, never thought about that. The money thing was apparently more obvious. Don't really know about the job vs education situation in Germany, but I think studying at university isn't all that common and people can get good jobs without a university degree, at least if they have some skills. Germany also doesn't have a general minimum-wage, btw.

Compare the ratios:
population USA vs Germany: 3.7
post-secondary education enrollment USA vs Germany: 7.12:1

That's not the numbers for finishing degrees, sadly, couldn't find those. And Germany's education steps might not be completely comparable to USA's.

 

[Tim Major]

you guys turned an easy question into a mathematical argument:fp

Interesting to read though.