Baltic Way 2023 Shortlist

We will prove the following claim: Claim: For $n\in {\mathbb{Z}}^{+}$, the maximal number of bounded regions of the plane generated by $n$ triangles (of whatever size and shape) is $1+3n(n-1)$.

Once the claim is established, we can easily see that the inequality $1+3n(n-1)\ge 2023$ is equivalent to $n\ge 27$, so that we need at least $27$ triangles.

Below, we will establish that $27$ equilateral triangles of side length $1$ are actually enough.

Proof. By induction. The case $n=1$ is trivial.

Suppose that the claim is true for $n$. Let $C=\{T_1,\dots ,T_n\}$ be a configuration consisting of triangles $T_1,\dots ,T_n$. Let us see what happens when a new triangle $T$ is added to the configuration. We enumerate the points of intersection of $T$ with the elements of $C$, starting at some point of $T$, in clockwise direction; let the set of these points be $\mathcal{P}:=\{P_1,\dots ,P_k\}$. Clearly, each region newly arising through the addition of $T$ will have some part of its border in common with $T$; since the regions are not supposed to be further subdivided, the part of the border of a new region will be the section between two successive elements of $\mathcal{P}$, where we also count $P_1$ as a successor of $P_k$. Each such line segment can at best generate one new region by either cutting an already bounded into two parts or by splitting off some bounded part of the unbounded region around $C$. It follows that the number of newly generated regions is at most $k$. Now, two triangles can have at most $6$ points of intersection, and $C$ consists of $n$ triangles, so that $k\le 6n$. Consequently, the addition of $T$ can yield at most $6n$ new regions. By assumption, the number of regions prior to the addition of $T$ was at most $1+3n(n-1)$. Thus, after adding $T$, the number of regions is at most $1+3n(n-1)+6n=1+3n(n+1)$.

(To see that two triangles can intersect in at most $6$ points, note that a triangle, being convex, can be intersected by a line in at most $2$ points, and each triangle consists of three line segments.) $\square$

Proof that $27$ triangles suffice. We prove by induction the more general claim that the upper bound $1+3n(n-1)$ for the number of bounded regions generated by $n$ triangles can actually be attained. Again, for the case $n=1$, this is trivial.

We now assume inductively that we have produced a configuration $C=\{T_1,\dots ,T_n\}$ of $n$ triangles such that: 1. All elements of $C$ have the same orthocenter. 2. Each two distinct elements of $C$ intersect in six points. 3. No point lies on three elements of $C$. 4. The number of bounded regions is $1+3n(n-1)$.

We will show that $C$ can be extended to a configuration with one extra triangle $T$ such that (1)-(3) still hold for the new configuration and such that the number of bounded regions is increased by $6n$.

To this end, consider rotations of $T_1$ around its orthocenter. There are only finitely many angles for which the respective rotation will pass through one of the finitely many points of intersection in $C$ (or such that the result will be identical to an element of $C$); thus (because there are infinitely many angles of rotation), there is an angle $\alpha$ such that the result $T$ of the rotation of $T_1$ around the orthocenter by $\alpha$ will not pass through any prior point of intersection. Thus (1) and (3) are satisfied for $C\cup \{T\}$. It is easy to see that, rotating an equilateral triangle around its orthocenter will either yield an identical triangle or exactly six points of intersection; the first case is excluded by construction, thus (2) is satisfied as well.

Thus, $T$ has $6n$ points of intersection with the elements of $C$, let these be $P_1,\dots ,P_{6n}$. We need to show each polygonal line $P_i{P}_{i+1}$ (which is either a line segment or comprised of two line segments meeting at a vertex of $T$) generates a new bounded region; let us enumerate these segments as $s_1,\dots ,s_{6n}$. To see this, note that, for each such segment $s_k=P_k{P}_{k+1}$ (with $s_{6n}=P_{6n}{P}_1$), one of the following cases holds: 1. $s_k$ runs through a region already bounded by $C$ and $s_1,\dots ,s_{k-1}$, splitting into two parts. 2. $s_k$ runs through the unbounded region of $C$, splitting off a bounded part of it. 3. $s_k$ runs through the unbounded region of $C$ without splitting off a bounded part of it.

In the cases (1) and (2), a new region is generated, while in case (3), this is not the case. But note that case (3) cannot occur: For if $P_k$ belongs to $T_i$ and $P_{k+1}$ belongs to $T_j$ then, by the case assumption, we have $i\ne j$ and, by assumption (2) about $C$, $T_i$ and $T_j$ intersect, so that $s_k$ must generate a new bounded region.

It follows that $6n$ new bounded regions are added, so that we now have $1+3n(n-1)=1+3(n+1)n$ regions, which finishes the induction. $\square$