This is a solution to area always half puzzle.
The problem description:
Show that a triangle whose vertices are integers points (both x and y co-ordinates) and which does not have any integer point inside or on the sides (except the vertices) has area exactly half.
These triangles are sometime called primitive triangles.
Solution
As promised, this is the proof from the book, "Proofs from the book".
This requires some Linear Algebra background.
[Perhaps a simpler proof is to just complete the rectangle (draw horizontal and vertical lines through $p_0$ and $p_2$ in the below figure) and count the number of integer points in the triangles, but the point is to show the book proof.]
The proof in the book goes as follows:
If the points are $p_0, p_1, p_2$, then the parallelogram formed by $p_i$ and $p_1 + p_2 - p_0$ does not contain any integer point, because both $\mathbb{Z}^2$ and the parallelogram are symmetric with respect to the reflection $x \to p_1 + p_2 -x$.
Now we can tile the plane by translating this parallelogram (by integer distances) and thus, $p_1 - p_0$ and $p_2 - p_0$ form a basis for $\mathbb{Z}^2$, which implies that the parallelogram has area $1$, and the triangle has area $\dfrac{1}{2}$.
A basis of $\mathbb{Z}^2$ is linearly independent vectors $e_1, e_2$ such that $\mathbb{Z}^2 = \{ae_1 + be_2 | a, b \in \mathbb{Z}\}$.
Area of the parallelogram spanned by $e_1 = (p,q), e_2 = (r,s)$ is given by the absolute value of the determinant of $A(e_1, e_2) = \begin{bmatrix} p & r \\ q & s \end{bmatrix}$
Given any other basis $f_1, f_2$, there is an invertible matrix $Q$ with integer entries such that $A(e_1, e_2) = A(f_1, f_2)\times Q$.
Since $Q$ is invertible and contains integer entries, we must have $|det(Q)| = 1$, and hence $|det (A(f_1, f_2))| = |det(A(e_1, e_2))|$.
Choosing $f_1, f_2 = (1,0), (0,1)$ gives us the result.
There are other elegant proofs, for instance using Minkowski's theorem. See here.
Another way to prove is to prove that the integer coordinates of primitive triangle (with a $(0,0)$ vertex) form consecutive numbers in the Farey sequence.
The stronger theorem I was referring to in the problem blog post is Pick's theorem.
The problem description:
Show that a triangle whose vertices are integers points (both x and y co-ordinates) and which does not have any integer point inside or on the sides (except the vertices) has area exactly half.
These triangles are sometime called primitive triangles.
Solution
As promised, this is the proof from the book, "Proofs from the book".
This requires some Linear Algebra background.
[Perhaps a simpler proof is to just complete the rectangle (draw horizontal and vertical lines through $p_0$ and $p_2$ in the below figure) and count the number of integer points in the triangles, but the point is to show the book proof.]
The proof in the book goes as follows:
If the points are $p_0, p_1, p_2$, then the parallelogram formed by $p_i$ and $p_1 + p_2 - p_0$ does not contain any integer point, because both $\mathbb{Z}^2$ and the parallelogram are symmetric with respect to the reflection $x \to p_1 + p_2 -x$.
Now we can tile the plane by translating this parallelogram (by integer distances) and thus, $p_1 - p_0$ and $p_2 - p_0$ form a basis for $\mathbb{Z}^2$, which implies that the parallelogram has area $1$, and the triangle has area $\dfrac{1}{2}$.
A basis of $\mathbb{Z}^2$ is linearly independent vectors $e_1, e_2$ such that $\mathbb{Z}^2 = \{ae_1 + be_2 | a, b \in \mathbb{Z}\}$.
Area of the parallelogram spanned by $e_1 = (p,q), e_2 = (r,s)$ is given by the absolute value of the determinant of $A(e_1, e_2) = \begin{bmatrix} p & r \\ q & s \end{bmatrix}$
Given any other basis $f_1, f_2$, there is an invertible matrix $Q$ with integer entries such that $A(e_1, e_2) = A(f_1, f_2)\times Q$.
Since $Q$ is invertible and contains integer entries, we must have $|det(Q)| = 1$, and hence $|det (A(f_1, f_2))| = |det(A(e_1, e_2))|$.
Choosing $f_1, f_2 = (1,0), (0,1)$ gives us the result.
There are other elegant proofs, for instance using Minkowski's theorem. See here.
Another way to prove is to prove that the integer coordinates of primitive triangle (with a $(0,0)$ vertex) form consecutive numbers in the Farey sequence.
The stronger theorem I was referring to in the problem blog post is Pick's theorem.
No comments:
Post a Comment