[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.)

[Guest]

Could someone show me the solution that I am missing. Here are the solutions the program generated for n =6.

I think I see two...?? Is one a duplicate?

Grrr.... having a hard time with the pic. The one I am pretty sure is unique is half the square divided into 3 sections horizontally (3 stacked boxes) and the other half divided horizontally first and then vertically.

The other is more complicated. You have a similar picture but the last division is rectangle so can be done two ways and you only have one, I think. Try this... one unit rectagle (vertical), then divide horizontal, then vertical, then horizontal, then the final vertical. Dang, I wish I could just draw it.... well I can draw it but can't figure out how to put it on here?

Edited June 7, 2008 by kevralthemathgirl

[Guest]

Ok.... guess I got the picture!

[Guest]

I think I see two...?? Is one a duplicate?

Grrr.... having a hard time with the pic. The one I am pretty sure is unique is half the square divided into 3 sections horizontally (3 stacked boxes) and the other half divided horizontally first and then vertically.

The other is more complicated. You have a similar picture but the last division is rectangle so can be done two ways and you only have one, I think. Try this... one unit rectagle (vertical), then divide horizontal, then vertical, then horizontal, then the final vertical. Dang, I wish I could just draw it.... well I can draw it but can't figure out how to put it on here?

The second one on the second row (the one you think is unique) is actually a duplicate of the third one on the first row. It's turned 90 degrees, but since it's a square, they're the same. The first one on the second row is the missing unique solution.

[Guest]

The second one on the second row (the one you think is unique) is actually a duplicate of the third one on the first row. It's turned 90 degrees, but since it's a square, they're the same. The first one on the second row is the missing unique solution.

Oh, I see it now... doh! Thanks.

[Guest]

The second one on the second row (the one you think is unique) is actually a duplicate of the third one on the first row. It's turned 90 degrees, but since it's a square, they're the same. The first one on the second row is the missing unique solution.

Yes seems there was a problem with how the program made the divisions. got it corrected now.

I was not able to get the program to complete for n=7. the number of ways to divide a square seems to increase dramatically with each increasing value of n. How did you find the solutions for n=6, did you try each and every possible combination?

Thanks kevral and flowstoneknight for helping me find the missing solution.

btw here's the diagram for n=6

Edited June 8, 2008 by vimil

[Guest]

After further optimization of code, I was able to get the solutions for n=7. The program outputs 75 solutions for n=7, and for n=8 the program outputs 186 solutions. I have attached a text file containing the coordinates of the rectangles for the solutions. It would be great if somebody could find a way to convert this to a wmf or emf image. I am having a hard time generating the diagram from the output.

Heres the diagram for n=7. I will try to get the diagram for n=8 in my next post

n7sol.txt

Edited June 15, 2008 by vimil

[Guest]

for n=9 the program output 564 solutions.

so we have

3 - 2

4 - 5

5 - 11

6 - 27

7 - 75

8 - 186

9 - 564

[HoustonHokie]

for n=9 the program output 564 solutions.

Can you post the coordinate output for n=7 in a text file or something? I'm having trouble coming up with all 75 geometrically, and want to figure out where I'm wrong. Glad to know you're still thinking about this - I know I'm having a hard time letting it go.

[Guest]

Can you post the coordinate output for n=7 in a text file or something? I'm having trouble coming up with all 75 geometrically, and want to figure out where I'm wrong. Glad to know you're still thinking about this - I know I'm having a hard time letting it go.

I have attached the coordinate output for n=7. Each solution is seperated by a blank line.

n7sol1.txt

Edited June 17, 2008 by vimil

[Guest]

for n=9 the program output 564 solutions.

so we have

3 - 2

4 - 5

5 - 11

6 - 27

7 - 75

8 - 186

9 - 564

got the program to execute for n=10. the number of solutions for n=10 is 1675. so heres the updated list again

3 - 2

4 - 5

5 - 11

6 - 27

7 - 75

8 - 186

9 - 564

10 - 1675

[Prime]

This math problem runs deep. I'm afraid, dividing one of the n rectangles into two to obtain an n+1 combination is not the solution.

1. It does not cover all possible arrangements even among rational-number solutions.

2. Where is the proof that after expanding one of the rectangles for division and adjusting dimensions of all other rectangles, we don't get irrational dimension solutions? (Although, that proof seems to be within reach.)

