Speed Solving Rubik's Cube  All about speed solving the Rubik's Cube is a Public Group with 2866 members.
 Speed Solving Rubik's Cube  All about speed solving the Rubik's Cube

 Public Group,
 2866 members
Primary Navigation
Need some help with a prestentation
Expand Messages
 0 Attachment
Hey guys... and girls,
For school, I have to do a presentation about a subject of my
choice. And because the Cube is one of the things I like, and the
public = Math students, I thought it would be a nice idea to tell
them something about the cube... For example, how you can calculate
how many positions you can make. Now, I know how to prove that it's
impossible to make an odd permutation, but what's the easiest way to
prove that all even permutations are possible? (I know how to prove
this, but my proof is a bit complicated to explain to a noncuber
(and it's not really beautiful), so does anyone know a (short) way
to prove it so a noncuber can understand it quickly?)
Also, to avoid being very boring, I am looking for some nice facts
about the cube... For example: I once heard some taxlaws of Hungary
were changed, because of Mr. Rubik. Or: When you make a line of 43 *
10^18 cubes (with all different cubestates) you get a line with a
length of xxx(?) lightyears. Does anyone know more interesting
facts like this?
Thanks for helping me :),
Joel. 0 Attachment
 In speedsolvingrubikscube@yahoogroups.com, "joel_vn"
