Consider triangles in the plane where each vertex has integer coordinates. Such a triangle can be legally transformed by moving one vertex parallel to the opposite side to a different point with integer coordinates. Show that if two triangles have the same area, then there exists a series of legal transformations that transforms one to the other.
Problem
Source: Baltic Way 2016, Problem 19
Tags: geometry
06.11.2016 03:56
Represent such a triangle as $M=\binom{v_1}{v_2}$ where $v_1=AB$ and $v_2=AC$ are elements of $\mathbb{Z}^2$. Legal transformations are of the forms $\binom{v_1}{v_2}\rightarrow\binom{v_1+cv_2}{v_2}$, $\binom{v_1}{v_2}\rightarrow\binom{v_1}{v_2+cv_1}$, and $\binom{v_1}{v_2}\rightarrow\binom{v_1+c(v_1-v_2)}{v_2+c(v_1-v_2)}$ for some constant $c$. Essentially, we want to show that the elements of a coset of $SL_2(\mathbb{Z})$ in $GL_2(\mathbb{Z})$ are equivalent under row reduction. We will show that we can always reduce to $\binom{n\quad 0}{0\quad1}$ in the coset with determinant $n$. We proceed by strong induction. This is clearly true for $n=1$ since everything in $SL_2(\mathbb{Z})$ has an inverse. Note that if all entries in any row or column of $M$ is divisible by $d$, then the row reduction of $M$ divided by $d$ in that row or column in $SL_2(\mathbb{Z})$ is equivalent to the row reduction of $M$ in $\binom{\frac{n}{d}\quad 0}{0\quad1}SL_2(\mathbb{Z})$. Hence, it suffices to show that we can reduce $M$ so that its top row (or bottom row, by a similar argument) has all entries divisible by $d$ for some $1<d\mid n$. This is not very difficult; if an entry in $M$ is divisible by $d\mid n$, then either the other entry in its row or column is divisible by $d$ since $\det M=n$. Otherwise, all entries in $M$ are relatively prime to $n$, so if $M=\binom{a\quad b}{c\quad d}$ then we can solve the equation $ax\equiv c\pmod{n}$ and add $x$ times $v_1$ to $v_2$ to obtain the first situation. Hence, any two triangles with the same area can be transformed to each other modulo translations. It remains to show that any two triangles equivalent under translation can be legally transformed to each other. First, legally transform the triangle to a triangle translationally equivalent to $(0,0)-(1,0)-(0,n)$. Then we will translate this triangle by any vector in $\mathbb{Z}^2$ and then take the inverse of the legal transformation from before. This clearly translates the original triangle by the same vector. Note that we can translate the triangle by $(1,0)$ and $(0,1)$ by the following moves, so we can do it for any vector in $\mathbb{Z}^2$, as desired: $(1,0)$: $(0,0)-(1,0)-(0,n)\rightarrow(0,0)-(1,0)-(1,n)\rightarrow(0,0)-(2,n)-(1,n)\rightarrow(1,0)-(2,n)-(1,n)\rightarrow(1,0)-(2,0)-(1,n)$ $(0,1)$: $(0,0)-(1,0)-(0,n)\rightarrow(0,0)-(1,1)-(0,n)\rightarrow(0,0)-(1,1)-(1,n+1)\rightarrow(0,1)-(1,1)-(1,n+1)\rightarrow(0,1)-(1,1)-(0,n+1)$