3. The arrangement offered by Flowstoneknight (Post49) cannot be obtained by dividing rectangles into two method. It can be proven algebraically to yield irrational number dimensions. However, there are other, more complex arrangements of the sort, where dimensions are not necessarily irrational numbers.

4. Since the OP requires finding a number of different sets of dimensions for each division into n equal areas, regardless of their order inside the subdivided square, the division into two method does not seem to render any orderly way of weeding out duplicate solutions.

I.

Let's start with illustration (and proof) for the point (1) above:

Suppose we divided the square into 9 equal squares with the dimensions (1/3)x(1/3) each (FIG 1). Now let's obtain a 10-division arrangement by dividing the square in the middle into two as shown.

All rectangle dimensions must be adjusted. We can do it by shrinking the top and bottom row of 3 squares each, into two rows of 3 (1/3)x(3/10) rectangles and adjusting squares in the middle into 4 (1/4)x(4/10) rectangles. (FIG 2.)

Or we can adopt an alternative scheme of shrinking/expanding:

Shrink the row at the top into 3 (1/3)x(3/10) rectangles;

The lower two on the left side – into 2 (7/20)x(2/7);

The rightmost 2 at the bottom – into 2 (5/14)x(14/50);

And the remaining 3 in the middle – into 3 (5/21)x(21/50).

(FIG. 3)

Thus we have two very distinguishable arrangements resulting from the very same division of a rectangle into two. With more complex arrangements of rectangles the number of variations resulting from the same operation increases.

II.

Let's prove algebraically that the subdivision found by Flowstoneknight (Post49) yields irrational dimensions.

Suppose, the length of each rectangle at the edge of the square is x and the width is y. Let's further assume that the square was subdivided into n parts (at least 5, but could be more by dividing the middle square, or even the rectangles at the edges.)

Then we have: x+y=1; x*y = 1/n²; Solving we find: x = (1 +- (1 – 4/n²)^1/2)/2

The expression under the square root can only yield rational number when n = 2.

However, the same type of arrangement does not have to follow such a neat symmetrical pattern. For example, it could sport unequal rectangles at the edges:

It seems plausible that such an arrangement is possible. Whereas, to calculate the relation of the dimensions to the side of the original square leads to large equations and higher degree polynomials. And we cannot say (without further research) that those would not yield rational solutions. And again, that arrangement cannot be obtained by "division into two" method.

If we search for solution by using "subdivision into two" method, we must prove that all other arrangements would lead to irrational dimensions (if such is the case.) Then each rectangle must define its relation to all others and identify all different methods of re-arranging rectangles when one is divided.

Alternatively, we could try identify some minimal allowed increment in dimensions of sub-rectangles, if such exist.

I say, if we can even devise an algorithm capable of finding the solution for a given n-division – that could be worthy of publishing in a respectable mathematical journal.

[HoustonHokie]

Oh... my... goodness... When I was obsessing about this a few months ago, it seemed hard enough to figure out the combinations without any interior shapes, knowing that eventually we would need to go there. Thanks, Prime, for making the problem SO MUCH MORE COMPLICATED!!!

[Prime]

First, couple of corrections to my previous post:

1. The illustration of two different arrangements resulting from the same subdivision operation may not be a "proof" that "subdivision into two" method does not cover all variations. Still, it identifies an algorithmic problem. And the method remains unproved.

2. The equation in part II should be x*y = 1/n, not x*y = 1/n². Correspondingly, n=4 yields the only rational solution.

Let's examine possible dimensions for the subdividing rectangles. Suppose, we subdivide the square of side 1 into n rectangles of equal area. The area of each rectangle is 1/n. Then the smallest any side can be is 1/n. (A side smaller than that, would necessitate the other side to be of length greater than 1, the side of the original square.) The shorter side of rectangle can be up to (1/n)^1/2, making it a square.

The next smallest size for a rectangle side is 1/(n-1). No dimensions between 1/n and 1/(n-1) are possible. Such rectangle would leave less than 1/n distance between its end and one of the square sides, making it impossible to fill that area. If there is a rectangle of the side 1/(n-1) there must be one and only one rectangle of side 1/n.

Next size up is (n-1)/n(n-2) for n > 2 as shown on the illustration below. Although, it would not be the smaller side for n = 3.