<joel_vn@y...> wrote:> what's the easiest way to
Hi Joel
> prove that all even permutations are possible? (I know how to prove
> this, but my proof is a bit complicated to explain to a noncuber
> (and it's not really beautiful), so does anyone know a (short) way
> to prove it so a noncuber can understand it quickly?)
I don't know a really nice way to do it, so will be interested to see
what others come up with. Threecycles are one possibility... but to
avoid having to treat edgesodd/cornersodd (slightly) separately
from edgeseven/cornerseven you might want to use the Tpattern
(permutation (UBL,UFL)(UR,UL)), as in Stefan's blindfold solving
method. Maybe this is what you have in mind anyway.
Presumably, when discussing even and odd perms, you would already
have mentioned that a permutation can be decomposed into a product of
transpositions. You'd then argue (with elegantly waving hands) that
any any one of these transpositions could be achieved by: (1)
manoeuvring the required pair of edges (resp. corners) into locations
UR,UL (resp. UBL,UFL) without disturbing the corners UBL,UFL (resp.
edges UR,UL); (2) performing the T move; and (3) manoeuvring the
pieces back again. This would bring in the idea of conjugates, too.
Although it is not hard to fill in the details, you perhaps couldn't
expect your audience to be that patient...
Mike 0 Attachment
This is also probably not the most elegant proof, but I always argue
based on the possible moves of the cube.
You can argue that all moves are isomorphic to R,R',R2 by using cube
rotations. Then you can show that R and R' are odd permutations by
showing that they 4cycle the corners and edges in their orbits,
then break down a 4cycle into 3 transpositions to show that it is
odd. Then show that R2 is an even permutation by performing 2
transpositions in each of the corner and edge orbits.
Then you can list a single alg, like the T perm or something, and
show how you can do a transposition in each of the edge or corner
orbit, but that this ALWAYS does a transposition in the other orbit
as well. (the moves R and R' show this by performing an odd
permutation on both orbits, so this always has to be the case).
Since you can perform a transposition in each orbit then all odd and
even permutations are possible, but the key is that both orbits have
to have the same parity.
You also have to show about the orientations of the pieces, but
after doing that you could argue in even and odd permutation cases,
since each is exactly half the number of combinations to the cube,
then add them together to get the total.
I always do the orientations by defining a hierarchy of faces,
exactly like in blindfolded cubing, and likewise examine your
possible moves R,R',R2 and you'll see that you always flip the
orientations of the pieces in the possible ways, ruling out a single
corner or edge rotated and things like that.
I don't know a shorter way to prove the orientations of the pieces,
but I remember seeing something very short in my modern algebra
class. Sadly I can't recall it very well though :(
Not sure if that was elegant or short, but that is how I prove the
number of combinations.
Chris
 In speedsolvingrubikscube@yahoogroups.com, mike_go_uk
<no_reply@y...> wrote:>
prove
>  In speedsolvingrubikscube@yahoogroups.com, "joel_vn"
> <joel_vn@y...> wrote:
> > what's the easiest way to
> > prove that all even permutations are possible? (I know how to
> > this, but my proof is a bit complicated to explain to a non
cuber
> > (and it's not really beautiful), so does anyone know a (short)
way
> > to prove it so a noncuber can understand it quickly?)
see
>
> Hi Joel
>
> I don't know a really nice way to do it, so will be interested to
> what others come up with. Threecycles are one possibility... but
to
> avoid having to treat edgesodd/cornersodd (slightly) separately
of
> from edgeseven/cornerseven you might want to use the Tpattern
> (permutation (UBL,UFL)(UR,UL)), as in Stefan's blindfold solving
> method. Maybe this is what you have in mind anyway.
>
> Presumably, when discussing even and odd perms, you would already
> have mentioned that a permutation can be decomposed into a product
> transpositions. You'd then argue (with elegantly waving hands)
that
> any any one of these transpositions could be achieved by: (1)
locations
> manoeuvring the required pair of edges (resp. corners) into
> UR,UL (resp. UBL,UFL) without disturbing the corners UBL,UFL
(resp.
> edges UR,UL); (2) performing the T move; and (3) manoeuvring the
too.
> pieces back again. This would bring in the idea of conjugates,
>
couldn't
> Although it is not hard to fill in the details, you perhaps
> expect your audience to be that patient...
>
> Mike 0 Attachment
Hi Joel,
>  joel_vn wrote:
I don't think there is a way to do it other than to explicitly
> > what's the easiest way to prove
> > that all even permutations are possible? (I know how to prove
> > this, but my proof is a bit complicated to explain to a noncuber
> > (and it's not really beautiful), so does anyone know a (short)
> > way to prove it so a noncuber can understand it quickly?)
establish an algorithm for solving any position, though it obviously
need not be at all practical.
 mike_go_uk wrote:> ... you might want to use the Tpattern
This is one of those facts which seems much deeper than it really is.
> (permutation (UBL,UFL)(UR,UL)), as in Stefan's blindfold solving
> method. Maybe this is what you have in mind anyway.
>
> Presumably, when discussing even and odd perms, you would already
> have mentioned that a permutation can be decomposed into a product
> of transpositions.
I prefer to think of it like this:
If yuo could swap any two edge piece you like (e.g. remove them, swap
and reinsert them), then it is obvious that you can put them all in
the correct place. With each swap you can bring (at least) one piece
to the position it should be.
You can go further than this. If all you could do is swap UL with any
of the other 11 edges, then it is still possible. To solve any nonUL
piece, swap it with UL, and then bring it from UL to the position you
want it with another swap. So with 2 swaps you can solve any nonUL
piece, without disturbing any other solved nonUL pieces. Eventually
all you might be left with is a swap to solve UL and the last piece.
All you need to show now is that you can swap any of the 11 nonUL
edges with UL using the T permutation.
> You'd then argue (with elegantly waving hands) that
The way I did it you only need to bring one edge to UR without
> any any one of these transpositions could be achieved by: (1)
> manoeuvring the required pair of edges (resp. corners) into
> locations
> UR,UL (resp. UBL,UFL) without disturbing the corners UBL,UFL (resp.
> edges UR,UL); (2) performing the T move; and (3) manoeuvring the
> pieces back again. This would bring in the idea of conjugates,
> too.
disturbing the ULF,UL,ULB bar. This is very easy (if you allow slice
moves). Regard ULF,UL,ULB as being bandaged, like a siamese cube.
Unfortunately this only shows how to solve edges. To prove it
rigorously you would have to do the same kind of thing with the
corners.
Jaap 0 Attachment
 cmhardw wrote:> Since you can perform a transposition in each orbit then all odd
Sure, but to show that _all_ even permutations are possible, you have
> and even permutations are possible, but the key is that both
> orbits have to have the same parity.
to be able to do _any_ transposition, not just a particular
transposition.
If it were impossible to bring certain edge pairs into the right
position for the T perm to swap them.
For example, in the 2 generator group it is quite possible to do an
odd permutation of the corners, e.g. R is a 4cycle. Any conjugate of
R is also a 4cycle of corners. But it is not possible to do any
corner 4cycle, simply because the movements are too restrictive that
you cannot find a way to bring any four corners to the R face.
Jaap 0 Attachment
 In speedsolvingrubikscube@yahoogroups.com, "joel_vn"
<joel_vn@y...> wrote:>
calculate
> Hey guys... and girls,
>
> For school, I have to do a presentation about a subject of my
> choice. And because the Cube is one of the things I like, and the
> public = Math students, I thought it would be a nice idea to tell
> them something about the cube... For example, how you can
> how many positions you can make. Now, I know how to prove that
it's
> impossible to make an odd permutation, but what's the easiest way
to
> prove that all even permutations are possible? (I know how to
prove
> this, but my proof is a bit complicated to explain to a noncuber
Hungary
> (and it's not really beautiful), so does anyone know a (short) way
> to prove it so a noncuber can understand it quickly?)
>
> Also, to avoid being very boring, I am looking for some nice facts
> about the cube... For example: I once heard some taxlaws of
> were changed, because of Mr. Rubik. Or: When you make a line of 43
*
> 10^18 cubes (with all different cubestates) you get a line with a
What level are you pitching it at? (Depending on this, you may have
> length of xxx(?) lightyears. Does anyone know more interesting
> facts like this?
>
> Thanks for helping me :),
>
> Joel.
to define a lot of information in advance, which could rush the main
presentation  and could be tedious.) I will try to give some scant
details, at the risk of incurring the wrath of some.
First of all, what level of information on permutations are you
assuming. Any permutation can be broken up as a product of disjoint
cycles. (That is the cycles will have no common elements.) It can
also be broken up as a product of transpositions (2cycles). The
transpositions will not in general be disjoint. This decomposition
into cycles will not be unique but the number of multiplicands
(here, transpositions) will be invariant modulo 2 for a given
permutation. (If your audience don't know this, you're probably
going to have to get them to take this as given  otherwise you
likely won't have time to finish. It could take some time to prove.)
In particular, a cycle is odd iff it moves an even number of
elements. For example (a b c ... w x y)=(a b c ... w x)(a y) and you
can use induction.
Now, since a move is a product of quarter turns and a quarter turn
is a product of two 4cycles (one of corners and one of edges)
forgetting orientation for the present, then the permutation of the
whole will be even. The product of 2 4cycles is clearly even (the
total number of transpositions is the sum of two odd numbers and so
even). So you can't get an odd permutation. But it is possible for
the restrictions to either edge or corner permutations to be odd
individually.
Fortunately, if this is the case, then simply doing any quarter turn
will clearly fix this. Now all you need to do (in the first
instance) is prove that any even permutation of corners and any even
permutation of edges is possible.
Even permutations are generated by 3cycles:
(a b)(a c)=(a b c), (a b)(c d)=(a b c)(c a d)
So all you need to be able to show is that you can do this sort of
thing. You can use the fact that the group clearly acts 3
transitively on the corners and on the edges (in fact you can do
rather more) to show that everything can be placed using conjugation
provided you can display an edge 3cycle and a corner 3cycle.
Exhibiting these last facts should be easy, so the only thing you
need to worry about is the 3transitivity (all this means here is,
for instance, that for any 3 edges a, b, c and any 3 edge positions
x, y, z you can find a move that takes a to x, b to y and c to z).
(Alternatively, you can use a few 3cycles and then show
conjugations that will allow you to generally place everything.)
You then need to show that the total edge flip is invariant modulo 2
and the total corner twist is invariant modulo 3. (Then you can
exhibit a double edge flip (which doesn't permute the pieces) and a
double corner twist (which doesn't permute the pieces) and use 2
transitivity, a consequence of 3transitivity) to show you can
orient the pieces  using conjugation.) To show invariance, you only
need show invariance under a set of generators  typically the 6
usual generators. The tedious part will be defining the orientation
(particularly for edges) which you can do lexicographically by
ordering the faces. You should probably leave the checking of
invariance (once defined) as an exercise. Show it for a couple of
faces, probably at least one of these should exhibit that the
orientations can be changed.
After that, it's easy to calculate the total number of positions
which must be (8!*12!)/2 * 2^11 * 3^7. 0 Attachment
Hi everybody,
I just want to thank everybody for their reply's! It definitly gave
me some inspiration about how to do this! If I have more questions,
I will let you know :)...
Bye!
Joel.
 In speedsolvingrubikscube@yahoogroups.com, "joel_vn"
<joel_vn@y...> wrote:>
calculate
> Hey guys... and girls,
>
> For school, I have to do a presentation about a subject of my
> choice. And because the Cube is one of the things I like, and the
> public = Math students, I thought it would be a nice idea to tell
> them something about the cube... For example, how you can
> how many positions you can make. Now, I know how to prove that
it's
> impossible to make an odd permutation, but what's the easiest way
to
> prove that all even permutations are possible? (I know how to
prove
> this, but my proof is a bit complicated to explain to a noncuber
Hungary
> (and it's not really beautiful), so does anyone know a (short) way
> to prove it so a noncuber can understand it quickly?)
>
> Also, to avoid being very boring, I am looking for some nice facts
> about the cube... For example: I once heard some taxlaws of
> were changed, because of Mr. Rubik. Or: When you make a line of 43
*
> 10^18 cubes (with all different cubestates) you get a line with a
> length of xxx(?) lightyears. Does anyone know more interesting
> facts like this?
>
> Thanks for helping me :),
>
> Joel. 0 Attachment
I once came up with a "visualization" I like better (because I can't
really imagine a lightyear, it's so abstract).
Imagine all of human kind has done nothing but cubing since it was
invented. So let's say 6 billion people and 30 years. And let's say
we've all been cubing 24h each and every day, making one move per
second. Finally, let's assume that this world wide project is so
wellorganized that we don't waste our time by producing duplicate
states, i.e. everybody creates a new state with every move. I won't do
the math again (you can ;) but I think it turned out that only 13% or
all states have ever be reached somewhere somewhere by someone. Of
course some assumptions might slightly differ from reality and the
fraction of explored states might thus be smaller.
I was actually quite surprised by this when I computed it. A friend of
mine had asked me "don't you get the same states again and again?" and
that's why I did it. It convinced me that when I randomly scramble,
most of the states I get to while scrambling have *never appeared
anywhere*. Still awesome.
Cheers!
Stefan
 In speedsolvingrubikscube@yahoogroups.com, "joel_vn" <joel_vn@y...> wrote:
>
> When you make a line of 43 *
> 10^18 cubes (with all different cubestates) you get a line with a
> length of xxx(?) lightyears. Does anyone know more interesting
> facts like this?
>
> Thanks for helping me :),
>
> Joel. 0 Attachment
 In speedsolvingrubikscube@yahoogroups.com, GameOfDeath2
<no_reply@y...> wrote:> This decomposition
How about doing it this way:
> into cycles will not be unique but the number of multiplicands
> (here, transpositions) will be invariant modulo 2 for a given
> permutation. (If your audience don't know this, you're probably
> going to have to get them to take this as given  otherwise you
> likely won't have time to finish. It could take some time to prove.)
There are many ways to decompose a permutation, but there's an
equivalence deterministic value. The number of "wrong pairs" in the
sequence.
Number the corners 18. Let's look at this state:
position: 1 2 3 4 5 6 7 8
cubie there: 6 8 1 7 4 3 5 2
There are many ways to "solve" (i.e. sort) this with swaps. But let's
compute the number of pairs in wrong order. First number is six and
15 are all behind it, but they should come before it. So that's five
wrong pairs. The 8 has 6 smaller numbers on it's right. So, 11 wrong
pairs so far. The 1 has no smaller numbers on the right. Let me
summarize it for all:
6 8 1 7 4 3 5 2 (the cubie numbers)
5 6 0 4 2 1 1 0 (smaller numbers on the right)
Sum: 19
The point is, that you have no choice (like you have a choice which
swaps to do for solving). What's this number good for? Well, it's even
if and only if the sequence can be ordered by an even number of swaps.
This is quite easy to prove and I leave it to you ;) Here's the idea:
The sorted sequence has an even number of wrong pairs (namely zero)
and it's solvable with an even number of swaps (namely zero). And
whenever you do a swap, the number of swaps done overall changes its
"evenness" and at the same time the number of wrong pairs changes its
"evenness", too.
Cheers!
Stefan 0 Attachment
 In speedsolvingrubikscube@yahoogroups.com, "Stefan Pochmann"
<pochmann@g...> wrote:>
Yes, but there's the issue of showing that it's not possible (in some
>  In speedsolvingrubikscube@yahoogroups.com, GameOfDeath2
> <no_reply@y...> wrote:
> > This decomposition
> > into cycles will not be unique but the number of multiplicands
> > (here, transpositions) will be invariant modulo 2 for a given
> > permutation. (If your audience don't know this, you're probably
> > going to have to get them to take this as given  otherwise you
> > likely won't have time to finish. It could take some time to prove.)
>
> How about doing it this way:
>
> There are many ways to decompose a permutation, but there's an
> equivalence deterministic value. The number of "wrong pairs" in the
> sequence.
>
> Number the corners 18. Let's look at this state:
>
> position: 1 2 3 4 5 6 7 8
> cubie there: 6 8 1 7 4 3 5 2
>
> There are many ways to "solve" (i.e. sort) this with swaps. But let's
> compute the number of pairs in wrong order. First number is six and
> 15 are all behind it, but they should come before it. So that's five
> wrong pairs. The 8 has 6 smaller numbers on it's right. So, 11 wrong
> pairs so far. The 1 has no smaller numbers on the right. Let me
> summarize it for all:
>
> 6 8 1 7 4 3 5 2 (the cubie numbers)
> 5 6 0 4 2 1 1 0 (smaller numbers on the right)
>
> Sum: 19
>
> The point is, that you have no choice (like you have a choice which
> swaps to do for solving). What's this number good for? Well, it's even
> if and only if the sequence can be ordered by an even number of swaps.
> This is quite easy to prove and I leave it to you ;) Here's the idea:
> The sorted sequence has an even number of wrong pairs (namely zero)
> and it's solvable with an even number of swaps (namely zero). And
> whenever you do a swap, the number of swaps done overall changes its
> "evenness" and at the same time the number of wrong pairs changes its
> "evenness", too.
>
> Cheers!
> Stefan
other, possibly noncanonical, way) to solve using a different number
(modulo 2) of transpositions  that's crucial if you want to show that
a permutation can't be both odd and even  which is key to being able
to compute the size of the group, for instance. It's equivalent to
showing that the identity can't be expressed as a product of an odd
number of transpositions (if sigma is both odd and even then you can
write sigma*sigma' as a product of an odd number of transpositions).
The identity has no pairs in the wrong order (in terms of your post)
but it's not completely trivial to show that it can't be written as a
product of an odd number of transpositions in some way. I guess the
usual way to do it would probably to be to write the identity matrix
(of the appropriate size) as a product of an odd number of permutation
matrices (corresponding to transpositions). Since each transposition
matrix has determinant 1 (you just need to swap 2 rows to make it the
identity matrix, which has determinant 1) then the identity matrix
would have determinant (1)^k for some odd k, i.e. 1, a contradiction
and so the result would follow by reductio ad absurdum. Of course,
you'd need to prove (or assume) facts on determinants  1) the
determinant is homomorphism from the multiplicative ring of matrices
into the underlying ring (this may require certain facts about the
underlying ring, but they'd be satisfied here) and 2) interchanging 2
rows (or columns) in a matrix changes the determinant by a factor of
1. (You'd probably just need rows or columns, depending on which way
you write your permutations, but if you can prove that the determinant
is invariant under transposing the matrix then you get two for the
price of one anyway.) 0 Attachment
Hi Joel!!
U could also go about and explain some other interesting facts about
the cube. Like it's impossible to just swap 2 edges or likewise just
swap 2 corners. Or u can also look at flip and twist parity.
U can gain some knowledge by looking at the following page :
http://members.tripod.com/~dogschool/rubikscube.html
The explanations ("proofs") are very easy to follow :)
God's algorithm is also a cool topic. See Jaap's pages :)
Best of luck w ur presentation ;)
Per
>  In speedsolvingrubikscube@yahoogroups.com, "joel_vn"
<joel_vn@y...> wrote:
>
to
> Hey guys... and girls,
>
> For school, I have to do a presentation about a subject of my
> choice. And because the Cube is one of the things I like, and the
> public = Math students, I thought it would be a nice idea to tell
> them something about the cube... For example, how you can calculate
> how many positions you can make. Now, I know how to prove that it's
> impossible to make an odd permutation, but what's the easiest way
> prove that all even permutations are possible? (I know how to prove
Hungary
> this, but my proof is a bit complicated to explain to a noncuber
> (and it's not really beautiful), so does anyone know a (short) way
> to prove it so a noncuber can understand it quickly?)
>
> Also, to avoid being very boring, I am looking for some nice facts
> about the cube... For example: I once heard some taxlaws of
> were changed, because of Mr. Rubik. Or: When you make a line of 43
*
> 10^18 cubes (with all different cubestates) you get a line with a
> length of xxx(?) lightyears. Does anyone know more interesting
> facts like this?
>
> Thanks for helping me :),
>
> Joel. 0 Attachment
 In speedsolvingrubikscube@yahoogroups.com, "Per Kristen Fredlund"
<aspiring_to_love@y...> wrote:>
I presume, he mentioned that near the start where he mentioned it was
> Hi Joel!!
>
> U could also go about and explain some other interesting facts about
> the cube. Like it's impossible to just swap 2 edges or likewise just
> swap 2 corners.
impossible to do an odd permutation. (At least one assumes that is
what he meant  of course that would be an odd permutation in S_20,
but then not all even permutations are possible because you can't move
edges into corner places and vice versa.) 0 Attachment
> Yes, but there's the issue of showing that it's not possible (in
some
> other, possibly noncanonical, way) to solve using a different
number
> (modulo 2) of transpositions  that's crucial if you want to show
that
> a permutation can't be both odd and even  which is key to being
able
> to compute the size of the group, for instance. It's equivalent to
a
> showing that the identity can't be expressed as a product of an odd
> number of transpositions (if sigma is both odd and even then you can
> write sigma*sigma' as a product of an odd number of transpositions).
> The identity has no pairs in the wrong order (in terms of your post)
> but it's not completely trivial to show that it can't be written as
> product of an odd number of transpositions in some way.
That's easy, isn't it? Assume that a certain permutation can be solved
one way with 12 swaps and another way with 7 swaps. Let's assume our
permutation has 5 wrong pairs. Since each swap changes the
"even/oddness" of this number, the 12 swaps can obviously not really
solve it. Only an odd number of swaps can solve an odd permutation
since every swap changes the oddness of permutations and the identity
is not odd.
My point mainly was that you can "read" the even/oddness of a
permutation *without* writing it as some cycles. Writing it as cycles
is bad because there are different ways to do so. Writing it in "raw"
form there's just one way to do so. So unless there's a good reason to
do so (e.g. blindfold solving) I'd suggest not to use cycle notation,
but instead "raw" order.
I do understand your way of using permutation matrices and
determinants, but that's just not really solving the problem, is it?
Writing a permutation as a product of permutation matrices also has
the problem that there are infinitely many different ways to do so.
And it wastes a lot more of paper/pencil, too ;)
Cheers!
Stefan
> I guess the
permutation
> usual way to do it would probably to be to write the identity matrix
> (of the appropriate size) as a product of an odd number of
> matrices (corresponding to transpositions). Since each transposition
the
> matrix has determinant 1 (you just need to swap 2 rows to make it
> identity matrix, which has determinant 1) then the identity matrix
contradiction
> would have determinant (1)^k for some odd k, i.e. 1, a
> and so the result would follow by reductio ad absurdum. Of course,
2
> you'd need to prove (or assume) facts on determinants  1) the
> determinant is homomorphism from the multiplicative ring of matrices
> into the underlying ring (this may require certain facts about the
> underlying ring, but they'd be satisfied here) and 2) interchanging
> rows (or columns) in a matrix changes the determinant by a factor of
way
> 1. (You'd probably just need rows or columns, depending on which
> you write your permutations, but if you can prove that the
determinant
> is invariant under transposing the matrix then you get two for the
> price of one anyway.) 0 Attachment
 In speedsolvingrubikscube@yahoogroups.com, GameOfDeath2
<no_reply@y...> wrote:>
permutation
> I guess the
> usual way to do it would probably to be to write the identity matrix
> (of the appropriate size) as a product of an odd number of
> matrices (corresponding to transpositions). Since each transposition
the
> matrix has determinant 1 (you just need to swap 2 rows to make it
> identity matrix, which has determinant 1) then the identity matrix
contradiction
> would have determinant (1)^k for some odd k, i.e. 1, a
> and so the result would follow by reductio ad absurdum.
Ok, I read your exact reasoning again. I think we're actually saying
pretty much the same thing, the difference is just that you're talking
about "determinants" of "matrices" and I'm talking about "wrong pairs"
of "raw order". Well, I'd need to define mine more precisely, yours
are two simple words that are wellknown already, so... you win ;)
But I still say our proofs are equivalent...
Cheers!
Stefan 0 Attachment
Hi Per, Joel, et al,
I find it interesting that even though you can can't move only one
pair of corners or edges and nothing else, you also cannot only move
the four centers of a slice to their adjacent sides of that slice. In
other words you can swap two edges without swapping two corners (and
vice versa) if you don't require that all the centers stay in place.
In yet other words, if you physically remove two corners of a cube
and switch them it is the same as physically switching two edges. Now,
if you do that and move the center slice one quarter turn and, leave
the centers there as you solve the rest of the cube, you can solve
ther rest of the cube including swapping those two corners back.
Regards,
David J
 In speedsolvingrubikscube@yahoogroups.com, "Per Kristen Fredlund"
<aspiring_to_love@y...> wrote:>
> Hi Joel!!
>
> U could also go about and explain some other interesting facts about
> the cube. Like it's impossible to just swap 2 edges or likewise just
> swap 2 corners. Or u can also look at flip and twist parity.
>
> U can gain some knowledge by looking at the following page :
>
> http://members.tripod.com/~dogschool/rubikscube.html
>
> The explanations ("proofs") are very easy to follow :)
>
> God's algorithm is also a cool topic. See Jaap's pages :)
>
> Best of luck w ur presentation ;)
>
> Per
>
> >  In speedsolvingrubikscube@yahoogroups.com, "joel_vn"
> <joel_vn@y...> wrote:
> >
> > Hey guys... and girls,
> >
> > For school, I have to do a presentation about a subject of my
> > choice. And because the Cube is one of the things I like, and the
> > public = Math students, I thought it would be a nice idea to tell
> > them something about the cube... For example, how you can calculate
> > how many positions you can make. Now, I know how to prove that it's
> > impossible to make an odd permutation, but what's the easiest way
> to
> > prove that all even permutations are possible? (I know how to prove
> > this, but my proof is a bit complicated to explain to a noncuber
> > (and it's not really beautiful), so does anyone know a (short) way
> > to prove it so a noncuber can understand it quickly?)
> >
> > Also, to avoid being very boring, I am looking for some nice facts
> > about the cube... For example: I once heard some taxlaws of
> Hungary
> > were changed, because of Mr. Rubik. Or: When you make a line of 43
> *
> > 10^18 cubes (with all different cubestates) you get a line with a
> > length of xxx(?) lightyears. Does anyone know more interesting
> > facts like this?
> >
> > Thanks for helping me :),
> >
> > Joel. 0 Attachment
 In speedsolvingrubikscube@yahoogroups.com, "Stefan Pochmann"
