#
All entries for Wednesday 06 April 2005

## April 06, 2005

### 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!