Let $n$ be a positive integer. A regular hexagon $ABCDEF$ with side length $n$ is partitioned into $6n^2$ equilateral triangles with side length $1$. The hexagon is covered by $3n^2$ rhombuses with internal angles $60^{\circ}$ and $120^{\circ}$ such that each rhombus covers exactly two triangles and every triangle is covered by exactly one rhombus. Show that the diagonal $AD$ divides in half exactly $n$ rhombuses.
Problem
Source: Polish MO Second round 2024 P4
Tags: combinatorics
starchan
10.02.2024 19:48
nice problem
We orient the hexagon so that $AD$ is horizontal. We mark points on $AB$ at unit distances with names \[A_0 = A, A_1, A_2, \dots, A_n = B\]Similarily, we mark the points \[D_0 = D, D_1, D_2, \dots, D_n = C\]
Claim: The line $A_iD_i$ has exactly $n-i$ rhombuses crossing over it for all $0 \leq i \leq n$.
Proof: Note that we are interested in proving the $i = 0$ case. To prove the claim, we backward induct with $i = n$ being the obvious base case. Now let us suppose we've proven the result for all $i > j$ and we would like to prove it for $j$.
Consider the sequence of triangles in order, from segment $A_jA_{j+1}$ to $D_jD_{j+1}$. There are exactly $2(n-j)+1$ such triangles, alternating between "up" and "down" triangles. Enumerate the up triangles $U_1, U_2, \dots, U_{n+1}$ and the down triangles $V_1, \dots, V_n$. From the inductive step, we know that there are exactly $n-j-1$ rhombuses crossing $A_{j+1}D_{j+1}$.
Each of these rhombuses covers exactly one $V_i$. Let these $V_i$ be the ones with $i \in \{m_1, m_2, \dots, m_{n-j-1}\}$ where we enforce \[m_1 < m_2 < \dots < m_{n-j-1}\]without losing generality. Imagine cutting out at all the triangles $V_{m_i}$. This creates $n-j-1+1 = n-j$ components, each of which starts with some up triangle and ends in another up triangle. Pick any such component $C$. We show that it has exactly one rhombus not completely contained in it, which would imply that there is one rhombus crossing $A_jD_j$ per component. Since there are $n-j$ such components, this would finish.
Consider a rhombus intersecting $C$. Since everything above $C$, to the left, and to the right is already covered by rhombuses, it follows that either a rhombus intersects $C$ in exactly a up triangle, or is completely contained in it. Note that rhombuses cover exactly $2$ cells, and since the component has an odd number of triangles, it follows that there are an odd number of intersecting rhombuses, in particular, at least one.
Suppose that this component had more than one such rhombus. Pick the two closest ones. Between the two triangles contained by the chosen rhombuses, there are an odd number of triangles. This means that we cannot completely cover it with rhombuses, and that there must be another incomplete rhombus in between, contradicting the fact that the chosen rhombuses were the closest.
Hence each component $C$ contributes $1$ rhombus crossing over $A_jD_j$, and summing over all components, the inductive step is finished. By induction, the claim follows now.
In particular, using the claim on $j = 0$ yields the desired result. $\square$
sami1618
01.07.2024 19:29
The 'aops' configuration is well known https://puzzling.stackexchange.com/questions/12357/tiling-a-hexagon-with-diamonds The technique used in kaine's post seems like it could be modified to solve the question.