26
$\begingroup$

A regular hexagon is divided into a triangular grid, and completely tiled with diamonds (two triangles glued together). Diamonds can be placed in one of three orientations. Prove that, no matter how the board is tiled, there will be the same number of diamonds in each orientation.

Here is an example of such a tiling. Though this hexagon has 5 triangles to a side, the problem asks you to prove this for any size hexagon, and any tiling of it.

$\qquad\qquad\qquad\qquad\quad$enter image description here

This is one of those puzzles that has many solutions, so I'm very curious to see what people's favorite approaches are. Therefore, I'm going to hold off on accepting an answer for a while, to try to get as many different solutions as I can.

Improve this question
$\endgroup$
2
  • $\begingroup$ Out of curiosity, what software did you use to create this image? $\endgroup$
    – Caleb
    Commented Apr 18, 2015 at 1:04
  • $\begingroup$ @CalebBernard I did not make the image. I could give the image source, but it is on a webpage with three solutions to this puzzle (none appearing below), so I won't do so yet. $\endgroup$
    – Mike Earnest
    Commented Apr 18, 2015 at 1:24

12 Answers 12

Reset to default
17
$\begingroup$

I think I've found a really easy proof.

Every tile with vertical sides needs to have two other tiles with vertical sides adjacent to it, or the vertical boundary of the hexagon. For a given tile with vertical sides, following these adjacent tiles yields a specific path to both vertical sides of the hexagon.

This means that every tile with vertical sides lies on a path that starts at the left side of the hexagon and ends at the right, and consists only of tiles with vertical sides. None of these paths can intersect, since that would create two different paths from a single tile with vertical sides to the left side of the hexagon, which cannot exist according to the first paragraph.

Since none of the paths intersect, every path between the left and right sides of the hexagon has to start and end at the same height. Therefore, every path must contain an equal number of each of the two differently oriented tiles with vertical sides. Since every tile with vertical sides lies on such a path, the total number of these two differently oriented tiles must be equal.

Repeat this symmetrically for two other orientations to find that the number of tiles of each orientation must be equal.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Very nice proof. I think it could be made even easier by the simple observation that a+b=b+c=c+a is equivalent to a=b=c. Then you can drop the whole crossing and up and down stuff. Instead just count vertical strokes. By your argument they must be the same number in each "column" and the boundary. You can map 1-to-1 all vertical strokes except the left boundary, say, to all tiles that have vertical sides (i.e. two kinds, as in a+b above) by associating each such tile with its right vertical edge. $\endgroup$
    – Paul Panzer
    Commented Nov 22, 2020 at 0:33
  • $\begingroup$ Ah, you're right. Once you know that there is an equal number of strokes in each orientation, the result follows easily. $\endgroup$
    – Sebastian Reichelt
    Commented Nov 22, 2020 at 19:14
17
$\begingroup$

I want to post an answer that is more intuitive than mathematical.
This picture perfectly represents it: enter image description here

