Exercises - Permutation Puzzles and the GCD

  1. How many shuffles are required to return a deck of 16 cards to their original positions if the deck is "shuffled" in the following way:  

    1. Place the deck face down on the table
    2. Split the deck into two piles, the top half and the bottom half. Place the top half to the right side of the table and the bottom half on the left side of the table.
    3. Merge the two piles together, by pulling the top card from either the right or left pile (as dictated by the order: R,L,L,R,R,L,L,L,R,R,R,L,L,R,R,L) and placing it in the center of the table.
  2. Suppose someone rearranges the numbered stickers in the first grid so that the result looks like the second grid. Find out how many such rearrangements are necessary to return the stickers to their original locations.  

    1 2 3 4
    5 6 7 8
    9 10 11 12
    13 14 15 16
    6 11 3 4
    5 7 1 2
    16 10 8 12
    13 14 15 9

  3. Construct a "multiplication table" for the symmetries of a rectangle.  

  4. Construct a multiplication table for the numbers $1, -1, i, -i$.  

  5. Construct a "multiplication table" for only the rotational symmetries of a pentagon.  

  6. Define "addition modulo 5" and "multiplication modulo 5" in the following way: Define $a + b \pmod{5}$ to mean the remainder upon division by 5 of $a+b$, and define $ab \pmod{5}$ to be the remainder upon division by 5 of $ab$. Construct an addition table for numbers $0,1,2,3,4$ and a multiplication table for numbers $1,2,3,4$.  

  7. Compare the tables you have created for problems #3-6.

    • Are there any that seem to be related?
    • Do they all describe a "closed" operation?
    • Does commutativity hold in each? (i.e., $ab=ba$ or $a+b = b+a$)
    • Does associativity hold in each? (i.e., $(ab)c=a(bc)$ or $(a+b)+c=a+(b+c)$)
    • Is there an identity in each? (i.e., something when combined with any other element leaves it unchanged?)
    • Does cancellation hold in each? (i.e., "if $ac=bc$ then $a=b$", or "if $a+c=b+c$ then $a=b$")
  8. Recall that two numbers share the same remainder upon division by $n$ if and only if their difference is a multiple of $n$. With this in mind, define $a \equiv b \pmod{n}$ to mean $n \mid b-a$ and prove the following are true for all integers $x$, $y$ $z$, and $n$ (with $n > 0$):

    1. $xy \equiv yx \pmod{n}$
    2. $x(yz) \equiv (xy)z \pmod{n}$
    3. $x(y+z) \equiv xy+xz \pmod{n}$

◆ ◆ ◆