Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Truchet Tilings

Puzzle

An 8x8 square grid has to be covered with isosceles triangular tiles with two tiles per square. Tiles come in two colors: black and white. Such tilings are called Truchet tilings. A tiling is said to be "fine" if no two tiles sharing an edge have the same color. How many "fine" Truchet tilings are there?

Source

From a Math competition.

Solution

truchet-tiles

Let us solve the problem for an m by n grid. We have four choices for the top-left square as shown in the figure. For any of these choices, there are only two ways to tile the square to the right of this square. For example, if the tiles in the figure are denoted by A, B, C, D, then, A or B may be followed only by A or B, both choices being valid. Similarly, C or D may be followed by only C or D. Continuing this way, there are exactly 2n+1 ways to tile the top-most row. Now, let us tile the row below the top-most row. There are two choices for the left-most square. For each of these two choices, there is exactly one choice for the square to its right, and so on. In other words, the entire row is determined by the row above and the left-most tile in that row. So for an m x n grid, there are 2m+n possible tilings.

The tiles shown in the figure are called Truchet Tiles. Further infrormation: article at Wolfram, and Truchet tile generator.

Previous Puzzle: Cube Problems

Imagine a cube on a flat table, tantalizingly balanced on one of its vertices such that the vertex most distant from it is vertically above it. (a) What is the length of the shortest path an ant could take to go from the topmost vertex to the bottommost vertex? (b) What will be the projection on the table if there is a light source right above the cube? (c) What would be the cross-section obtained if we slice the cube along a plane parallel to the table, passing through the midpoint of the topmost and the bottommost points of the cube? (d) Split a large 3×3×3 cube into 27 small 1×1×1 cubes. An ant can burrow through one small cube to an adjacent small cube if these two cubes share a face. Can the ant burrow through all of the 27 small cubes, visiting each small cube exactly once? Can such a sequence have the additional property that the first and the last small cube share a face?

Next Puzzle: Treasure Island

An old parchment has directions to a treasure chest buried in an island:

“There is an unmarked grave and two tall oak trees. Walk from the grave to the left tree, counting the number of steps. Upon reaching the left tree, turn left by 90 degrees and walk the same number of steps. Mark the point with a flag. Return to the grave. Now, walk towards the right tree, counting the number of steps. Upon reaching the right tree, turn right by 90 degrees and walk the same number of steps. Mark this point with another flag. The treasure lies at the midpoint of the two flags.”
A party of sailors reached the island. They find a pair of tall oak trees merrily swaying in the wind. However, the unmarked grave is nowhere to be found. They are planning to dig up the entire island. It'll take a month. Can they do any better?
4 Nov 2008
© Copyright 2008—2017, Gurmeet Manku.