White, grey and black are used to highlight the diamonds with the same orientation. The right picture shows a weird solid, I guess everyone can see it.
Well, it's intuitive to see that, for any configuration, the black area is equivalent (white and grey as well): it's like extruding parts of your floor (aka building stairs!), the area on which you can walk doesn't change!

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ Your shape keeps flipflopping in my head. One moment black is "up", the next it is "down". But I like this proof. $\endgroup$
    – Floris
    Commented Apr 18, 2015 at 18:27
  • 2
    $\begingroup$ @Floris My intention is indeed to solve this problem as a puzzle (we're in Puzzling, eheh!), and not as a pure math task. $\endgroup$
    – leoll2
    Commented Apr 18, 2015 at 18:34
  • 6
    $\begingroup$ You're assuming that every solution "looks like" a stack of cubes. How do you know that to be true? Indeed, assuming that every solution looks like a stack of cubes is pretty much assuming the thing you're being asked to prove. $\endgroup$
    – David Richerby
    Commented Apr 18, 2015 at 18:46
  • 2
    $\begingroup$ @Floris: Ow, it took me a while to see it flipped, and once I do I have to struggle to "hold" that interpretation and it hurts my head. I suppose I played too much Q*bert in my youth. $\endgroup$
    – user1502
    Commented Apr 18, 2015 at 19:20
  • 2
    $\begingroup$ @leoll2 It's your job to convince us that it can't be anything else. How can I be sure there isn't some weird tiling that doesn't look like a stack of cubes? $\endgroup$
    – David Richerby
    Commented Apr 18, 2015 at 20:11
9
$\begingroup$

Here's a 3D-inspired proof.

Take any tiled hexagon, and look at its vertical lines.

First, observe that due to the shape of the tiles, all vertical lines must have the same length as the left and right side of the hexagon, possibly with gaps in between.

So, if none of them have gaps, and all of them end at the bottom, the entire tiling has to look like this ("completely filled cube"):

completely filled cube

We show that it is possible to transform any other tiling into a "completely filled cube" without changing the number of tiles in each orientation.

First, select a fragment of a vertical line that doesn't end at the bottom. It has to end at a horizontal tile instead, as the other two tiles both have vertical sides. Hopefully, the situation looks like this ("corner"):

corner

But maybe there are one or two additional lines originating at the same spot, like this:

non-corner

If that is the case, follow one of them. It must belong to another horizontal tile adjacent to the current one. (You can see this from the picture.) So after following the line, you are in the same situation again, but closer to one of the sides of the hexagon (which guarantees termination, since there is definitely a vertical line in the direction you just came from). Continue in the same direction until you reach a "corner".

Now that you have reached a "corner", "fill it":

filled corner

Obviously, the number of tiles in each orientation has stayed the same. However, a vertical line fragment has just moved downwards.

Repeat this algorithm until all vertical lines end at the bottom and all gaps are removed, resulting in the "completely filled cube" (see above).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Cool! It also proves that any tiling can be transformed into any other by a sequence of "corner fillings", or small hexagon rotations $\endgroup$
    – Mike Earnest
    Commented Apr 18, 2015 at 0:19
  • $\begingroup$ Yes, and in a way it proves that the 3D interpretation always works. But I think that could be proved much more directly, as in "take any tiling, and build a corresponding 3D structure as follows..." $\endgroup$
    – Sebastian Reichelt
    Commented Apr 18, 2015 at 1:06
  • $\begingroup$ good :) basically 3d rotation. I did the 2d one. Ever met that puzzle? $\endgroup$
    – CoffeDeveloper
    Commented Apr 18, 2015 at 1:06
7
$\begingroup$

Interestingly enough, looking at the image as a 3d graph, you can see that each "face" has the same number of tiles. So, if you looked at it from the left, you'd see 25 squares. Top, 25 squares. Right, 25 squares. And each of the 3 orientations corresponds to one of the faces.

Improve this answer
$\endgroup$
3
  • 6
    $\begingroup$ I feel like this argument is convincing, but only for the particular tiling you are looking at. How can you be sure the optical illusion will happen for every possible tiling? $\endgroup$
    – Mike Earnest
    Commented Apr 17, 2015 at 21:25
  • 4
    $\begingroup$ This answer seems to be a way to visualize the answer... it proves nothing. It is, however, possible to prove it this way. $\endgroup$
    – kaine
    Commented Apr 17, 2015 at 21:49
  • $\begingroup$ I totally agree. I "know" the answer, but explaining it is beyond me this Friday. $\endgroup$
    – JonTheMon
    Commented Apr 17, 2015 at 21:55
5
$\begingroup$

Yet another; this one is triangle-based and might be more of a standard proof.

Divide the entire hexagon into triangles and assign numbers to the vertical lines like this (or similarly):

numbers

Now, for any triangle-based shape (which does not necessarily have to be a tiling) define its "degree" as the number obtained by adding all of the numbers assigned to its left boundary and subtracting all of the numbers assigned to its right boundary. For example, the shape shape