There may not be any sizes between that and 1/(n-1), since the latter cannot be subdivided. The (n-1)/n(n-2) must necessarily come in a package with 1/(n-1) and 1/n. (FIG. 1)

Incidentally, in Flowstoneknight arrangement, the side of a size (1 – (1 – 1/n)1/2)/2 could be the next size after 1/(n-1), but it is an irrational number, which was disqualified in the earlier posts.

Next rational size that I see is 1/(n-2) as shown in FIG. 2. That one can come with two (1/n)x1 rectangles, or with one (2/n)x(1/2). That makes things more complicated…

The above analysis shows that rectangles come in certain increments and have some forced relations. An algorithm could find all possible dimensions for an n-subdivision, and traverse (perhaps recursively) all possible sets of those dimensions, that would pack the area. The problem with that approach is dealing with remaining free space, which is not a single rectangle.

[Guest]

Incidentally, in Flowstoneknight arrangement, the side of a size (1 – (1 – 1/n)1/2)/2 could be the next size after 1/(n-1), but it is an irrational number, which was disqualified in the earlier posts.

I thought the problem was simplified so that only the arrangements that can be obtained by division of the square and rectangles formed by division of the square were considered valid. If that is the case then flowstoneknights arrangement is invalid not because it has rectangles with sides whose length is an irrational number but because it cannot be obtained by subdivision of a square or rectangles formed by subdivision of the square.

The thing is all arrangements obtained by subdivision of squares and subsequent rectangles have rectangles of rational dimensions but the reverse is not true i.e not all arrangements which have rectangles of rational dimensions can be obtained by subdivision of the square or the subsequent rectangles.

See an example of the latter case posted by HoustonHokie

http://brainden.com/forum/index.php?s=&amp...ost&p=37553

[Prime]

I thought the problem was simplified so that only the arrangements that can be obtained by division of the square and rectangles formed by division of the square were considered valid. If that is the case then flowstoneknights arrangement is invalid not because it has rectangles with sides whose length is an irrational number but because it cannot be obtained by subdivision of a square or rectangles formed by subdivision of the square.

I have accepted the modification to the OP, and I'm discarding irrational solutions. My point is, how can you be sure that "subdivision method" adopted here covers all rational solutions?

Here is a direct quote from the OP.

...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. ...

Whereas, "subdivision method" adapted here is geared toward finding different arrangements of rectangles inside the square -- not finding sets of rectangles with different dimensions that can fill the square. I did not see your program, but I get an impression that the division operation is ambiguous. See illustration in my post 89, where I show how the same division can result in two different arrangements. The reverse is also possible, different division would result in the same set of rectangles.

...The thing is all arrangements obtained by subdivision of squares and subsequent rectangles have rectangles of rational dimensions...

Can you prove that subdivision always yields a set of rational-dimensioned rectangles? (Not that I'm arguing, it's not true. But I think, a proof is in order.)

... but the reverse is not true i.e not all arrangements which have rectangles of rational dimensions can be obtained by subdivision of the square or the subsequent rectangles.

If I understand right, here you support my argument. Which is subdivision method may not be sufficient to find all solutions.

However, I am not completely sure myself. It may, or may not be. For certain, it needs more work, since it does not specify exactly how it re-arranges the dimensions of the rectangles with each new division. And it requires all those proofs I mentioned above. The proofs will help to understand the problem better and help find working algorithm.

[Prime]

Here is an example of unambiguous construction. The square was subdivided in the order shown with the numbers in blue. (In a spiral pattern.) If we were to deconstruct it, we'd have to proceed in the reverse order. I.e. the only side that could be removed first is the one between 6 and 7. Removing of any other side would leave hanging segments and the square would no longer be divided into rectangles. In that spiral division arrangement, the dimensions of rectangles are determined uniquely as shown by formulas, where n is the number of rectangles inside the square. (In this example n = 7).

The formulas also show exactly how the dimensions would be adjusted with further subdivision, or reverse process of deconstruction. This pattern yields only one instance of subdivision.

However, other patterns of subdividing square are not so restrictive and lead to ambiguity as shown in post 89. To make those useful, we'd have to describe exactly how the remaining rectangles must be adjusted when dividing one of them into two.

