## Exercises - Permutation Puzzles

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.

Suppose we number the cards 1 through 16, where the 1 is on the bottom of the deck. Shuffling the cards once in the described way changes the order as shown below: $$\begin{array}{cccccccccccccccc}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ 16 & 8 & 7 & 15 & 14 & 6 & 5 & 4 & 13 & 12 & 11 & 3 & 2 & 10 & 9 & 1\end{array}$$ Now we can find the cycles: \begin{align} &(1,16),\\ &(2, 8, 4, 15, 9, 13),\\ &(3, 7, 5, 14, 10, 12),\\ &(6) \textrm{ and } (11)\end{align} Note, the cycle lengths are 2, 6, 6, 1, and 1 respectively. So the deck will return to its original order in 6 shuffles (the least common multiple of the cycle lengths seen: 2, 6, and 1).

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

Comparing the new sticker locations with the old, we find: $$\begin{array}{cccccccccccccccc}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 \end{array}$$ Now we can find the cycles: \begin{align} &(1, 6, 7), (2, 11, 8), (9,16), (3), (4), (5),\\ &(10), (12), (13), (14), \textrm{ and } (15)\end{align} Note, the first three cycle lengths are 3, 3, and 2, respectively, while the rest are 1. So the stickers will return to their original positions collectively after 6 similar rearrangements (the least common multiple of the cycle lengths seen: 3, 2, and 1).

3. Your answer may differ from what follows depending on: how you labeled your transformations, in what order you placed your transformations, which transformation you applied first, and so on... Amazingly however, the overall structure of your answer won't change even if you made different choices than were made below.

Consider the possible ways to reposition a rectangle, subject to the restraint that we must end up in the same area our rectangle once occupied:

 Identity, I Rotate 180°, R Vert. Axis Flip, V Horiz. Axis Flip, H

Notice, we fail to have a rotation of 90 degrees, as such a rotation would make the rectangle fall outside of its original area occupied.

With a little help from an index card whose corners are labeled: A, B, C, and D; we can find the net effect of applying any two of these transformations together. (Assume the column below indicates the first transformation applied.)

I R V H
I I R V H
R R I H V
V V H I R
H H V R I

4. Recalling that $i^2=-1$, this is quickly done:

. $1$ $i$ $-i$ $-1$
$1$ $1$ $i$ $-i$ $-1$
$i$ $i$ $-1$ $1$ $-i$
$-i$ $-i$ $1$ $-1$ $i$
$-1$ $-1$ $-i$ $i$ $1$

5. The transformations we use must be limited to rotations where our pentagon ultimately ends up in the same area it originally occupied after the rotation.

Given that a pentagon has 5 sides, the smallest such rotation (besides rotating by $0^{\circ}$) is a rotation of $360^{\circ} / 5=72^{\circ}$. One could rotate the pentagon by any multiple of $72^{\circ}$ and occupy its original area, but notice $5 \cdot 72^{\circ} = 360^{\circ}$ is equivalent to no rotation at all.

As such, we really only have 5 distinct transformations: rotating by $0^{\circ}$ (doing nothing), $72^{\circ}$, $144^{\circ}$, $216^{\circ}$, or $288^{\circ}$. Calling these rotations $R_{0}, R_{72}, R_{144}, R_{216}$, and $R_{288},$ we can flesh out the table for their combinations:

$R_{0}$ $R_{72}$ $R_{144}$ $R_{216}$ $R_{288}$
$R_{0}$ $R_{0}$ $R_{72}$ $R_{144}$ $R_{216}$ $R_{288}$
$R_{72}$ $R_{72}$ $R_{144}$ $R_{216}$ $R_{288}$ $R_{0}$
$R_{144}$ $R_{144}$ $R_{216}$ $R_{288}$ $R_{0}$ $R_{72}$
$R_{216}$ $R_{216}$ $R_{288}$ $R_{0}$ $R_{72}$ $R_{144}$
$R_{288}$ $R_{288}$ $R_{0}$ $R_{72}$ $R_{144}$ $R_{216}$

6. In both cases, we simply do the normal operation (addition or multiplication) and then find the remainder upon division by 5 of the result. This remainder is our answer. So for example:

$$4 \cdot 3 = 12$$ and 12 has remainder 2 upon divison by 5, so... $$4 \cdot 3 \equiv 2 \pmod{5}$$ Likewise, if we look at addition... $$4 + 2 = 6$$ and 6 has remainder 1 upon division by 5, so... $$4 + 2 \equiv 1 \pmod{5}$$ Using the same technique, the addition and multiplication tables asked for are found very quickly.

The addition table$\pmod{5}$ is given by

$+$ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
The multiplication table$\pmod{5}$ is given by:
$\cdot$ 1 2 3 4
1 1 2 3 4
2 2 4 1 3
3 3 1 4 2
4 4 3 2 1

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}$