Solution to area exactly half, geomety puzzle

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.

Area always half, geometry puzzle.

A cute fact about triangles with integer co-ordinates:

Lemma: Suppose $A, B, C$ are points in the 2D plane each with integer co-ordinates, such that no point with integer co-ordinates lies inside, or on the sides (except $A, B, C$) of triangle $ABC$. Then, the area of triangle $ABC$ is exactly $\dfrac{1}{2}$ 

[A point with integer co-ordinates is a point whose x and y co-ordinates are both integers].

For example, $A = (0,0)$, $B = (1,1)$, $C = (2,1)$. The "base" $BC$ and height $AD$ (where $D = (0,1)$) are both of length $1$ and so the area of $\triangle{ABC}$ is exactly $\dfrac{1}{2}$

Can you prove the Lemma?

[Note, using a stronger theorem about lattice points and areas would be circular (unless you prove the stronger theorem without using this Lemma).]

[A neat proof of this appears in Proofs from the Book: Solution]

Solution to monochromatic equilateral triangle puzzle

This is a solution to the math puzzle posted earlier.

We will post a solution to the variant (which also solves the main puzzle).

The problem:

Each point of 2D plane is coloured either black or white. Given three positive angles $\alpha + \beta + \gamma = 180^{\circ}$, show that there are there points $A,B,C$ of the same colour such that the triangle formed by those three has the angles $\alpha, \beta, \gamma$.

Solution

---

The solution is quite similar to the one posted in the comments by 226.

First we show that there are three collinear points $X,Y,Z$ which are coloured the same, and $Y$ is the midpoint of $X$ and $Z$.

Assume that is not true.

Consider two points which are coloured the same (say black, wlog). Say they are $(0,0)$ and $(2a, 0)$.

Now $(a,0)$, $(-2a, 0)$ and $(4a, 0)$ must be coloured white. These three points satisfy the requirement.

Say $X,Y,Z$ are coloured black.

Let $\gamma = \max \{\alpha, \beta, \gamma\}$

Let $P,Q$ be such that $\angle{YXP} = \angle{ZYQ} = \alpha$ and $\angle{XYP} = \angle{YZQ} = \beta$. Both $\triangle{XYP}$ and $\triangle{YZQ}$ have the angles $\alpha, \beta, \gamma$.

Ths $P$ and $Q$ must both be coloured white.

Now consider point $R$ such that $\angle{QPR} = \angle{ZXR} = \alpha$ and $\angle {PQR} = \angle{XZR} = \beta$

Triangle $PQR$ also has the given angles, and so $R$ must be black. But $\triangle{XZR}$ also has the given angles, and all vertices are black.

Basically, $XZR$ is an $\alpha, \beta, \gamma$ triangle, and $P,Q,Y$ are the midpoints of the sides of $\triangle{XZR}$.

Monochromatic Equilateral Triangle, IMO problem

This problem appeared in the International Math Olympiad (IMO) in the 1970/80s.

Each point of the 2D plane, is coloured either black or white. Show that there are three points $A,B,C$ which are of the same colour, and form the vertices of an equilateral triangle.

In other words, there is a monochromatic equilateral triangle, no matter how you colour each point of the plane, with one of two colours.

A variant:

Given three positive angles $\alpha + \beta + \gamma = 180^{\circ}$, show that there is a monochromatic triangle with those angles.

[Solution]

Solution to only the twain shall meet geometry puzzle

This is a solution to the geometry puzzle about lines posted earlier.

A brief description of the problem:

Given a set $S$ of finite number lines in the 2D plane, no two parallel, and not all concurrent, show that there is a point through which only two lines of $S$ pass (hence the title).

Solution

---

Since no two lines are parallel, and not all are concurrent, there is at least one triple of lines which forms a non-degenerate triangle.

Of all such triplets, consider the lines which form a triangle of the least area. The claim is that one of the vertices of this triangle satisfies the requirement!

