[Guest]

This is a problem that I came up with over 10 years ago, and haven't really ever spent time solving it since then, because I got stuck and real life got in the way. Posting on this site has made me think of it again, and was wondering if anyone had some ideas.

Imagine a square, with a length and width of 1 unit. A square can be subdivided into two rectangles, each with an area of 1/2 of the square. This would be accomplished by drawing a line through the middle of the square.

A square can be subdivided into three rectangles many ways, each with an area of 1/3 of the square. The most obvious way is to draw two lines down the middle so that each subdividing rectangles has a length and width of 1/3 by 1 unit. However, there is another way to subdivide the square into two rectangles each with an area of 1/3. You can make one rectangle with the dimensions of 1/3 by 1 unit, and then draw a line perpendicular to the one to create that, to create two rectangles with dimensions of 1/2 by 2/3 units.

Let me be clear. There are more ways than this to subdivide a square into 3 parts, even 3 parts with equal area, but the purpose is to subdivide a square into equal area rectangles.

Also, a unique solution is based solely on the number of rectangles with specifc dimensions. Even if you can make the rectangles in the square look differently, if they have the same dimensions and quantity as another look, it is not a unique solution.

So, with 1 rectangle with an area of 1 (the square), there is only 1 unique solution.

With 2 rectangles each with an area of 1/2, there is only 1 unique solution.

With 3 rectangles each with an area of 1/3, there are only 2 unique solutions.

Can you continue with the reasoning on how many unique solutions there area for rectangles of areas 1/4, 1/5, 1/6, ...?

Moreover (and here's where I got stuck), can you come up with a function that describes this pattern? This isn't for everyone. I was unable to come up with a function that predicted the next number, both mathematical or conceptual. The issue is not double-counting some solutions (if you work through a few more of these, you'll see what I'm saying.)

[Prime]

You are right about the program finding duplicate solutions. But you can always write a function that post processes the generated solutions to weed out duplicates. I had written this program not as a solution to the problem but to verify that we are not missing out any valid solutions. ...

So the program does exhaustive search of all possible divisions with division into 2 method. Then it sorts the results and weeds out duplicates.

That is not exactly same as finding mathematical formula for the number of possible arrangements.

Still, an efficient algorithm that would traverse all possible combinations seems like a non-trivial task in itself. It could also evolve into a formula.

There are two ways to get duplicate solutions. One is where the algorithm arrives to the identical division pattern through different sequences of divisions. Another – where same sets of rectangles can be arranged in different ways inside the square.

An algorithm avoiding just the first kind of duplicate solutions (arriving to the same division pattern more than once) seems like an interesting programming task in itself. Do you have such an algorithm?

I’ll make an illustration:

Let’s say we had to divide square into n parts. A recursive algorithm could be something like:

RecAlg(area)

1: Go through all possible ways to break area into 2.

__1.1: For each break down:

____1.1.1: If area1 > 1/n then call RecAlg(area1)

____1.1.2: If area2 > 1/n then call RecAlg(area2)

____1.1.3: Store division results

__1.2: Store division result

2: Add up all results.

…

Such algorithm would go through all possible divisions. However, it is not very efficient. It would stumble into exact same division many times over. And the larger is n, more inefficient the algorithm becomes.

On the bright side, the order (number of division variations) for such algorithm is easy to estimate. For a division into n, there are [n/2] valid ways to divide a square into two parts and 2*[n/2] ways to divide rectangle into two parts. (Those ways are: [1/n, (n-1)/n], [2/n, (n-2)/n], and so on.) Thus the Order for division of square into n parts would be: O(n) = O(n-1)*O(1) + O(n-2)*O(2) + … + O(n/2)*O(n/2).

For example, let’s divide square into 5. There are two ways [5/2] to make the initial split of a square into 2. Those are: (1/5, 4/5) and (2/5, 3/5).

Say, program has processed the (1/5, 4/5) split finding the number of variations O(4)*O(1). It moves on to process (2/5, 3/5) split. When algorithm divides the 2/5 area into two rectangles as shown in FIG. 3, it has stumbled into variations already processed, since the same arrangement could have resulted when processing (1/5, 4/5) split.

Question: can you devise an algorithm that would “visit” each different division pattern exactly once? Then the Order of such algorithm would be a half way to the formula. Second half, possibly more difficult, to figure out the formula for: in how many different ways a given collection of rectangles could be fit into a square.

After that, to solve the OP with stipulation no irrational dimensions, all we’d have left is to prove that division into 2 method covers all rational number solutions. If that’s not the case, the problem stands unshaken. We’d have to look for other methods for solution.