(The illustration was drawn approximately, without actual measurments. So some rectangles appear bigger.)

[Prime]

The thing is all arrangements obtained by subdivision of squares and subsequent rectangles have rectangles of rational dimensions but the reverse is not true i.e not all arrangements which have rectangles of rational dimensions can be obtained by subdivision of the square or the subsequent rectangles.

See an example of the latter case posted by HoustonHokie

http://brainden.com/forum/index.php?s=&amp...ost&p=37553

Sorry, I missed that point in my previous reply. The example that you reffer to, actually sports irrational dimensions.

I calculate the sides for the rectangles at the edges of the square are: (1 +- 5^1/2/3)/2. Square root of 5 is an irrational number. All other rectangles inside that square have irrational dimensions too.

I have posted a general proof that any arrangement of that type, where the four rectangles at the edges are identical, will have only irrational dimensions. (See my post 89 part II.)

Edited September 10, 2008 by Prime

[Guest]

Sorry, I missed that point in my previous reply. The example that you reffer to, actually sports irrational dimensions.

I calculate the sides for the rectangles at the edges of the square are: (1 +- 5^1/2/3)/2. Square root of 5 is an irrational number. All other rectangles inside that square have irrational dimensions too.

I have posted a general proof that any arrangement of that type, where the four rectangles at the edges are identical, will have only irrational dimensions. (See my post 89 part II.)

Oops, I must have misunderstood HoustonHokies post. Thanks for pointing that out.

Can you prove that subdivision always yields a set of rational-dimensioned rectangles? (Not that I'm arguing, it's not true. But I think, a proof is in order.)

Heres a somewhat informal proof that valid arrangements obtained by subdivision can only produce rectangles with rational dimensions

1) For a valid arrangement every subdivision should divide the rectangle into two smaller rectangles such that the area of one is a multiple of the area of the other.

2) For a division to produce a rectangle of irrational dimensions from a rectangle of rational dimensions, the division has to be made at an irrational point.

Consider a rectangle of dimensions l*b where l and b are rational numbers.

A division at an irrational point at a distance 'a' along one of the dimensions say 'l' of the rectangle will create two rectangles R1 and R2 of dimensions a*b and (l-a)*b respectively

Now for this division to produce a valid arrangement, either area of R1 must be a multiple of the area of R2 or the area of R2 must be a multiple of the area of R1. But it can be shown that this is not possible.

For (l-a)*b to be a multiple of a*b it must be possible to write (l-a) as k*a for some integer k. Note that 'a' is an irrational number. Since 'l' is rational (l-a) is also an irrational number. Similarly since k is an integer (k*a) is also irrational. If we could write (l-a) as (k*a) for some integer k then k*a + a would be equal to l. This is not possible because the sum of two irrational numbers can never be rational. So any division made at an irrational point will not lead to a valid arrangement.

[Guest]

If we could write (l-a) as (k*a) for some integer k then k*a + a would be equal to l. This is not possible because the sum of two irrational numbers can never be rational. So any division made at an irrational point will not lead to a valid arrangement.

Correction to my previous post -

If we could write (l-a) as (k*a) for some integer k then k*a + a would be equal to l. or a*(1+k) = l. This is not possible because the product of an irrational number and an integer cannot produce a rational number. So any division made at an irrational point will not lead to a valid arrangement.

[Prime]

1) For a valid arrangement every subdivision should divide the rectangle into two smaller rectangles such that the area of one is a multiple of the area of the other.

That line of reasoning does not take into account the OP requirement that all subdividing rectangles must be of equal area.

For example: Suppose we have an instance of divison of a unit square into 5 equal area rectangles. The area of each rectangle is 1/5. Then we designate one of the small rectangles for further subdivision into two. Since the square is going to be divided into 6 rectangles, the area of each must be 1/6. Thus the rectangle designated for subdivison must be expanded from 1/5 to 2*(1/6)=1/3, while the remaining 4 rectangles must shrink from area of 1/5 to 1/6.

In general terms, operation of changing subdivision of n into n+1 must expand the area of one rectangle from 1/n to 2/(n+1) and shrink others from 1/n to 1/(n+1).

I did not see anywhere in this topic, HOW the subdivison operation changes dimensions of individual rectangles. I gave an example of ambiguity of subdivision in my post 87. (I mistakingly refered to it as post 89 in few posts above.)