<pochmann@g...> wrote:>
matrix
>  In speedsolvingrubikscube@yahoogroups.com, GameOfDeath2
> <no_reply@y...> wrote:
> >
> > I guess the
> > usual way to do it would probably to be to write the identity
> > (of the appropriate size) as a product of an odd number of
transposition
> permutation
> > matrices (corresponding to transpositions). Since each
> > matrix has determinant 1 (you just need to swap 2 rows to make
it
> the
matrix
> > identity matrix, which has determinant 1) then the identity
> > would have determinant (1)^k for some odd k, i.e. 1, a
saying
> contradiction
> > and so the result would follow by reductio ad absurdum.
>
> Ok, I read your exact reasoning again. I think we're actually
> pretty much the same thing, the difference is just that you're
talking
> about "determinants" of "matrices" and I'm talking about "wrong
pairs"
> of "raw order". Well, I'd need to define mine more precisely,
yours
> are two simple words that are wellknown already, so... you win ;
)
> But I still say our proofs are equivalent...
Actually, my main point is that you need to show that
>
> Cheers!
> Stefan
oddness/evenness can't both occur at once. To be odd just means that
the permutation can be expressed as a product of an odd number of
transpositions  to be even is similarly defined. There is a
question of whether it is possible to be simultaneously odd and even
that needs to be addressed. You've defined oddness/evenness
differently, in terms of wrong pairs and described a canonical way
of defining it, so providing a welldefined notion of odd vs even.
What it doesn't prove is that it is impossible to write an odd/even
permutation (as defined like this) as a product of an even/odd
number of transpositions. (In other words, if you didn't do it
canonically and just switched pairs and eventually came to the
identity in some nonmethodical way, how would you know that you
always take an odd (or always take an even) number of
transpositions.)
You do make some reference to this: 'And whenever you do a swap, the
number of swaps done overall changes its "evenness" and at the same
time the number of wrong pairs changes its "evenness", too.' but it
is a technical issue that does require a bit of proof (and is
equivalent to the fact that the identity permutation can't be
written as the product of an odd number of permutations). If you
could flesh out the bit I quoted from you above, we'd be on the same
track.
I guess the way I'd tackle it using your definition is to look at a
permutation (a b) (where a<b, say).
So you have 1 2 ... a1 b a+1 a+2 ... b1 a b+1 ...
The number b has (b1)(a1)=ba smaller numbers on the right,
namely a,...,b1.
The numbers a+1,...,b1 all have just 1 smaller number to the right
(namely a).
All the other numbers have no smaller numbers to the right.
So the total number of wrong pairs is ba+((b1)a)=2b2a1 which is
odd.
So by your definition a transposition is odd.
Now you just need to work the quoted bit above to the effect that if
you compose 2 permutations the number of wrong pairs is (modulo 2)
just the sum of the wrong pairs in the permutations. (It won't
generally be the sum, only the sum modulo 2  and that is the key
thing here, to be able to prove that.) The sum of an odd number of
odd number is odd, but due to the specific way you've defined
odd/even it is something to be proven that composing permutations
actually does behave as hoped.
(In your example, for instance there are 6 smaller numbers to the
right of the 8. If you compose with another permutation, will there
be an even or odd number of smaller numbers to the right of the 8?
I've not investigated, but perhaps this depends on more than whether
the 2nd permutation is odd/even on a number by number basis, though
not for the whole sum.) 0 Attachment
Hi Richard,
I think you misunderstood me somehow. Especially this part makes me
think so:
> (In other words, if you didn't do it
I did *not* define a canonical way for "solving" a permutation, but
> canonically and just switched pairs and eventually came to the
> identity in some nonmethodical way, how would you know that you
> always take an odd (or always take an even) number of
> transpositions.)
rather a way for "looking" at it. I.e. the wrong pairs shall not be
swapped in some particular way (there are many ways for this), they
shall only be counted (there's only one way=result for this).
In other words, define for a permutation p:
federminant(p) := (number of wrong pairs in p) mod 2
What I left as an exercise to Joel is to prove:
1) federminant(identity) = 0
2) federminant(swap(p,i,j)) = (federminant(p) + 1) mod 2
Where swap(p,i,j) is the permutation you get by swapping elements i
and j in permutation p.
Simple induction shows that if you take permutation p, apply k swaps,
and reach permutation q, you have:
federminant(q) = (federminant(p) + k) mod 2
Now assume you take permutation p=identity, apply k swaps (with odd k)
, and reach permutation q=identity. Then you have (everything mod 2):
federminant(identity)
= federminant(q)
= federminant(p) + k
= federminant(identity) + 1
= 0 + 1
= 1
Contradiction!
I don't think there's something missing in my proof (other than the
exercise part of course ;), hopefully my more formal description
above makes clearer what I mean.
What do you say?
Cheers!
Stefan 0 Attachment
 In speedsolvingrubikscube@yahoogroups.com, "Stefan Pochmann"
