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!

April 2005

Mo Tu We Th Fr Sa Su
Mar |  Today  | May
            1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30   

Search this blog


Most recent comments

  • Ok this is odd, I got here via Stumble Upon… It's the first time I've come across a Warwick Blogs … by on this entry
  • I've been wondering the same question…what's the secret? I know there's an easier way. I'm just go… by Wanda on this entry
  • chinese? by confucian on this entry
  • Please… please we're not called global warming "deniers" we prefer to be called global warming "in… by Peter Jungmann on this entry
  • Now, to continue, if you need evidence that the 1998 anomaly was not due to solar activity, pick a d… by Zhou on this entry

Blog archive

Not signed in
Sign in

Powered by BlogBuilder