| | |
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:
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.
|
|
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).
Construct a "multiplication table" for the symmetries of a rectangle.
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 |
Construct a multiplication table for the numbers $1, -1, i, -i$.
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$ |
Construct a "multiplication table" for only the rotational symmetries of a pentagon.
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}$ |
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$.
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 division 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 |
| $\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 |
Compare the tables you have created for problems #3-6.
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$):