[Sorry, no figures yet, so it might help to draw it out]

Suppose not, then if the triangle was $\triangle ABC$, then there are lines passing through $A,B,C$ such that they form a bigger triangle, $\triangle DEF$, with each of $A,B,C$ lying on different sides of $\triangle DEF$ and $\triangle ABC$, say $A$ is on side $DE$ (between $D$ and $E$), B is on side $DF$ (between $D$ and $F$) and $C$ is on side $EF$ (between $E$ and $F$).

We consider two cases:

1) $A$ is closer to $D$ than $E$ (possibly equidistant from both points). $B$ is closer to $D$ than $F$. Then we must have that the area of $\triangle ABC$ lies between areas of $\triangle ABE$ and $\triangle ABF$, say area of $\triangle ABE$ is smaller. This we can see, by drawing lines parallel to $AB$ through $E$ and through $F$, and considering the altitude lengths.

Since $A$ is closer to $D$ than $E$, we must have that area of $\triangle DAB \lt$ area of $\triangle ABE$, and thus contradicting the fact that $\triangle ABC$ has the least area.

2) $A$ is closer to $D$ than $E$ (possibly equidistant) and $B$ is closer to $F$ than $D$, and $C$ is closer to $E$ than $F$.

In this case, we can move $C$ to the midpoint of $EF$ and $B$ to the midpoint of $DF$ and decrease the area of $\triangle ABC$. This we can see by drawing lines parallel to $AB$ through $C$ and the midpoint $M$ of $EF$, and lines parallel to $MA$ through $B$ and $M'$, the midpoint of $DF$ (and considering the altitude lengths).

The resulting area is exactly one-fourth the area of $\triangle{DEF}$, and hence area of $\triangle ABC$ is more than the average of the sum of triangles $ABC, DAB, EBC, FAB$ and thus there must be a triangle of lesser area.

The above two cases cover all the possibilities, so we are done.

Futher reading

---

The classic problem I was referring to is the Sylvester-Gallai problem, which is the dual of this problem, by considering the polar/pole version.

A different proof of the claim that $\triangle ABC$ is not the least can also be found here (Theorem 3.1.2 on pages 20-22).

More information about the Sylvester-Gallai theorem, including some nice history can be found here and here.

Only the twain shall meet, geometry puzzle.

This is a classic problem, in disguise. That problem was open for 20+ years, so if you solve this problem without using the classic result, pat yourself on the back!

You are given a finite set of lines, $S$ in the 2D plane, no two lines of which are parallel and not all are concurrent.

Show that there are two lines (call them $p$ and $q$) such that no other line in $S$ passes through the intersection point of $p$ and $q$.

i.e. among all the points of intersections formed by the lines in $S$, there is a point through which only two lines of $S$ meet.

[Solution]

Solution to separating circle puzzle

[This is a solution to the Separating Circle, geometry puzzle posted earlier]

The problem:

Given $2n+3$ points in the general position (no three collinear, no four concyclic) in the 2D plane, show that there are three points among those, such that the circle through those points has exactly $n$ of the remaining $2n$ points inside the circle (and exactly $n$ outside).

Solution

---

We use the following property of circles:

If $AB$ is a chord of a circle, and $P$ and $Q$ are any two points on the major (or minor) arc of a circle, then $\angle{APB} = \angle{AQB}$, i.e. the arc of the circle is the locus of points $X$ such that the angle subtended by $AB$ at $X$ is constant.

We won't use this other fact, but just mentioning it for clarity: if $R$ is a point on the opposite arc as $P$ and $Q$ then $\angle{ARB} = 180^{\circ} - \angle{APB}$.

We won't prove these facts here, as they are easily available in textbooks/online.

Now, we can show that, if $S$ is a point inside the circle, on the same side of $A,B$ as $P$ and $Q$, then $\angle{ASB} \gt \angle{APB}$.

