A discrete hexagon with center \((a,b,c)\) \emph{(where \(a\), \(b\), \(c\) are integers) and radius \(r\) (a nonnegative integer)} is the set of lattice points \((x,y,z)\) such that \(x+y+z=a+b+c\) and \(\max(|x-a|,|y-b|,|z-c|)\le r\). Let \(n\) be a nonnegative integer and \(S\) be the set of triples \((x,y,z)\) of nonnegative integers such that \(x+y+z=n\). If \(S\) is partitioned into discrete hexagons, show that at least \(n+1\) hexagons are needed. Proposed by Linus Tang
Problem
Source: ELMO Shortlist 2023 C7
Tags: Elmo, combinatorics
Phorphyrion
11.08.2023 11:46
The set $S$ is the set of points of a triangular array of side length $n+1$. Align this array in the plane so that one vertex is on the top (with the opposite side at the bottom, parallel to the $x$ axis).
We fix a tiling of $S$ with discrete hexagons, and prove that their number is at least $n+1$. We will define a directed (multi-) graph, with vertex set the set of hexagons together with a additional vertex "at the bottom", beneath the bottom edge of the array.
First construct an edge from the bottom vertex to each hexagon containing points from the bottom row of the array. The multiplicity of these edges is equal to the number of points of the bottom row the hexagon contains. For example, if a hexagon contains $3$ points from the bottom row, construct three directed edges from the bottom vertex to this hexagon.
To define the edges between the hexagons, define the "waterfall" of a hexagon as the set of points outside it with both of their neighbors below them belonging to the hexagon. If a hexagon has a side of $r$ points, its waterfall will be of size $r-1$.
Now, for any two hexagons $A$, $B$, construct directed edges from $A$ to $B$, whose number equals the number of elements of the waterfall of $A$ contained in $B$. Thus each hexagon with side $r$ has an out-degree of exactly $r-1$. The in-degree of such a hexagon is easily seen to be at most $r$ (for hexagons touching the bottom row this is obvious, and for the others because the waterfalls of distinct hexagons don't intersect).
The bottom vertex has out degree $n+1$ and in degree $0$. Each other vertex has in degree greater by at most $1$ from the out degree. We conclude that there must be at least $n+1$ hexagons, as the total out-degree must equal the total in-degree.
dgrozev
24.11.2023 22:31
@above: A nice and instructive idea. I just brushed some details. See here.
Danie1
19.12.2023 17:25
The main idea of this solution is the last two drawings, and counting the number of upwards and downwards triangles in the pictures.
Restate the problem as follows:
Let $S$ be the set of points of a triangular lattice with $n + 1$ points on each side. For example, for $n = 6$:
[asy][asy]
size(5cm);
int n = 6;
for (int i=0; i < n+1; ++i) {
for (int j=0; j < i+1; ++j) {
dot((-0.5, -0.5*sqrt(3))*i + (1, 0)*j);
}
}
[/asy][/asy]
Discrete hexagons look like this:
[asy][asy]
size(10cm);
void drawHexAt(int n, pair coord) {
for (int i=-n; i < n+1; ++i) {
for (int j=-n; j < n+1; ++j) {
if (i - j < n + 1 && j - i < n + 1) {
dot(coord + (-0.5, -0.5*sqrt(3))*i + (1, 0)*j);
}
}
}
}
drawHexAt(0, (-3, 0));
drawHexAt(1, (0, 0));
drawHexAt(2, (5, 0));
[/asy][/asy]
As in the original statement, we want to show that any partition of $S$ into discrete hexagons must use at least $n + 1$ discrete hexagons.
We now visualise the problem in a new way again, in order to be able to apply a straightforward colouring argument.
To draw $S$, we will now place an upwards facing blue equilateral triangle on each point, so the diagram above (which was for $n = 6$), would now look like this:
[asy][asy]
size(5cm);
void drawPointAt(pair coord) {
pair vertex1 = coord + (0.5, -0.5 / sqrt(3));
pair vertex2 = coord + (-0.5, -0.5 / sqrt(3));
pair vertex3 = coord + (0, 1 / sqrt(3));
fill(vertex1--vertex2--vertex3--cycle, lightblue);
dot(coord);
}
int n = 6;
for (int i=0; i < n+1; ++i) {
for (int j=0; j < i+1; ++j) {
drawPointAt((-0.5, -0.5*sqrt(3))*i + (1, 0)*j);
}
}
[/asy][/asy]
Also, our hexagons now look like this:
[asy][asy]
size(10cm);
void drawPointAt(pair coord) {
pair vertex1 = coord + (0.5, -0.5 / sqrt(3));
pair vertex2 = coord + (-0.5, -0.5 / sqrt(3));
pair vertex3 = coord + (0, 1 / sqrt(3));
fill(vertex1--vertex2--vertex3--cycle, lightblue);
dot(coord);
}
void drawHexAt(int n, pair coord) {
pair v1 = coord + (-0.5, -0.5 / sqrt(3)) + n * (-1, 0);
pair v2 = coord + (0, 1 / sqrt(3)) + n * (-0.5, 0.5 * sqrt(3));
pair v3 = coord + (0, 1 / sqrt(3)) + n * (0.5, 0.5 * sqrt(3));
pair v4 = coord + (0.5, -0.5 / sqrt(3)) + n * (1, 0);
pair v5 = coord + (0.5, -0.5 / sqrt(3)) + n * (0.5, -0.5 * sqrt(3));
pair v6 = coord + (-0.5, -0.5 / sqrt(3)) + n * (-0.5, -0.5 * sqrt(3));
draw(v1--v2--v3--v4--v5--v6--cycle, lightblue);
for (int i=-n; i < n+1; ++i) {
for (int j=-n; j < n+1; ++j) {
if (i - j < n + 1 && j - i < n + 1) {
drawPointAt(coord + (-0.5, -0.5*sqrt(3))*i + (1, 0)*j);
}
}
}
}
drawHexAt(0, (-3, 0));
drawHexAt(1, (0, 0));
drawHexAt(2, (5, 0));
[/asy][/asy]
Now look at the upside down equilateral triangle "gaps" in these drawings. Note that our drawing of $S$ has $n + 1$ more blue triangles than gaps (for example, one can see this by reflecting each gap upwards and noting that each reflection covers a blue triangle, and only the bottom $n + 1$ blue triangles don't get covered by this process).
Also, note that each hexagon has exactly one more blue triangle than it has gaps (if we include the "gaps" on the border). For example, the middle hexagon has $7$ blue triangles, and $6$ gaps (again this can be proved by a reflection argument).
Note that the gaps of each discrete hexagon must be disjoint. This means that if we partition $S$ into discrete hexagons, then each blue triangle is covered exactly once, whilst each gap is covered at most once.
Combining this with the fact that any set of $k$ disjoint discrete hexagons will cover exactly $k$ more blue triangles than gaps, we deduce that any partition of $S$ into discrete hexagons will require at least $n + 1$ hexagons.