From a Math competition.

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 2^{n+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 2^{m+n} possible tilings.

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

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

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?
© Copyright 2008—2017, Gurmeet Manku.