Proof: Line through $A$ and $S$ cuts the circle at S'. If $S$ is inside, then $\angle{ASB} = \angle{AS'B} + \angle{SBS'} = \angle{APB} + \angle{SBS'}$

Similarly, if $S$ is outside, on the same side of $AB$ as $P$ and $Q$, then $\angle{ASB} \lt \angle{APB}$.

So, if we have a circle through $A,B,C$ which separates the points, and say all the points lie to the same side of $A,B$, then the angles of the other points will be such that exactly $n$ are smaller than $\angle{ACB}$ and exactly $n$ are bigger.

This gives us a constructive proof:

Take the convex hull of all the points. Since they are not all collinear, the convex hull will have at least three sides. Pick one side, say $AB$. Now all the other points lie on the same side as $AB$.

Now, for each of the remaining $2n+1$ points, $P_i$, compute the angle $\angle{AP_{i}B}$. Since no four are concyclic, all these angles will be distinct, and we can sort them in ascending order, say: $\angle{AP_1B} \lt \angle{AP_2B} \lt \dots \lt \angle{AP_nB} \lt \angle{AP_{n+1}B} \lt \dots \lt \angle{AP_{2n+1}B}$.

Pick $C = P_{n+1}$.

The circle through $A,B,C$ will have $P_1, P_2, \dots, P_n$ outside, and $P_{n+2}, \dots, P_{2n+1}$ inside.

This generalizes to any combination of $n\pm k$ and $ n \mp k$ inside/outside.

Separating circle geometry puzzle

[This puzzle was given to me by Arvind Hariharan a long time back]

The puzzle is easy to state:

Given $2n+3$ points in the general position (no three collinear, no four concyclic) in the 2D plane, show that there are three points among those, such that the circle through those points has exactly $n$ of the remaining $2n$ points inside the circle (and exactly $n$ outside).

[Solution]

Solution to the two triangles puzzle.

[This is a solution to the two triangles geometry puzzle posted earlier]

The problem, repeated here:

In the figure below (not to scale, forgive the shoddy drawing skills).




$ABC$ is a triangle such that $\angle{BAC} = 60$ and $\angle{ABC} = 25$.

$DEF$ is an isosceles triangle, such that $\angle{EDF} = \angle{EFD}$, and $\angle{DEF} = 10$

(all angles are in degrees).

We also have that $|BC| = |DE|$ ($|XY|$ = length of the segment $XY$)

Show that $2|AC| + |DF| = |AB|$

Solution

---

Notice that $\angle{FDE} = 85$ and $\angle{ACB} = 95$, and so their sum is $180$.

Since $|BC| = |ED|$, we can position one copy of $\triangle{ABC}$ with $B$ coinciding with $E$ and $C$ coinciding with $D$ to get a bigger triangle.

Another copy of $\triangle{ABC}$, call it $\triangle{A'B'C'}$, can be positioned so that $B'$ coincides with $E$ and $C'$ coincides with $F$.

The result will be an even bigger triangle, $\triangle{EAA'}$ as below (more drawing incompetence):

Placing two copies of ABC along with DEF results in an equilateral triangle.

$\triangle{EAA'}$ is an equilateral triangle, and thus the base of the triangle which is $2|AC| + |DF|$ is same as the other side which is $|AB|$.

A property of two triangles, geometry puzzle

[This is a geometry puzzle, solvable by elementary 8th grade geometry, i.e. no trigonometry etc]

In the figure below (not to scale, forgive the shoddy drawing skills).




$ABC$ is a triangle such that $\angle{BAC} = 60$ and $\angle{ABC} = 25$.

$DEF$ is an isosceles triangle, such that $\angle{EDF} = \angle{EFD}$, and $\angle{DEF} = 10$

(all angles are in degrees).

We also have that $|BC| = |DE|$ ($|XY|$ = length of the segment $XY$)

Show that $2|AC| + |DF| = |AB|$

[Solution]