## Need some help with a prestentation

Expand Messages
• 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 =
Message 1 of 19 , Nov 1, 2004
• 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 non-cuber
(and it's not really beautiful), so does anyone know a (short) way
to prove it so a non-cuber 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 tax-laws 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(?) light-years. Does anyone know more interesting
facts like this?

Thanks for helping me :),

Joel.
• ... Hi Joel I don t know a really nice way to do it, so will be interested to see what others come up with. Three-cycles are one possibility... but to avoid
Message 2 of 19 , Nov 1, 2004
• 0 Attachment
--- 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 prove
> 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 non-cuber can understand it quickly?)

Hi Joel

I don't know a really nice way to do it, so will be interested to see
what others come up with. Three-cycles are one possibility... but to
avoid having to treat edges-odd/corners-odd (slightly) separately
from edges-even/corners-even you might want to use the T-pattern
(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
• 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
Message 3 of 19 , Nov 1, 2004
• 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 4-cycle the corners and edges in their orbits,
then break down a 4-cycle 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
>
> --- 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
prove
> > 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 non-cuber can understand it quickly?)
>
> Hi Joel
>
> I don't know a really nice way to do it, so will be interested to
see
> what others come up with. Three-cycles are one possibility... but
to
> avoid having to treat edges-odd/corners-odd (slightly) separately
> from edges-even/corners-even you might want to use the T-pattern
> (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
• Hi Joel, ... I don t think there is a way to do it other than to explicitly establish an algorithm for solving any position, though it obviously need not be at
Message 4 of 19 , Nov 2, 2004
• 0 Attachment
Hi Joel,

> --- joel_vn wrote:
> > 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 non-cuber
> > (and it's not really beautiful), so does anyone know a (short)
> > way to prove it so a non-cuber can understand it quickly?)

I don't think there is a way to do it other than to explicitly
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 T-pattern
> (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.

This is one of those facts which seems much deeper than it really is.
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 non-UL
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 non-UL
piece, without disturbing any other solved non-UL 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 non-UL
edges with UL using the T permutation.

> 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.

The way I did it you only need to bring one edge to UR without
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
• ... Sure, but to show that _all_ even permutations are possible, you have to be able to do _any_ transposition, not just a particular transposition. If it were
Message 5 of 19 , Nov 2, 2004
• 0 Attachment
--- cmhardw wrote:
> 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.

Sure, but to show that _all_ even permutations are possible, you have
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 4-cycle. Any conjugate of
R is also a 4-cycle of corners. But it is not possible to do any
corner 4-cycle, simply because the movements are too restrictive that
you cannot find a way to bring any four corners to the R face.

Jaap
• ... calculate ... it s ... to ... prove ... Hungary ... * ... What level are you pitching it at? (Depending on this, you may have to define a lot of
Message 6 of 19 , Nov 2, 2004
• 0 Attachment
--- 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 non-cuber
> (and it's not really beautiful), so does anyone know a (short) way
> to prove it so a non-cuber 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 tax-laws 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(?) light-years. Does anyone know more interesting
> facts like this?
>
> Thanks for helping me :),
>
> Joel.

What level are you pitching it at? (Depending on this, you may have
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 (2-cycles). 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 4-cycles (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 4-cycles 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 3-cycles:
(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 3-cycle and a corner 3-cycle.
Exhibiting these last facts should be easy, so the only thing you
need to worry about is the 3-transitivity (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 3-cycles 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 3-transitivity) 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.
• 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
Message 7 of 19 , Nov 2, 2004
• 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:
>
> 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 non-cuber
> (and it's not really beautiful), so does anyone know a (short) way
> to prove it so a non-cuber 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 tax-laws 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(?) light-years. Does anyone know more interesting
> facts like this?
>
> Thanks for helping me :),
>
> Joel.
• I once came up with a visualization I like better (because I can t really imagine a light-year, it s so abstract). Imagine all of human kind has done nothing
Message 8 of 19 , Nov 2, 2004
• 0 Attachment
I once came up with a "visualization" I like better (because I can't
really imagine a light-year, 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
well-organized 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(?) light-years. Does anyone know more interesting
> facts like this?
>
> Thanks for helping me :),
>
> Joel.
• ... 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
Message 9 of 19 , Nov 2, 2004
• 0 Attachment
--- In speedsolvingrubikscube@yahoogroups.com, GameOfDeath2
> 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 1-8. 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
1-5 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
• ... Yes, but there s the issue of showing that it s not possible (in some other, possibly non-canonical, way) to solve using a different number (modulo 2) of
Message 10 of 19 , Nov 3, 2004
• 0 Attachment
--- In speedsolvingrubikscube@yahoogroups.com, "Stefan Pochmann"
<pochmann@g...> wrote:
>
> --- In speedsolvingrubikscube@yahoogroups.com, GameOfDeath2
> > 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 1-8. 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
> 1-5 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

Yes, but there's the issue of showing that it's not possible (in some
other, possibly non-canonical, 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.)
• 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
Message 11 of 19 , Nov 3, 2004
• 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:
>
> 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 non-cuber
> (and it's not really beautiful), so does anyone know a (short) way
> to prove it so a non-cuber 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 tax-laws 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(?) light-years. Does anyone know more interesting
> facts like this?
>
> Thanks for helping me :),
>
> Joel.
• ... I presume, he mentioned that near the start where he mentioned it was impossible to do an odd permutation. (At least one assumes that is what he meant - of
Message 12 of 19 , Nov 3, 2004
• 0 Attachment
--- 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.

I presume, he mentioned that near the start where he mentioned it was
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.)
• ... some ... number ... that ... able ... a ... That s easy, isn t it? Assume that a certain permutation can be solved one way with 12 swaps and another way
Message 13 of 19 , Nov 3, 2004
• 0 Attachment
> Yes, but there's the issue of showing that it's not possible (in
some
> other, possibly non-canonical, 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.

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,

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
> 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
> 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.)
• ... permutation ... the ... contradiction ... Ok, I read your exact reasoning again. I think we re actually saying pretty much the same thing, the difference
Message 14 of 19 , Nov 3, 2004
• 0 Attachment
--- In speedsolvingrubikscube@yahoogroups.com, GameOfDeath2
>
> 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

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
of "raw order". Well, I'd need to define mine more precisely, yours
are two simple words that are well-known already, so... you win ;-)
But I still say our proofs are equivalent...

Cheers!
Stefan
• 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
Message 15 of 19 , Nov 3, 2004
• 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 non-cuber
> > (and it's not really beautiful), so does anyone know a (short) way
> > to prove it so a non-cuber 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 tax-laws 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(?) light-years. Does anyone know more interesting
> > facts like this?
> >
> > Thanks for helping me :),
> >
> > Joel.
• ... matrix ... transposition ... it ... matrix ... saying ... talking ... pairs ... yours ... ) ... Actually, my main point is that you need to show that
Message 16 of 19 , Nov 4, 2004
• 0 Attachment
--- In speedsolvingrubikscube@yahoogroups.com, "Stefan Pochmann"
<pochmann@g...> wrote:
>
> --- In speedsolvingrubikscube@yahoogroups.com, GameOfDeath2
> >
> > 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
> > 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
pairs"
> of "raw order". Well, I'd need to define mine more precisely,
yours
> are two simple words that are well-known already, so... you win ;-
)
> But I still say our proofs are equivalent...
>
> Cheers!
> Stefan

Actually, my main point is that you need to show that
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 well-defined 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 non-methodical 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 ... a-1 b a+1 a+2 ... b-1 a b+1 ...
The number b has (b-1)-(a-1)=b-a smaller numbers on the right,
namely a,...,b-1.
The numbers a+1,...,b-1 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 b-a+((b-1)-a)=2b-2a-1 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.)
• Hi Richard, I think you misunderstood me somehow. Especially this part makes me ... I did *not* define a canonical way for solving a permutation, but rather
Message 17 of 19 , Nov 4, 2004
• 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
> canonically and just switched pairs and eventually came to the
> identity in some non-methodical 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, but
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

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
• ... me ... but ... be ... they ... No, what I meant was a canonical way of defining odd vs even (rather than solving the permutation): namely sum over x
Message 18 of 19 , Nov 5, 2004
• 0 Attachment
--- In speedsolvingrubikscube@yahoogroups.com, "Stefan Pochmann"
<pochmann@g...> wrote:
>
> Hi Richard,
>
> I think you misunderstood me somehow. Especially this part makes
me
> think so:
>
> > (In other words, if you didn't do it
> > canonically and just switched pairs and eventually came to the
> > identity in some non-methodical 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,
but
> 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:
> 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.

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.)

>
> 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
>
>
> 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
• ... Ah, ok... so we did indeed misunderstand each other a bit ;-) How about this proof of step 2): Call a swap of two adjacent elements a bubble . Swapping
Message 19 of 19 , Nov 5, 2004
• 0 Attachment
--- In speedsolvingrubikscube@yahoogroups.com, GameOfDeath2
>
> 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.)

Ah, ok... so we did indeed misunderstand each other a bit ;-)