Loading ...
Sorry, an error occurred while loading the content.

Need some help with a prestentation

Expand Messages
  • joel_vn
    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.
    • mike_go_uk
      ... 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
      • cmhardw
        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
          <no_reply@y...> wrote:
          >
          > --- 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
        • _jaap
          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
          • _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
            • GameOfDeath2
              ... 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.
              • joel_vn
                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.
                • Stefan Pochmann
                  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.
                  • Stefan Pochmann
                    ... 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
                      <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 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
                    • GameOfDeath2
                      ... 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
                        > <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 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.)
                      • Per Kristen Fredlund
                        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.
                        • GameOfDeath2
                          ... 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.)
                          • Stefan Pochmann
                            ... 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,
                              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
                              > 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.)
                            • Stefan Pochmann
                              ... 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
                                <no_reply@y...> wrote:
                                >
                                > 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.

                                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 well-known already, so... you win ;-)
                                But I still say our proofs are equivalent...

                                Cheers!
                                Stefan
                              • d_j_salvia
                                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.
                                • GameOfDeath2
                                  ... 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
                                    > <no_reply@y...> wrote:
                                    > >
                                    > > 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.
                                    >
                                    > 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 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.)
                                  • Stefan Pochmann
                                    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

                                      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
                                    • GameOfDeath2
                                      ... 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
                                        >
                                        > 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
                                      • Stefan Pochmann
                                        ... 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
                                          <no_reply@y...> wrote:
                                          >
                                          > 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 ;-)

                                          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.