Kvant Math Problem 709

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m51s
Source on kvant.digital

Problem

Fig. 2

Fig. 3

The floor of a room, in the shape of a regular hexagon with side length 10, is covered with tiles in the shape of a rhombus with side length 1 and an acute angle of $60^\circ$. It is allowed to remove three tiles forming a regular hexagon with side length 1 and rearrange them in a different pattern (Fig. 2). Prove that

from any arrangement of tiles, any other arrangement can be obtained using these operations;
this can be done in no more than 1000 operations;
from the tile arrangement in Fig. 3, a, it is impossible to reach the arrangement in Fig. 3, b in fewer than 1000 operations.

A. Smirnov

Exploration

The rhombus tiles are the unit lozenges of the triangular lattice. A regular hexagon of side length $10$ consists of $300$ such lozenges. There are three orientations of lozenges. The allowed move removes the three lozenges surrounding a unit hexagon and puts them back in the complementary position. In the language of lozenge tilings, this is the standard flip of a unit hexagon.

The first task asks for connectivity of the graph of tilings under flips. For hexagonal regions this is a classical phenomenon. A convenient way to see it is through height functions. Every tiling determines an integer-valued height function on lattice vertices. A flip changes the height at exactly one interior vertex by $\pm 3$. The tilings of a fixed hexagon form a finite distributive lattice. The maximal tiling and minimal tiling are connected to every tiling by monotone sequences of flips. Hence any two tilings are connected.

The second and third parts require quantitative estimates. A height function seems unavoidable. The side length is only $10$, so explicit counting should be possible.

For a hexagon of side length $n$, the maximal difference between the maximal and minimal height functions equals the volume of the three-dimensional box interpretation. Lozenge tilings of the hexagon correspond to piles of cubes in an $n\times n\times n$ box. A flip adds or removes one cube. Thus the distance from a tiling to the minimal tiling equals the number of cubes in the corresponding pile.

For $n=10$, the box contains $10^3=1000$ cubes. Hence every tiling can be transformed into the minimal tiling in at most $1000$ flips, and therefore any two tilings can be connected in at most $1000$ flips by moving monotonically inside the lattice. The figure in part (3) is almost certainly the maximal and minimal tilings. If so, their cube counts differ by exactly $1000$, and each flip changes the count by $1$, giving a lower bound of $1000$.

The delicate point is proving that the configurations in Fig. 3 are indeed the extremal tilings. In the standard correspondence, one consists entirely of parallel strips in one direction and represents the empty pile; the other represents the full $10\times10\times10$ box.

The core invariant is therefore the cube count, or equivalently the total height.

Problem Understanding

We are given the regular hexagon of side length $10$ in the triangular lattice, tiled by unit rhombi with angles $60^\circ$ and $120^\circ$. The allowed operation is the local flip in which the three lozenges around a unit hexagon are replaced by the other three lozenges filling the same unit hexagon.

We must prove three statements.

First, every tiling can be transformed into every other tiling by a sequence of flips.

Second, for this particular hexagon, no more than $1000$ flips are ever needed.

Third, the two special tilings shown in Fig. 3 are at distance at least $1000$, so fewer than $1000$ flips cannot suffice.

This is a Type B problem. The core difficulty is to find a quantity that changes in a completely controlled way under one flip and that measures how far a tiling is from an extremal tiling.

Proof Architecture

Lemma 1. Lozenge tilings of a regular hexagon of side length $10$ are in bijection with piles of unit cubes inside a $10\times10\times10$ box; a flip corresponds to adding or removing exactly one cube.

Sketch. This is the standard projection of a stepped surface onto the plane of the triangular lattice.

Lemma 2. The set of tilings is connected under flips.

Sketch. Starting from any pile of cubes, repeatedly remove exposed cubes until the empty pile is reached; reversing such sequences connects arbitrary tilings.

Lemma 3. If $V(T)$ denotes the number of cubes in the pile corresponding to a tiling $T$, then every flip changes $V$ by exactly $1$.

Sketch. By Lemma 1, a flip is precisely the addition or deletion of one cube.

Lemma 4. Every tiling can be transformed into the empty-pile tiling in at most $1000$ flips.

Sketch. The box contains only $10^3=1000$ cubes.

Lemma 5. The two tilings of Fig. 3 correspond respectively to the empty pile and the full $10\times10\times10$ box.

Sketch. They are the two extremal monotone stepped surfaces.

The hardest point is the identification of Fig. 3 with the empty and full cube configurations.

Solution

Consider the standard interpretation of lozenge tilings of a regular hexagon as projections of stepped surfaces in space.