Once we decide exactly how the dimensions of rectangles are changed, we could go ahead with a proof or rationality. It could be based on the fact that a rational number can only be a sum of other rational numbers.

[Guest]

That line of reasoning does not take into account the OP requirement that all subdividing rectangles must be of equal area.

For example: Suppose we have an instance of divison of a unit square into 5 equal area rectangles. The area of each rectangle is 1/5. Then we designate one of the small rectangles for further subdivision into two.

Oh thats not what I meant by subdivision. If I understand correctly you are trying to generate valid patterns for n=6 from the patterns obtained for n=5 by subdividing the inner rectangles of the patterns for n=5. I am not sure if that will generate all the patterns for n=6.

By subdivision, I meant u start all over from the beginning. that is

1) you start with an initial square.

2)Then you draw a line at some point dividing the square into two smaller rectangles.

3) You then try subdividing one of those rectangles two obtain still smaller rectangles.

4) you repeat step 3 n-1 times where n is the total number of rectangles required.

This was the algorithm I used for my program. Only thing is I had to choose which rectangle I was going to divide next and at what point on the rectangle I was going to make the division. My previous post was to prove that when I needed to choose a point to divide the rectangle I could safely eliminate irrational points as dividing at an irrational point would never lead to a valid pattern.

[Prime]

By subdivision, I meant u start all over from the beginning. ...

OK, so if I understand it right, the algorithm cuts 1/n area from the remaining area on each division. Then, of course, you are guaranteed rational dimensions. With every cut, the algorithm reuses one of the existing rectangle sides, which is of a rational length. And since 1/n is a rational number it can be obtianed by multiplication of two rational numbers, or two irrational, but not the mix. So if one side is rational, the other one has to be also.

What I don't understand, how that algorithm would produce all possible divisions? For example, a square divided into 4 squares as shown below?

If algoritm cuts off 1/4 of the total area on each division, and then leaves that correctly sized cut untouched by consecutive divisions, it would never achieve the arrangement as above.

On the other hand, if the algorithm cuts the area into equal (or whatever other relation) parts on each consecutive step, then we are back to what I am pointing out -- the ambiguity (not uniquely defined operation.)

Say, algorithm first drew the AB line through the middle. On the next step it drew CO line down the middle. Then it would have to change the coordinates of the AB line -- slide it down. Then after drawing DO line, it would have to change the position of the AB again. My illustration in post 87 refers to your algorithm on its n-th step.

Does your algorithm actually verify that each rectangle has an area of 1/n and calculate the exact dimensions of all rectangles, or does it simply subdivide the square?

Edited September 10, 2008 by Prime

[Guest]

OK, so if I understand it right, the algorithm cuts 1/n area from the remaining area on each division. Then, of course, you are guaranteed rational dimensions. With every cut, the algorithm reuses one of the existing rectangle sides, which is of a rational length. And since 1/n is a rational number it can be obtianed by multiplication of two rational numbers, or two irrational, but not the mix. So if one side is rational, the other one has to be also.

No I dont cut at 1/n. I cut at those points such that the area of two rectangles obtained are such that the area of one is a multiple of the other. And for given n, I make only n-1 cuts. Heres a diagram

[Prime]

No I dont cut at 1/n. I cut at those points such that the area of two rectangles obtained are such that the area of one is a multiple of the other. And for given n, I make only n-1 cuts.

I am still unclear, how does the algorithm choose the coordinates of each cut? Does it decide up front how many smaller rectangles each larger rectangle is going to have? That seems to lead to many hidden duplicate solutions. Does your program actually calculate the dimensions of the rectangles in each set?

Edited September 10, 2008 by Prime

[Guest]

I am still unclear, how does the algorithm choose the coordinates of each cut? Does it decide up front how many smaller rectangles each larger rectangle is going to have? That seems to lead to many hidden duplicate solutions. Does your program actually calculate the dimensions of the rectangles in each set?

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. It becomes difficult to find solutions by hand for n starting from as small as 7. It also helps validate any claims of a solution made,

Because someone may find a function that generates the the correct values for n only upto a certain number. It becomes difficult to show that the function does not produce the correct value for n starting from a certain number manually.

Yes the program actually computes the dimesnions of the rectangles. Without that information it wont be able to weed out duplicates.