There are $N$ acute triangles on the plane. Their vertices are all integer points, their areas are all equal to $2^{2020}$, but no two of them are congruent. Find the maximum possible value of $N$. Note: $(x,y)$ is an integer point if and only if $x$ and $y$ are both integers. Proposed by CSJL
Problem
Source: 2020 Taiwan TST Round 2 Mock exam P3
Tags: combinatorics, Taiwan, Hi
13.05.2020 10:19
This problem is proposed by me. Bump, bump!
28.05.2020 01:16
Call a triangle a lattice triangle if its vertices are at lattice points. We claim that there are $2^n - 1$ distinct (up to congruence) lattice triangles with area $2^n$, which would imply that the answer to our problem is $\boxed{2^{2020} - 1}.$ We will show this by induction on $n.$ Before doing so, we will need a few lemmas. Lemma 1. Consider a lattice triangle $\triangle ABC$ such that the midpoint of $BC$ is $M_a$, that of $CA$ is $M_b$, and that of $AB$ is $M_a.$ At least one of $M_a, M_b, M_c$ is a lattice point. Proof. Suppose the contrary, for contradiction. By some simple parity checking, we can assume WLOG that $\overrightarrow{AB} = (2 x_b + 1, 2 y_b)$ and $\overrightarrow{AC} = (2x_c +1 , 2y_c)$ for some integers $x_b, x_c, y_b ,y_c.$ But then it's easily verified that $|AB \times AC|$ is odd and therefore $\triangle ABC$ has non-integral area, contradiction. So our assumption was wrong and the lemma holds. $\blacksquare$ It's also clear from Lemma $1$ that the medial triangle of any acute lattice triangle with area a power of two has either one or three vertices at lattice points. Call triangles of the former kind tangy and those of the latter kind wangy . Lemma 2. There are precisely $n$ acute isosceles lattice triangles with area $2^n$, for all nonnegative $n$. Proof. Omitted. $\blacksquare$ Now, we will attack the problem. Let $S_n$ denote the set of acute scalene lattice triangles of area $2^n$ and let $f(n) = |S_n|$, for all nonnegative integers $n$ We claim that $f(n) = 2^n - n - 1$ for all $n \in \mathbb{Z}_{\ge 0}$, which yields the desired result when combined with Lemma $2.$ It's easy to check that this holds for $n = 0, 1$ by hand. To show that $f(n) = 2^n - n - 1$, it would suffice by induction to show that $f(n) = 3 \cdot f(n-1) - 2 \cdot f(n-2) + 1$ for $n \ge 2$, which is precisely what we shall show. Observe that there is a bijection between wangy triangles in $S_n$ and triangles in $S_{n-2}$ by simply considering the medial triangles of wangy triangles in $S_n$. For a triangle, we define an augmentation of it to be the triangle formed when we take two of its vertices $P$ and $Q$, and move $Q$ to the point $Q'$ satisfying $\overrightarrow{PQ'} = 2 \overrightarrow{PQ}.$ In this way, a triangle has up to six different augmentations. Observe that any triangle in $S_{n-1}$ has precisely $3$ augmentations which are acute. Furthermore, it's easy to check that any isosceles lattice triangle with area $2^{n-1}$ has precisely one augmentation. Furthermore, any tangy triangle in $S_n$ is the augmentation of precisely one acute lattice triangle of area $2^{n-1}$, while the wangy triangles in $S_n$ are the augmentations of three acute lattice triangles of area $2^{n-1}.$ It's easy to check that precisely $n-2$ augmentations of acute lattice triangles with area $2^{n-1}$ are isosceles acute lattice triangles. Hence, if we let $x$ denote the number of augmentations of acute lattice triangles in $S_{n-1}$ (with multiplicity) and $y$ be the number of wangy triangles in $S_n$, we can use the previous results to arrive at: $$f(n) + n-2 = x - 2y. \qquad (1)$$ From previous results, it's also easy to see that $x = 3 \cdot f(n-1) + n-1$. Now, we can observe that the triangles in $S_{n-2}$ are simply the medial triangles of the wangy triangles of $S_n$, implying that $y = f(n-2).$ Hence, $(1)$ can now be rewritten as: $$f(n) + n-2 = 3f(n-1) + n-1 - 2f(n-2) \Leftrightarrow f(n) = 3f(n-1) -2f(n-2) + 1,$$ as desired. $\square$