IMO 2006 Shortlisted Problems

Let $T$ be a holey triangle. The unit triangles in it will be called cells. We say simply "triangle" instead of "upward equilateral triangle" and "size" instead of "side length."

The necessity will be proven first. Assume that a holey triangle $T$ can be tiled with diamonds and consider such a tiling. Let $T^{\prime }$ be a triangle of size $k$ in $T$ containing $h$ holes. Focus on the diamonds which cover (one or two) cells in $T^{\prime }$. Let them form a figure $R$. The boundary of $T^{\prime }$ consists of upward cells, so $R$ is a triangle of size $k$ with $h$ upward holes cut out and possibly some downward cells sticking out. Hence there are exactly $\left(k^2+k\right)/2-h$ upward cells in $R$, and at least $\left(k^2-k\right)/2$ downward cells (not counting those sticking out). On the other hand each diamond covers one upward and one downward cell, which implies $\left(k^2+k\right)/2-h\ge \left(k^2-k\right)/2$. It follows that $h\le k$, as needed.

We pass on to the sufficiency. For brevity, let us say that a set of holes in a given triangle $T$ is spread out if every triangle of size $k$ in $T$ contains at most $k$ holes. For any set $S$ of spread out holes, a triangle of size $k$ will be called full of $S$ if it contains exactly $k$ holes of $S$. The proof is based on the following observation.

Lemma. Let $S$ be a set of spread out holes in $T$. Suppose that two triangles $T^{\prime }$ and $T^{\prime \prime }$ are full of $S$, and that they touch or intersect. Let $T^{\prime }+T^{\prime \prime }$ denote the smallest triangle in $T$ containing them. Then $T^{\prime }+T^{\prime \prime }$ is also full of $S$.

Proof. Let triangles $T^{\prime },T^{\prime \prime },T^{\prime }\cap T^{\prime \prime }$ and $T^{\prime }+T^{\prime \prime }$ have sizes $a,b,c$ and $d$, and let them contain $a,b,x$ and $y$ holes of $S$, respectively. (Note that $T^{\prime }\cap T^{\prime \prime }$ could be a point, in which case $c=0$.) Since $S$ is spread out, we have $x\le c$ and $y\le d$. The geometric configuration of triangles clearly satisfies $a+b=c+d$. Furthermore, $a+b\le x+y$, since $a+b$ counts twice the holes in $T^{\prime }\cap T^{\prime \prime }$. These conclusions imply $x=c$ and $y=d$, as we wished to show.

Now let $T_n$ be a holey triangle of size $n$, and let the set $H$ of its holes be spread out. We show by induction on $n$ that $T_n$ can be tiled with diamonds. The base $n=1$ is trivial. Suppose that $n\ge 2$ and that the claim holds for holey triangles of size less than $n$.

Denote by $B$ the bottom row of $T_n$ and by $T^{\prime }$ the triangle formed by its top $n-1$ rows. There is at least one hole in $B$ as $T^{\prime }$ contains at most $n-1$ holes. If this hole is only one, there is a unique way to tile $B$ with diamonds. Also, $T^{\prime }$ contains exactly $n-1$ holes, making it a holey triangle of size $n-1$, and these holes are spread out. Hence it remains to apply the induction hypothesis.

So suppose that there are $m\ge 2$ holes in $B$ and label them $a_1,\dots ,a_m$ from left to right. Let $\ell$ be the line separating $B$ from $T^{\prime }$. For each $i=1,\dots ,m-1$, pick an upward cell $b_i$ between $a_i$ and $a_{i+1}$, with base on $\ell$. Place a diamond to cover $b_i$ and its lower neighbour, a downward cell in $B$. The remaining part of $B$ can be tiled uniquely with diamonds. Remove from $T_n$ row $B$ and the cells $b_1,\dots ,b_{m-1}$ to obtain a holey triangle $T_{n-1}$ of size $n-1$. The conclusion will follow by induction if the choice of $b_1,\dots ,b_{m-1}$ guarantees that the following condition is satisfied: If the holes $a_1,\dots ,a_{m-1}$ are replaced by $b_1,\dots ,b_{m-1}$ then the new set of holes is spread out again.

We show that such a choice is possible. The cells $b_1,\dots ,b_{m-1}$ can be defined one at a time in this order, making sure that the above condition holds at each step. Thus it suffices to prove that there is an appropriate choice for $b_1$, and we set $a_1=u,a_2=v$ for clarity.

Let $\Delta$ be the triangle of maximum size which is full of $H$, contains the top vertex of the hole $u$, and has base on line $\ell$. Call $\Delta$ the associate of $u$. Observe that $\Delta$ does not touch $v$. Indeed, if $\Delta$ has size $r$ then it contains $r$ holes of $T_n$. Extending its slanted sides downwards produces a triangle ${\Delta }^{\prime }$ of size $r+1$ containing at least one more hole, namely $u$. Since there are at most $r+1$ holes in ${\Delta }^{\prime }$, it cannot contain $v$. Consequently, $\Delta$ does not contain the top vertex of $v$.

Let $w$ be the upward cell with base on $\ell$ which is to the right of $\Delta$ and shares a common vertex with it. The observation above shows that $w$ is to the left of $v$. Note that $w$ is not a hole, or else $\Delta$ could be extended to a larger triangle full of $H$.

We prove that if the hole $u$ is replaced by $w$ then the new set of holes is spread out again. To verify this, we only need to check that if a triangle $\Gamma$ in $T_n$ contains $w$ but not $u$ then $\Gamma$ is not full of $H$. Suppose to the contrary that $\Gamma$ is full of $H$. Consider the minimum triangle $\Gamma +\Delta$ containing $\Gamma$ and the associate $\Delta$ of $u$. Clearly $\Gamma +\Delta$ is larger than $\Delta$, because $\Gamma$ contains $w$ but $\Delta$ does not. Next, $\Gamma +\Delta$ is full of $H\backslash \{u\}$ by the lemma, since $\Gamma$ and $\Delta$ have a common point and neither of them contains $u$.



If $\Gamma$ is above line $\ell$ then so is $\Gamma +\Delta$, which contradicts the maximum choice of $\Delta$. If $\Gamma$ contains cells from row $B$, observe that $\Gamma +\Delta$ contains $u$. Let $s$ be the size of $\Gamma +\Delta$. Being full of $H\backslash \{u\},\Gamma +\Delta$ contains $s$ holes other than $u$. But it also contains $u$, contradicting the assumption that $H$ is spread out.

The claim follows, showing that $b_1=w$ is an appropriate choice for $a_1=u$ and $a_2=v$. As explained above, this is enough to complete the induction.