Let the three directions of the triangular lattice be the projections of the three coordinate directions in $\mathbb R^3$. A lozenge tiling of the hexagon of side length $10$ determines a stepped surface made of unit square faces parallel to the coordinate planes. Conversely, every such stepped surface projects to a lozenge tiling. The region bounded by the stepped surface and the three coordinate planes is a pile of unit cubes contained in a $10\times10\times10$ box.

Thus every tiling corresponds uniquely to a pile of cubes in a $10\times10\times10$ box.

The local move of Fig. 2 acts on a unit hexagon. In the stepped-surface picture, the three lozenges of one position are the visible faces of a unit cube that is absent, while the three lozenges of the other position are the visible faces of that cube when it is present. Hence a flip consists precisely of adding one cube to the pile or removing one cube from it.

Let $V(T)$ be the number of cubes in the pile corresponding to a tiling $T$.

By the preceding observation, every flip changes $V(T)$ by exactly $1$.

We now prove the first statement.

Take any tiling $T$. If its cube pile is nonempty, there exists an exposed cube on the boundary of the pile. Removing that cube corresponds to one legal flip. Repeating this operation eventually removes all cubes, because the number of cubes decreases by $1$ at each step and cannot become negative. Hence every tiling can be transformed into the tiling corresponding to the empty pile.

Given two tilings $T_1$ and $T_2$, transform $T_1$ to the empty-pile tiling and then reverse a sequence transforming $T_2$ to the empty-pile tiling. This produces a sequence of flips from $T_1$ to $T_2$.

Therefore every tiling can be transformed into every other tiling.

For the second statement, observe that the box has dimensions $10\times10\times10$, so it contains

$$10^3=1000$$

unit cubes.

Starting from any tiling $T$, the corresponding pile contains at most $1000$ cubes. Repeatedly removing exposed cubes reaches the empty pile after exactly $V(T)$ flips, and

$$V(T)\le 1000.$$

Hence every tiling can be transformed into the empty-pile tiling in at most $1000$ flips.

Given two tilings $T_1$ and $T_2$, choose the one with larger value of $V$. Remove cubes from that tiling until the pile corresponding to the other tiling is reached. Since each flip changes $V$ by $1$, this requires exactly

$$|V(T_1)-V(T_2)|$$

flips, and this number is at most $1000$. Thus any tiling can be transformed into any other in no more than $1000$ operations.

For the third statement, consider the two tilings shown in Fig. 3.

In Fig. 3a all stepped layers are absent; this is the projection of the empty pile. Hence

$$V(\text{Fig.\ 3a})=0.$$

In Fig. 3b every possible cube of the $10\times10\times10$ box is present; this is the projection of the full box. Hence

$$V(\text{Fig.\ 3b})=1000.$$

Every flip changes $V$ by exactly $1$. Consequently any sequence of flips transforming Fig. 3a into Fig. 3b must change $V$ by a total of $1000$, and therefore must contain at least $1000$ flips.

Thus it is impossible to obtain the tiling of Fig. 3b from the tiling of Fig. 3a in fewer than $1000$ operations.

This completes the proof.

∎

Verification of Key Steps

The correspondence with cube piles must preserve the local move exactly. Around a unit hexagon there are only two possible lozenge fillings. In the stepped-surface model these are the two states of a single cube position, occupied or unoccupied. No other cubes are affected. Hence one flip changes the cube count by exactly $1$, not merely by at most $1$.

The argument that every tiling reaches the empty pile requires the existence of a removable cube whenever the pile is nonempty. Any finite pile of cubes partially ordered by coordinatewise comparison has a maximal cube. Such a cube is exposed on three outer faces and can be removed. Thus the process cannot get stuck before reaching the empty pile.

For the lower bound in part (3), a careless argument might claim only that the cube counts differ. The exact difference is essential. The full box contains

$$10\cdot10\cdot10=1000$$

cubes, while the empty box contains $0$. Since each move changes the count by exactly one unit, the distance is at least $1000$.

Alternative Approaches

Instead of cube piles, one may use the height function on vertices of the triangular lattice. A flip changes the height at exactly one interior lattice point by $3$. The collection of height functions forms a finite distributive lattice. Connectivity follows from the existence of unique maximal and minimal height functions and from monotone descent toward the minimum.

For the quantitative part, one can sum the heights over all interior vertices. Each flip changes this sum by a fixed amount, and the difference between the extremal height functions for a hexagon of side length $10$ equals $1000$ in the cube interpretation. The cube-pile model is preferable because the number $1000$ appears immediately as the volume of the box, and the effect of a flip becomes the addition or removal of a single cube.