The SlugMath Wiki is under heavy development!
Act/2D hop and skip
|Title||2D hop and skip|
|Purpose||Introduce the reduction algorithm for two by two integer matrices.|
Each student in the class is paired with a partner (or triple). The instructions of the activity are as follows:
- This game is played on a grid, i.e., $\ZZ^2$. You begin at $(0,0)$.
- You are allowed to move along the grid in two ways:
- You can "hop" by moving along the vector $(7,11)$, i.e., moving $7$ units right and $11$ units up. You can also "hop backwards" by moving $7$ units left and $11$ units down.
- You can "skip" by moving along the vector $(5,8)$, i.e., moving $5$ units right and $8$ units up. You can also "skip backwards" by moving $5$ units left and $8$ units down.
- The object of the game is to reach both points $(1,0)$ and $(0,1)$, by hopping and skipping from the origin.
Students are given a few minutes to work on this game, without interruption and without shouting out the answer!
After playing the game for a few minutes, students are invited to discuss how they solved it. In particular, the following items should be discussed:
- Can the game be won?
- How do "compound moves" (call them "jumps" or "leaps", for example) help to solve the game?
- What solutions were found? How many hops and how many skips did it take?
- Is there a unique way to win the game?
Transition to the Reduction algorithm
One may play this game, by reducing the $x$ coordinate first. We begin with the hop and skip:
- $H = (7,11)$ and $S = (5,8)$.
- To reduce the $x$ coordinate, define a jump to be $J = H - S = (2,3)$.
- Now, consider the pair of moves $S = (5,8)$ and $J = (2,3)$.
- Again, one may reduce the $x$ coordinate, by defining a "leap" by $L = S - 2 J = (1,2)$.
- Now, consider the pair of moves $J = (2,3)$ and $L = (1,2)$.
- Define a "bound" by $B = J - L = (1,1)$.
- Define a "step" by $L - B = (0,1)$. This was one of our goals.
- Observe that $(1,1) - (0,1) = (1,0)$; this was another one of our goals.
Suppose that $(a,b)$ and $(c,d)$ is a "pair of moves", i.e., a pair of vectors in $\ZZ^2$. The determinant is defined to be $\Delta = ad - bc$. The crucial properties of the determinant are the following:
- If we switch $(a,b)$ and $(c,d)$, the determinant changes only in sign:
$$cb - ad = - (ad - bc).$$
- If we replace $(a,b)$ by $(a \pm c, b \pm d)$, the determinant does not change:
$$(a \pm c) d - (b \pm d) c = (ad - bc) \pm cd \mp cd = ad - bc.$$
This "reduction via compound moves" may be formalized as follows:
- Begin with two vectors $U = (a,b)$ and $V = (c,d)$ in $\ZZ^2$.
- Assume that $ad - bc = \pm 1$. This implies that $GCD(a,c) = 1$.
- Switching $U$ and $V$ in sign, and with eachother, if necessary, so that $a \geq c \geq 0$.
- If $a = c$, then $a = 1$ and $c = 1$, since $GCD(a,c) = 1$. In this case, go to step 7.
- If $a > c$, replace the pair $U,V$ with the pair $U - V, V$.
- Return to step 3. Observe that the determinant does not change (up to sign) after this replacement.
- If $a = 1$ and $c = 1$, the subtract $U$ from $V$.
- This yields compound moves of the form $(1,b)$ and $(0,d)$. $d = \pm 1$, by the determinant condition.
- Repeatedly subtracting $(0,1)$ from $(1,b)$ yields $(1,0)$.