has a "degree" of $(1-2)-(2+2-1-2)=-2$.

Now, build a tiling piece by piece, and consider the "degree" of the resulting shape. Adding a horizontal tile does not change the degree, adding one of the others increases or decreases it by 1, respectively:

-1 +1

Since the entire hexagon has a degree of 0, the number of the two tiles shown must be equal. Repeat symmetrically in another direction.

Improve this answer
$\endgroup$
5
  • $\begingroup$ You can divide the hexagon in any number of shapes then the sum of degrees of those shapes is 0. Technically this does not answer because you still have to prove you can build the tiling (for example by extruding, you just proved that if a tiling exists then it must have degree 0) But this answer provide for sure a missing piece to the proof so +1 $\endgroup$
    – CoffeDeveloper
    Commented Apr 18, 2015 at 12:34
  • $\begingroup$ The way I understand the question, there is no need to prove that a tiling always exists. But it does, of course. :-) (See my first answer.) $\endgroup$
    – Sebastian Reichelt
    Commented Apr 18, 2015 at 13:22
  • $\begingroup$ and to see that you can build all possible tilings need my answer :) $\endgroup$
    – CoffeDeveloper
    Commented Apr 18, 2015 at 15:50
  • $\begingroup$ Oh, now I understand what you are saying. By "build", I mean something different: Start with one tile; that is your first shape. Then add one tile after another, until you reach the tiling that you originally had. $\endgroup$
    – Sebastian Reichelt
    Commented Apr 18, 2015 at 17:42
  • $\begingroup$ Nope, for me is starting from a valid state (just have to give one, that's trivial) then apply some kind of transformation that leave you in another valid state. Build as you say is harder because you need some kind of "pre-emption" wich is possible but require search, while in my post I don't use any search, just pre-fixed "transitions" that makes reasoning very easy.. $\endgroup$
    – CoffeDeveloper
    Commented Apr 19, 2015 at 0:00
3
$\begingroup$

Let's consider the triangular grid by column.

enter image description here

Each column in the left half has one more left-pointing triangle than right-pointing triangles. In the right half there is an excess of one right-pointing triangle.

Diagonal lozenges contribute to exactly one left-pointing and one right-pointing triangle in a column. Let's ignore these. You are left with left with the triangles that are part of a horizontal lozenge. A horizontal lozenge is made of a left-pointing triangle in one column (red) and a matching right-pointing triangle in the column at the right (green).

enter image description here

The triangles we ignore consists of pairs of left-pointing and right-pointing triangles in one column. So in each column there still must be an excess on one red triangle in the left half and an excess of one green triangle in the right half.

In the first column there must be one red triangle because there is an excess of one and there can be no green triangle. That triangle is matched by a green triangle in the 2nd column. In column 2 there is a 1 green triangle, so there must be one more red triangle. That is 2. These 2 red triangles have matching green triangles in the 3rd column, etc.

As you see there is one more red triangle in each subsequent column, up to the middle line. The last column before the middle line has 5 red triangles. There are 5 matching green triangles right of the middle line. But still we now have an excess of 1 green triangle, the count of red triangles decreases to 4. From there on the count decreases with each column. The result is that regardless of how the lozenges are placed, the red triangles count in the columns form the sequence 1,2,3,4,5,4,3,2,1,0, which sums to 25.

That means that there will always be 25 red triangles. And these are halves of the horizontal lozenges, so there will aways be 25 horizontal lozenges.

By rotational symetry the same applies to left-diagonal and right-diagonal lozenges. That means that regardless how they are placed there will always be 25 of each of the 3 types of lozenges.

QED

Improve this answer
$\endgroup$
2
$\begingroup$

Here's my attempt to prove it.. It seemed impossible until I finally exploited a trick.

I start from a valid configuration where there's only one change possible (rotating the 3 semilines in the middle: any other change would at same time change number of diamonds an create triangles.)

Proof attempt to the puzzle by Dario Oliveri

Once you do that change you are free to undo it (useless, I'll mark it blue) or to do other 3 changes (in red). You immediately note that you can do that "change" only on points that have lines placed like the middle of the first move, or the middle of the initial cube.

Once you do your 2nd move you'll be unable to undo the first move (grey now) because doing so would create triangles and other shapes.

another wireframe cube

(Assuming my first move was a clockwise rotation of 1/6 round, my undo is a 1/6 anti-clockwise)

Basically you can just check that the only possible moves are rotations of group of tiles made by 3 diamonds (1 for each orientation) (you can check all possible moves on a 2x2x2 "cube" and see that is true).

Hence you note also that rotation keeps number of diamonds for each orientation the same.

There's a little piece missing of the proof: I did not show that starting from my first cube I can do all possible tilings, that's because rotations have "inter-dependencies" and I don't know if at some point "I'll get stuck" without more possible moves.

I'm too sleepy for that proof, but I developed another proof method I'll let you the pleasure to use it:

Extruding columns starting from an "empty" cube:

You see you cannot extrude a column to a length greater than the preceding columns (there are 2 directions to check for preceding columns) because you'll get triangles.

enter image description here

You have now a way to compute really all possible tilings. You start with the backmost column, and once decided a height you can extrude the 2 neighbour to any height lower or equal to the backmost column. After that you can do the same for the next 3 columns.

There is no dependency on rotations here. You choose a number, and then you can choose again same number or a lower number. That's much easier but have some help from imagination (3rd dimension in a problem that has 2 dimensions).

Well, probably that's not a formal proof. But helps imagination you have 2 ways to attack the problem, and probably those can be worked around for a formal proof. But I think is more interesting the intuition than the proof. Without some intuition there will never be some proof.

The key seems always to be the same. Starting from a trivial configuration the only possible moves incidentally preserves the number of diamonds for each configuration.

P.S:

I have never seen that puzzle before. Hope you like my first answer in puzzling exchange.

Improve this answer
$\endgroup$
1
$\begingroup$

From the triangular tiling with a 'cube boundary', we can see that:

  • there are an equal number of line segments at $0^\circ, 120^\circ, 240^\circ$

  • each rhombi covers exactly one type of line segment

Improve this answer
$\endgroup$
2
  • $\begingroup$ Isn't that just repeating what leoll2 said, that when "extruding parts of your floor" that "the area on which you can walk doesn't change". $\endgroup$
    – Jaap Scherphuis
    Commented Feb 2, 2020 at 10:47
  • 1
    $\begingroup$ That's actually a much better proof than my answers. It's interesting that you just ignore all of the lines that are visible and focus on the invisible ones instead. $\endgroup$
    – Sebastian Reichelt
    Commented Nov 7, 2020 at 15:37
0
$\begingroup$

If we assign $S$ to be the side length of the hexagon (in number of diamond side lengths) and $A$,$B$,$C$ to be the number of diamonds of each type where $A$ is longer than tall, $B$ points to the bottom right/top left, and $C$ points to the bottom left/top right.

The total number of diamonds (aka area) lets us make this equation:

$$S^2*3=A+B+C$$

Imagine the $S=1$ hexagon... There are only 2 solutions which are the same one rotated by 30 degrees. There needs to be all three diamonds present in order of the central portion to add up to 360 degrees.

We can imagine that there are 3 paths which proceed from the top to bottom, upper right to lower left, and upper left to lower right corners. The total movement down for any path you follow (top to bottom) must be equal to $2S$ but the movement left to right must be zero. If you move the whole way down on an $A$ diamond, you do not move right or left. If you move down on a $B$ or $C$ diamond you move right or left respectively. In order for all paths to not move left or right, the total number of $B$ and $C$ must be equal. If you rotate the graph 60 degrees such that a different pair of corners point up/down, you can show this for $A$ and $B$ or $A$ and $C$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can you elaborate a little more on where these 3 paths come from? Are there several possible paths (from top to bottom), or unique given the tiling? Are these like a pawn hopping from diamond to adjacent diamond, or an ant following the edges? $\endgroup$
    – Mike Earnest
    Commented Apr 17, 2015 at 23:21
  • $\begingroup$ It is vector addition....it refers to all paths that proceeds from on corner to the opposite one without back tracking. It is ant following edges. $\endgroup$
    – kaine
    Commented Apr 17, 2015 at 23:26
  • $\begingroup$ To clarify, there is no path that doesnt follow B=C so add them all up and B=C $\endgroup$
    – kaine
    Commented Apr 17, 2015 at 23:45
0
$\begingroup$

Not sure this is a full answer but I'm getting tired.

enter image description here

Let n = number of triangles to a side. Take the diamonds touching EDIT: n+1 adjacent edge units (just at 1 point doesn't count): At least one diamond must be different from the others. Let all the changes happen in the corners, with a change at every other corner. We've made a loop which can contain a hexagon with side length n-1, and the number of diamonds of each kind is equal. Induction down to n = 1, where it's obviously equal.

Now let a hexagon outer loop deviate from our "changes only occur at corners" policy. Color all of the outer edge-adjacent diamonds a certain color (say, black) and leave any diamonds that jut out from this loop white. Now we can see a broken loop surrounding another (certainly broken) loop of n-1. Color in this inner loop with a second color, again leaving all rebels white. Do this down to the n=1 hexagon, then color the rebels by orientation.

Now if you look at my diagram, the inner purple hexagon really wants a red tile at bottom instead of an orange and a pink. Imagine this is a mosaic. Rip up a red tile and the orange and pink rebels in the middle, and put the red tile there. The purple hex is happy now. Now make the green hex happy (a change only at every other corner) -- The bottom sideways diamond wants to be two slanted diamonds to fit around the purple hex -- add in our orange and pink tiles to the side, putting the green tile wherever we robbed the red tile from earlier. I think it's clear that this process can be continued until we reach our "optimal hexagon". My brain is too fried to prove this definitively, though.

EDIT: I believe these two things are true: 1. If we take a non-optimal hexagon, every concentric loop will be unhappy. 2. Fixing an unhappy loop necessarily adds tiles to our 'hand' of removed mosaic tiles. 3. To fix the innermost hex, rob any appropriate rebel.

With these two things in mind, it's impossible that we will want to fix a hex but will not have tiles in our 'hand' of removed tiles, assuming that there is at least one rebel of the kind needed by the n=1 loop.

Improve this answer
$\endgroup$
-2
$\begingroup$

There is no need for long proofs. Think 3D.

Imagine that some cubes are fixed in a corner of a room. The three orientations are the faces that we see since from every side we need to see the same number of faces.

Improve this answer
$\endgroup$
2
  • $\begingroup$ there is a proof from numbering also . Put two 0s in a corner and construct the number such that the 3 orientations always add up to -1,0and 1 . By adding row by row total sum will be 0 Therefore X(1) + Y(0) + Z(-1) = 0 which means X= Z . Now rotate the numbering 120degress With similar argument X=Y This completes the proof $\endgroup$
    – ghaura mahabaduge
    Commented Feb 2, 2020 at 8:40
  • $\begingroup$ Unfortunately this is essentially the same as the answer already given by leoll2, and which was proved in Sebastian Reichelt answer. The proof you mention in your comment was also already posted in Sebastian Reichelt second answer. $\endgroup$
    – Jaap Scherphuis
    Commented Feb 2, 2020 at 9:34
-2
$\begingroup$

In order to prove this principle, through Pascal programming to generate different diamond layouts, through different colors, you will find that this 2D paving problem has become a 3D model generation problem, and these models are very similar to urban planning or architecture. A trial calculation of the layout of the tower and the podium. Another feature is that the generated three-dimensional model does not have a large upper part and a small lower part, and is a stable rectangular parallelepiped layout. An "upgrading" from a two-dimensional problem to a three-dimens layout.enter image description hereional enter image description here

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ How does this prove the claim in the question? $\endgroup$
    – melfnt
    Commented Nov 20, 2020 at 10:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.