<pochmann@g...> wrote:>
me
> Hi Richard,
>
> I think you misunderstood me somehow. Especially this part makes
> think so:
but
>
> > (In other words, if you didn't do it
> > canonically and just switched pairs and eventually came to the
> > identity in some nonmethodical way, how would you know that you
> > always take an odd (or always take an even) number of
> > transpositions.)
>
> I did *not* define a canonical way for "solving" a permutation,
> rather a way for "looking" at it. I.e. the wrong pairs shall not
be
> swapped in some particular way (there are many ways for this),
they
> shall only be counted (there's only one way=result for this).
No, what I meant was a canonical way of defining odd vs even (rather
>
than solving the permutation): namely sum over x #{y:y<x and y is to
the right of x} (mod 2).
> In other words, define for a permutation p:
i
> federminant(p) := (number of wrong pairs in p) mod 2
>
> What I left as an exercise to Joel is to prove:
> 1) federminant(identity) = 0
> 2) federminant(swap(p,i,j)) = (federminant(p) + 1) mod 2
> Where swap(p,i,j) is the permutation you get by swapping elements
> and j in permutation p.
2) is what I was referring to  hadn't realized you were leaving
this as an exercise. This is the part I was saying was vital.
Then I agree with you. (The point I was trying to make is that I
thought you were leaving 2) out.)
(All the rest is agreed.)
>
swaps,
> Simple induction shows that if you take permutation p, apply k
> and reach permutation q, you have:
odd k)
> federminant(q) = (federminant(p) + k) mod 2
>
> Now assume you take permutation p=identity, apply k swaps (with
> , and reach permutation q=identity. Then you have (everything mod
2):
>
the
> federminant(identity)
> = federminant(q)
> = federminant(p) + k
> = federminant(identity) + 1
> = 0 + 1
> = 1
>
> Contradiction!
>
> I don't think there's something missing in my proof (other than
> exercise part of course ;), hopefully my more formal description
> above makes clearer what I mean.
>
> What do you say?
>
> Cheers!
> Stefan 0 Attachment
 In speedsolvingrubikscube@yahoogroups.com, GameOfDeath2
<no_reply@y...> wrote:>
Ah, ok... so we did indeed misunderstand each other a bit ;)
> 2) is what I was referring to  hadn't realized you were leaving
> this as an exercise. This is the part I was saying was vital.
> Then I agree with you. (The point I was trying to make is that I
> thought you were leaving 2) out.)
>
> (All the rest is agreed.)
How about this proof of step 2): Call a swap of two adjacent elements
a "bubble". Swapping any two elements A and B in a sequence is the
same as first bubbling A towards B (so they're adjacent), then
bubbling A and B, then bubbling B back to A's original place by
undoing the first part. A bubble clearly changes "evenness" of the
number of wrong pairs. And for a swap, we do (n+1+n) bubbles. So a
swap changes that evenness, too.
Cheers!
Stefan
Your message has been successfully submitted and would be delivered to recipients shortly.