18
$\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.

$\endgroup$
  • $\begingroup$ Out of curiosity, what software did you use to create this image? $\endgroup$ – Caleb Apr 18 '15 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 Apr 18 '15 at 1:24
8
$\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.

$\endgroup$
6
$\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.

$\endgroup$
  • 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 Apr 17 '15 at 21:25
  • 3
    $\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 Apr 17 '15 at 21:49
  • $\begingroup$ I totally agree. I "know" the answer, but explaining it is beyond me this Friday. $\endgroup$ – JonTheMon Apr 17 '15 at 21:55
6
$\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).

$\endgroup$
  • $\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 Apr 18 '15 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 Apr 18 '15 at 1:06
  • $\begingroup$ good :) basically 3d rotation. I did the 2d one. Ever met that puzzle? $\endgroup$ – GameDeveloper Apr 18 '15 at 1:06
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.

$\endgroup$
  • $\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$ – GameDeveloper Apr 18 '15 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 Apr 18 '15 at 13:22
  • $\begingroup$ and to see that you can build all possible tilings need my answer :) $\endgroup$ – GameDeveloper Apr 18 '15 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 Apr 18 '15 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$ – GameDeveloper Apr 19 '15 at 0:00
5
$\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!

$\endgroup$
  • 3
    $\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 Apr 18 '15 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 Apr 18 '15 at 18:34
  • 3
    $\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 Apr 18 '15 at 18:46
  • 1
    $\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 Apr 18 '15 at 19:20
  • 1
    $\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 Apr 18 '15 at 20:11
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.

$\endgroup$
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$.

$\endgroup$
  • $\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 Apr 17 '15 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 Apr 17 '15 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 Apr 17 '15 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.

$\endgroup$
-8
$\begingroup$

Let S be the surface of the hexagon, and s the surface of one diamond.

Whatever the way you tile them, you'll need S / s diamonds.

$\endgroup$
  • 1
    $\begingroup$ This is true but it does nothing to show that a tiling must have equal numbers of each of the three orientations of diamond. $\endgroup$ – David Richerby Apr 18 '15 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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