The SlugMath Wiki is under heavy development!

# Act/2D hop and skip

(diff) ←Older revision | Current revision (diff) | Newer revision→ (diff)
 Title 2D hop and skip 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!

## Discussion

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.

## The determinant

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:

1. Begin with two vectors $U = (a,b)$ and $V = (c,d)$ in $\ZZ^2$.
2. Assume that $ad - bc = \pm 1$. This implies that $GCD(a,c) = 1$.
3. Switching $U$ and $V$ in sign, and with eachother, if necessary, so that $a \geq c \geq 0$.
4. If $a = c$, then $a = 1$ and $c = 1$, since $GCD(a,c) = 1$. In this case, go to step 7.
5. If $a > c$, replace the pair $U,V$ with the pair $U - V, V$.
6. Return to step 3. Observe that the determinant does not change (up to sign) after this replacement.
7. If $a = 1$ and $c = 1$, the subtract $U$ from $V$.
8. This yields compound moves of the form $(1,b)$ and $(0,d)$. $d = \pm 1$, by the determinant condition.
9. Repeatedly subtracting $(0,1)$ from $(1,b)$ yields $(1,0)$.