All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Shapes
Cutting a Rectangle (Posted on 2007-12-07) Difficulty: 3 of 5
How many ways can a 3x4 rectangle be cut into two polyominoes by cutting along the grid lines? (Not counting reflections and rotations.)
Examples of valid cuts are shown in the first row and invalid cuts are shown in the second row:
+--+--+--+--+   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+
|     |     |   |           |   |  |        |   |  |        |
+  +  +  +  +   +  +--+  +  +   +  +--+--+  +   +  +  +  +  +
|     |     |   |  |  |     |   |        |  |   |  |        |
+--+--+  +  +   +  +--+  +  +   +  +  +--+  +   +  +  +  +  +
|           |   |           |   |     |     |   |  |        |
+--+--+--+--+   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+

+--+--+--+--+   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+
|     |     |   |           |   |  |        |   |     /     |
+  +  +  +  +   +--+--+  +  +   +  +  +--+  +   +  + /+  +  +
|     |     |   |  |  |     |   |        |  |   |   /       |
+--+--+  +  +   +  +--+  +  +   +  +--+--+  +   +  +  +  +  +
|     |     |   |           |   |     |     |   |  |        |
+--+--+--+--+   +--+--+--+--+   +--+--+--+--+   +--+--+--+--+

See The Solution Submitted by Brian Smith    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution for General Case (NxM rectangle) | Comment 8 of 9 |

As interesting as the presented solutions are, they remain for me somewhat unsatisfying, as they are not readily generalisable. I present here my own approach for solving the NxM case. Although I haven’t yet arrived at a solution, I credit myself with having made good progress. Perhaps I may carry things farther, but for now I want to share my interim results in the hope that some readers may find the discussion entertaining and, perhaps, even feel inspired to continue forward.

One useful distinction (already used by a previous contributor) is to distinguish whether a partition intersects a side. Let F(N, M) be the number of partitions of an NxM rectangle, G(N, M) be the number of internal partitions and H(N, M) the number of partitions that intersect a side (excluding rotations and reflections). Then

F(N, M) = G(N, M) + H(N, M)

Since the internal partitions for an NxM rectangle is one more than the set of all partitions for a (N-2)x(M-2) rectangle, we also have

G(N, M) = F(N-2, M-2) + 1

(Note – the reason for the +1 term is that the (N-2)x(M-2) rectangle taken as a whole counts toward G(N, M), but not toward F(N-2, M-2). Note as well that for our later argument, it will be useful to imagine the internal partitions on the left side of the rectangle.)

Now, starting from the bottom left and proceeding counterclockwise while skipping corners; index the external nodes from 1 to 2N + 2M - 4. We see then that H(N, M) is the number of routes starting at any index between 1 and T(N) = [(N-1)/2] (here [] indicates the greatest integer less than function) and terminating at a higher index, subject to the constraints that we avoid closed loops and the insistance that none of the intermediary nodes are external (indexed).

From this we see that it is of interest to investigate the number of simply connected routes between two points. We will also discover that it is especially useful to determine a formula for the number of non-trivial (that is, with length > 1) simply connected routes from a given point to it’s nearest neighbours.

Note first that there is only a single internal route connecting two points adjacent to a corner. (That is, for nodes 1 and 2N + 2M – 4). This is an exception case among the node pairs contributing to H(N, M). More generally, with N, M each exceeding 2 there will be multiple routes connecting external nodes.

How many such routes are there? Consider any internal partition passing through the node immediately above the starting node. We have the choice of passing this internal partition either on the left or the right. Hence, (with the exception cited above) the number of routes through an SEC is one more than twice the number of internal partitions passing through the node one step north of the starting point. (The +1 term is needed to account for a "direct connection" in the absence of any relevant internal partitions).

How many internal partitions pass through the node one step north? This is the same as the number of simply connected routes between starting point and a neighbour neighbouring point on a N-2 X M-2 grid, excluding trivial (length one) routes but (this time) allowing paths along external edges.

The motivation will be to continue in this way is to derive a recursion relation for H...


  Posted by FrankM on 2008-01-10 16:18:32
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information