### Tricky Puzzle of the Diagonal Tiles

A reasonably tough puzzle a friend of mine thought up: Which may well be insoluble, or may have been mentioned in some place already.

Consider a rectangular grid of arbitary size. Say, M by N grid squares, in size.

The grid is filled with tiles, each of them containing a 45 degree (or Pi/2 radian, for pure maths pedants) line segment – the line either goes from top right to bottom left, or top left to bottom right.

For example, below is a possible configuration:

Obviously, there are 2^(M*N) possible configurations. Now, what concerns us are the regions generated by the outer boundary of the grid and the diagonal tile lines. I.e. the red lines. Specifically, the number of distinct closed regions thus generated.

#### The Big Questions are:

1. What is the minimum number of regions for a given grid?

2. What is the maximum number of regions for a given grid?

3. Out of all the possible configurations, how is the region number distributed?

1 can be solved semi-easily. The answer is M + N regions. Proof is an exercise for the reader. (Think about the available length of outer-boundary available, and how much each external-touching region must use up)

2 hasn't been solved, but looks okay-ish.

3 is insanity itself.

Why not have a go? If anyone can solve this, I'll be willing to reward you with something pointless and insignificant. Have fun!

## One comment

## baf

Unless I'm mistaken, the maximum number of regions is M+N+((MN-M-N+2)/2) if M and N are both even, M+N+((MN-M-N+1)/2) otherwise. Proof follows:

Each half-tile has only two edges that can be joined to other half-tiles, so every region will be a sequence of half-tiles chained together with no branching. Such a sequence must either form a loop or have two endpoints. The only place where we can have endpoints is on the edge of the rectangle, and each tile edge that is on the edge of a rectangle must be an endpoint. There are 2(M+N) tile-edges that are on the edges of the rectangle, so there must be exactly M+N edge regions. Only the number of interior regions can vary.

Now, to maximize the number of interior regions, we must make them as small as possible. Interior regions must form loops, and the smallest possible loop is four half-tiles in a diamond, with an area of 2 tiles.

Lemma: For every configuration of the tiles, if you remove the edge regions, the area remaining can be divided into minimal diamonds.

Proof of lemma: Color the vertices alternately white and black, in a checkerboard pattern. Diagonals always join either two white vertices or two black vertices; color all diagonals according to the vertices they join. Once you eliminate the edge regions, the remaining area is enclosed by one or more closed loops compsed entirely of diagonals; since the diagonals enclosing an interior area share vertices, each such boundary will be entirely white or entirely black. Draw in all diagonals within this area that have the same color as the boundary. You have now turned the entire area into a section of the infinite all-black or all-white diagonal grid, which is composed entirely of minimal diamonds.

Back to the main proof. Once we eliminate the edge regions, we can always divide the remaining area into regions of minimal size. So the problem hinges on minimizing the total area of the edge regions.

Each tile on the edge must contribute at least one of its half-tiles to the edge regions. If M and N are both even, that's all they need to contribute: each corner tile can be divided across the corner, and the remaining edge tiles can be paired off in a zig-zag pattern: \/\/\/. In this case, the area of the edge regions is 1/2 times the number of edge tiles, or M+N-2. The area remaining for interior regions is MN-M-N+2, so the number of interior regions (each a minimal diamond with area 2) is (MN-M-N+2)/2. Add in the M+N edge regions, and you get M+N+((MN-M-N+2)/2).

If M or N is odd, you can't do things quite as efficiently. If you keep the same zig-zag pattern along the edge as in the even case, one corner on each odd-length edge will be split the wrong way and wind up with its entire area in edge regions. The only way to avoid this is to break the zig-zag — \/\\/\/ —, which will result in an edge region containing at least one half-tile of a non-edge tile, which is no better (and in most cases worse) than what you get if you preserve the zig-zag. So if one dimension is odd, you'll wind up with one extra half-tile in edge regions for each of the two odd edges, for a total additional area of 1; the total area of the edge regions will be M+N-1, and by the same reasoning as above, the total number of regions will be M+N+((MN-M-N+1)/2).

If both dimensions are odd, one corner tile on each edge of the rectangle will contribute an extra half-tile, but since the horizontal and vertical edges share corners, we still need only two corner tiles to handle all four edges. So the number of regions winds up the same as in the case where only one dimension is odd. (In the case where one dimension is even, the all-edge-region tiles will be on adjacent corners; in the case where both are odd, on opposite corners.)

06 Apr 2005, 17:59

## Add a comment

You are not allowed to comment on this entry as it has restricted commenting permissions.