A large regular hexagon is cut out of a triangular grid and tiled with diamonds (pairs of triangles glued together along an edge). Diamonds come in three varieties, depending on orientation; prove that precisely the same number of each variety must appear in the tiling.

On the back cover of Mathematical Puzzles: A Connoisseur's Collection (163 pages, 2003) by Peter Winkler. Originally, the problem appeared in "The Problem of Calissons" by G David and C Tomei, American Mathematical Monthly, Vol 96(5), May 1989, p. 429 - 431.

David and Tomei presented a curious "Proof Without Words" (see photos).

Dijkstra's Notes: The pictorial proof is not rigorous because it depends on an "optical illusion". The lack of rigor prompted E W Dijkstra to write two short notes (both notes have the same idea — the second note is a refinement of the first): On the Problem of Calissons (5 July 1989) and On Covering a Figure with Diamonds (11 October 1989). The proof is summarized below.

Dijkstra's proof technique is ingenious! In fact, he proves a more general result: "The triple of frequencies of the three types of diamonds is unique for any figure that admits a tiling." And since the hexagon is symmetric in three directions, it follows that these three frequencies must be identical.

Proof: Consider two different tilings A and B of the same figure. Ignore diamonds that are identical in A and B. The triangles covered by the remaining diamonds form a graph where two triangles are deemed adjacent if some diamond in A or some diamond in B covers both triangles. This graph is essentially a union of cycles of even length. It suffices to prove the theorem for one such cycle. Color all triangles in the original grid black and white so that triangles sharing an edge differ in color. Then all triangles touching a grid line are black on one side and white on the other. Choose a diamond in A that belongs to the cycle and focus on the grid line that divides this diamond into two. The cycle of triangles must cross this grid line an even number of times. In exactly half of these crossings, the cycle moves from a black triangle to a white triangle. So half of these crossings correspond to diamonds in one tiling, and half correspond to the other tiling. QED.

A Simpler Proof: Dijkstra's proof is insightful. However, there is little in common between his proof technique and the intuitive "proof without words" in the picture above. One approach to formalize the intuitive proof is as follows: "Draw grid lines in one of the three directions. Ignore calissons that are bisected by these grid lines. That leaves calissons in two out of three orientations. Let two such calissons be glued together if they share an edge parallel to the grid lines. For an n-sided hexagon, gluing partitions the calissons into n disjoint sets. Each set has 2n members, with an equal number of calissons in two orientations in each set."