[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]

(Blah Blah Blah) ... 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.... (Blah Blah Blah)

stop imagining...

[Guest]

IN RESPONSE TO THE NEW f(5) SOlUTION

Ouch! I wish you hadn't done that - perhaps the OP would rule it out, although the problem description would seem to allow it.

The OP does not rule it out. But, it should.

I am (after the fact) amending the OP so that only RATIONAL solutions to the lengths of the sides of our rectangles can be considered.

That being said, if we ever solve the rational explanation, I would be interested in exploring the irrational ones too.

Hopefully, this decision is rational.

[Guest]

After some thought, I came up with another arrangement for 5 rectangles:

The square in the middle is roughly 0.447 by 0.447 on a unit square. (1/sqrt(5) by 1/sqrt(5)) I do believe this is the only arrangement of its kind for 5 rectangles. This brings f(5) up to 12.

All I have to say is ... AWESOME thinking!

If you read my previous post, I am going to exclude these types of solutions, at least for now, because they open up our can of worms from acre size to square mile size.

That being said, if we ever solve the rational solutions, I'd love to try to solve this with these solutions too.

And, to add on, your square is (1/root 5 by 1/root 5), and your four rectangles are (5-root 5)/10 by (5+root 5)/10.

For anyone who wants to keep thinking of these, my question would be, do these only occur when n = k² + 1 for values of k > 1, or do they occur for other values of n as well?

[HoustonHokie]

graphic to go with my last post showing central square solutions for n=6,7,8 - I think this confirms the exclusion of irrational solutions for now.

rhapsodize, I think this confirms that these type of solutions occur for all n>=k^2 + 1 for values of k>1, or simply for n>=5. The problem simply becomes more complex each time k increases.

Edited June 4, 2008 by HoustonHokie

[Guest]

graphic to go with my last post showing central square solutions for n=6,7,8 - I think this confirms the exclusion of irrational solutions for now.

rhapsodize, I think this confirms that these type of solutions occur for all n>=k^2 + 1 for values of k>1, or simply for n>=5. The problem simply becomes more complex each time k increases.

Yeah, I see what you're saying.

Now looking at it more, it looks like to me that the general pattern of them gets created for n = 4k + 1, and then uses previous iterations of our f(n) sequence starting with n = 1 in the "middle". In other words, your extra pictures for f(8) can be expanded the same way for f(9), but then there'd be more, as you could create a double "border" with a square in the middle, and you could create a "border" of 8 rectangles where each one takes up about half the area of the new f(5) picture.

All in all, probably still somewhat predictable, but it makes sense to solve the rational rectangles first. All of these pictures are irrational, literally with their lengths, but I guess not figuratively (gosh, I never get tired of "irrational" math puns).

[HoustonHokie]

my last irrational post for a while

Actually, the form of the irrational solutions begins at n>=k^2 for k>1 instead of n>=k^2 + 1. It just so happens that root 4 is not irrational. The level of complexity increases again at n=9=3^2 not at n=10=3^2+1. See below for n=9:

I think the four-square solution to f(4) and the nine-square solution to f(9) are examples of irrational solutions that migrate from the irrational pattern to the rational one and will not fit the general rational solution we are looking for. Maybe we should try to develop a function that ignores those solutions (and their children for higher values of n) and come back to them later. So:

f(2) = 1

f(3) = 2

f(4) = 4

f(5) = 10

f(6) = 24

Does that make sense to anyone? Or am I just being irrational?

[HoustonHokie]

Whoops - you're right. Complexity increases at multiples of 4, not square numbers.

[Guest]

my last irrational post for a while

Actually, the form of the irrational solutions begins at n>=k^2 for k>1 instead of n>=k^2 + 1. It just so happens that root 4 is not irrational. The level of complexity increases again at n=9=3^2 not at n=10=3^2+1. See below for n=9:

I think the four-square solution to f(4) and the nine-square solution to f(9) are examples of irrational solutions that migrate from the irrational pattern to the rational one and will not fit the general rational solution we are looking for. Maybe we should try to develop a function that ignores those solutions (and their children for higher values of n) and come back to them later. So:

f(2) = 1

f(3) = 2

f(4) = 4

f(5) = 10

f(6) = 24

Does that make sense to anyone? Or am I just being irrational?

The original OP says that the rectangles should be obtained by dividing the square and the other rectangles so created. Considering that , the central square solutions do not seem valid as the rectangles cannot be obtained by actually subdividing the original square or the rectangles obtained. What do you think?

[Guest]

The original OP says that the rectangles should be obtained by dividing the square and the other rectangles so created. Considering that , the central square solutions do not seem valid as the rectangles cannot be obtained by actually subdividing the original square or the rectangles obtained. What do you think?

The OP doesn't actually say that. Subdividing rectangles was used as a way of showing how to get f(3)=2. Whether or not the arrangements have to contain only rectangles at any given point while drawing them isn't specified.

[Guest]

The OP doesn't actually say that. Subdividing rectangles was used as a way of showing how to get f(3)=2. Whether or not the arrangements have to contain only rectangles at any given point while drawing them isn't specified.

No, it doesn't, but I sure wish it did!

Again, I'd love to tackle the irrational additions we're discussing here, but I'd hope I or someone else can have a solution to find all rational division solutions to the problem first, and then we can come back and tackle these other ones.

[HoustonHokie]

The original OP says that the rectangles should be obtained by dividing the square and the other rectangles so created. Considering that , the central square solutions do not seem valid as the rectangles cannot be obtained by actually subdividing the original square or the rectangles obtained. What do you think?

Agreed. At least for now - maybe we'll tackle the central square stuff later. For right now, the rational solutions are difficult enough.

That being said, I might have found a pattern that holds for at least n<=6. I tried counting the number of solutions that contained at least one unit rectangle (ignoring irrational solutions) and got the following:

f(n) = # with unit rect + # w/o unit rect

f(2) = 1 + 0 = 1

f(3) = 2 + 0 = 2

f(4) = 4 + 1 = 5

f(5) = 9 + 2 = 11

f(6) = 22 + 5 = 27

At first, I was puzzled because an earlier post had stipulated that the number of solutions with at least one unit rectangle was 2*f(n-1), but that didn't hold true for f(5). Then I realized I was back to rectangles . The number of solutions with at least one unit rectangle is rect(n-1). I'm having a hard time defining rect(n) mathematically, but I can show graphically that rect(n) = 2*sq(n), except for n=4, where it's 9 instead of 10. I know it has something to do with the fact that 4 is a square number itself, but I can't get it out mathematically. I think that there is a geometric explanation for this first term being rect(n-1), but I'm having difficulty being eloquent about it. Basically, it's that every unit rectangle solution for n includes the unit rectangle and another rectangle which has been divided into n-1 parts.

I don't have a good geometric reason for the second term, but it is starting to have a very familiar pattern: sq(n-2). I think that might have to do with the fact that the remaining solutions all have a pair of rectangles of dimension L/2 x 2L/n. But I'm not sure how to justify it.

I'm not sure if a third term would be needed for n=9 where the next square number is encountered to handle the fact that I think will exist unique solutions with three rectangles of dimension L/3 x 3L/n.

Carrying out my guesses to n=8, I get:

f(7) = 54 + 11 = 65

f(8) = 130 + 22 = 152

Of course, I'm not sure these are right, and I'm not going to even try to go any further before I let somebody else tear this apart.

[HoustonHokie]

Well, since no one's told me any different, I think I'm going to continue my line of reasoning and present a comprehensive solution for the rational portion of this problem.

I propose that the best way to find the number of methods for subdividing a square into equal area rectangles, all of whose sides have lengths which can be expressed rationally, is to take the sum of all solutions including a unit rectangle (L x L/n) and all unique solutions including two half-unit rectangles (L/2 x 2L/n), three third-unit rectangles (L/3 x 3L/n), four fourth-unit rectangles (L/4 x 4L/n), etc.

In order to do so, I define two functions: square(n) and rect(n), where:

square(n) is the number of methods for subdividing a square into equal area rectangles, all of whose sides have lengths which can be expressed rationally (the target function)

rect(n) is the number of methods for subdividing a rectangle into equal area rectangles, all of whose sides have lengths which can be expressed rationally.

In general, rect(n) = 2*square(n), except for values of n which can be defined as k^2, where k is a non-negative integer. For values of n=k^2, rect(n) = 2*square(n) - 1.

Further, I will define square(2) = rect(1) = 1.

Then, it follows that:

for n<=k^2, square(n) = rect(n-1) + [square(n-(2^2-2))+square(n-(3^2-2))+...+square(n-((k-1)^2-2))]

Working out the problem:

square(2) = 1 (by definition)

square(3) = rect(2) = 2*square(2) = 2*1 = 2

square(4) = rect(3) + square(2) = 2*2 + 1 = 5

square(5) = rect(4) + square(3) = 2*5-1 + 2 = 11

square(6) = rect(5) + square(4) = 2*11 + 5 = 27

square(7) = rect(6) + square(5) = 2*27 + 11 = 65

square(8) = rect(7) + square(6) = 2*65 + 27 = 157

square(9) = rect(8) + square(7) + square(2) = 157*2 + 65 + 1 = 380

square(10) = rect(9) + square(8) + square(3) = 380*2 + 157 + 2 = 918

When the next term is added at square(16), there are 183,755 ways to divide the square

square(25) = 520,157,803

square(36) = 8.612 E+12

Needless to say, we won't be drawing out the higher solutions to confirm!

Here's the geometry behind my solution:

For the unit rectangle portion of the function, what you're really doing is making a square by adding a unit rectangle to all possible subdivisions of another rectangle into n-1 equal area rectangles. For every other portion of the solution (half-unit rectangles, third-unit rectangles, etc.), the same is true that a portion of the overall solution is, for example, 2 half-unit rectangles with every possible subdivision of another rectangle into n-2 equal area rectangles. The problem is that this double-counts all the solutions which already have at least one unit rectangle. The way to avoid double-counting is by using square(n-2) instead of rect(n-2) [or square(n-7) instead of rect(n-7), and so on].

Graphically, I can illustrate that the unique solutions for rect(n) look like two sets of the unique solutions for square(n) - one oriented vertically, and the other oriented horizontally. (I'll work on that picture later and upload so you can see what I mean). For values of n where n=k^2, the horizontal and vertical orientations generate the same picture, and that is why rect(n) in these cases = 2*square(n)-1 instead of 2*square(n).

Every time that n=k^2, we add another set of possible solutions, which is why we need another term in the equation. I have difficulty explaining in words why this is (maybe I'll edit the post later if I can come up with the right words), but it has to do with being able to get unique solutions by dividing the square in half, thirds, fourths, etc. and putting all the lower level rectangles into each of the half-squares, third-squares, fourth-squares, etc. Like I said, the words are not working for me right now!

Taking a guess at the irrational solution, which is next (I guess), I think all that's necessary is to add another term to the equation for all n>4. That term would be square(n-4). I think this is because the central square contains all possible subdivisions of a square into n-4 equal area rectangles, and outside the central square are 4 other rectangles. I may have to make sure that works at n=8 and that we don't need to have another term that gets added when n=k*4.

Okay, I'm done. Tear holes!

Edited June 5, 2008 by HoustonHokie

[Guest]

Carrying out my guesses to n=8, I get:

f(7) = 54 + 11 = 65

f(8) = 130 + 22 = 152

I believe you're on the right track. However, I think you made a typo, and mean: f(8) = 130 + 27 = 157

I've been thinking about: f(n) = 2f(n-1) + f(n-2), but as you suggest, I think we need to subtract 1 for (n-1) being a perfect square. Not sure how to write that.

Perhaps...

f(2) = 1

f(3) = 2

for int((n-1)^0.5)=(n-1)^0.5 : f(n) = 2f(n-1) - 1 + f(n-2)

otherwise : f(n) = 2f(n-1) + f(n-2)

I'm also not yet convinced that this holds for n>6; there may be further terms required as more combinations of the 'unit rectangles' become available.

[Guest]

Oops! You posted while I was composing my reply!

[HoustonHokie]

Every time that n=k^2, we add another set of possible solutions, which is why we need another term in the equation. I have difficulty explaining in words why this is (maybe I'll edit the post later if I can come up with the right words), but it has to do with being able to get unique solutions by dividing the square in half, thirds, fourths, etc. and putting all the lower level rectangles into each of the half-squares, third-squares, fourth-squares, etc. Like I said, the words are not working for me right now!

That paragraph made no sense to me, even when I was writing it!

This is what I mean:

Every time that n=k^2, we add another set of possible solutions, which is why we need another term in the equation. The reason is that the first term describes all solutions that have at least one unit rectangle, but there are solutions which do not have any unit rectangles. For n = 4, the four-square solution is a good example. For n = 5, a solution with 2 half-unit rectangles and 3 third-unit rectangles is another example. There are no unit rectangles in either.

The solutions we're looking for then correspond to the cases where there are k k-th unit rectangles (or k-1 [k-1]th unit rectangles, etc.) on one side of a line drawn across the square with all possible subdivisions of a rectangle into n-k equal area rectangles on the other side. These solutions do all exist in the set, but there are a good number of duplicates because many of them contain unit rectangles (or [k-1]th unit rectangles, etc.), which have already been counted. It turns out that square(n) is all of the unique solutions to rect(n) in one orientation (horizontal or vertical). One orientation will give a solution with a unit rectangle and the other will not, and the solution without the unit rectangle is the one you need for the k-th unit rectangle solutions.

A picture of this can be seen where it occurs the first time, at n=4. The unit rectangle solutions for n=4 include a unit rectangle of dimension L x L/4 with all the possible subdivisions of the remaining L x 3L/4 rectangle into 3 equal area rectangles. Looking for half-unit rectangles, we see that there are two of them, but one has a unit rectangle already and the other does not. The solution without the unit rectangle is unique, and corresponds graphically to the unique solution of rect(2), which is square(2), so there are only square(2) = 1 additional unique solutions with half-unit rectangles. See the picture for the real graphical explanation.

After understanding the first solution, the extrapolation to higher values of n and k becomes more obvious. Hopefully this is a better explanation!

[HoustonHokie]

I'm also not yet convinced that this holds for n>6; there may be further terms required as more combinations of the 'unit rectangles' become available.

I think you're right. I can envision a solution for n=7 consisting of 3 third-unit rectangles and 4 fourth-unit rectangles. That wouldn't be accounted for in my function, because it contains no unit or half-unit rectangles and I didn't introduce third-unit rectangles until n=9. Any guesses on an elegant description of this? I'm about mathed-out right now - my brain hurts!

[HoustonHokie]

Graphically, I can illustrate that the unique solutions for rect(n) look like two sets of the unique solutions for square(n) - one oriented vertically, and the other oriented horizontally. (I'll work on that picture later and upload so you can see what I mean). For values of n where n=k^2, the horizontal and vertical orientations generate the same picture, and that is why rect(n) in these cases = 2*square(n)-1 instead of 2*square(n).

The promised picture:

[Guest]

I think you're right. I can envision a solution for n=7 consisting of 3 third-unit rectangles and 4 fourth-unit rectangles. That wouldn't be accounted for in my function, because it contains no unit or half-unit rectangles and I didn't introduce third-unit rectangles until n=9. Any guesses on an elegant description of this? I'm about mathed-out right now - my brain hurts!

Mine too. I can see more awkard configurations appearing as n increases. For example, for n=9, one result is to divide into 9 squares; four of these form a larger square that can be divided according to f(4). f(16) is even worse!

[Guest]

I have written a program that uses brute force technique to generate the solutions for a given n. The program is horribly inefficient as of now (it takes a while for n=5 and did not get it to complete for n =6 ).

I will have to optimize it when I get time. I have attched the program as a text file. Its written in java so if anyone interested can help me get this optimized.

The program basically outputs a series of solutions for a given n. For each solution it ouptuts the coordinates of the divided rectangles. the program does not take the central square solutions into consideration though.

the output for n= 3,4 and 5 are as follows.

n=3

--------------------------------

[(4,0) - (6,6)]

[(2,0) - (4,6)]

[(0,0) - (2,6)]

--------------------------------

[(2,3) - (6,6)]

[(2,0) - (6,3)]

[(0,0) - (2,6)]

--------------------------------

Total Solutions 2

n=4

--------------------------------

[(12,12) - (24,24)]

[(12,0) - (24,12)]

[(0,12) - (12,24)]

[(0,0) - (12,12)]

--------------------------------

[(6,16) - (24,24)]

[(6,8) - (24,16)]

[(6,0) - (24,8)]

[(0,0) - (6,24)]

--------------------------------

[(15,8) - (24,24)]

[(6,8) - (15,24)]

[(6,0) - (24,8)]

[(0,0) - (6,24)]

--------------------------------

[(18,0) - (24,24)]

[(12,0) - (18,24)]

[(6,0) - (12,24)]

[(0,0) - (6,24)]

--------------------------------

[(12,12) - (24,24)]

[(12,0) - (24,12)]

[(6,0) - (12,24)]

[(0,0) - (6,24)]

--------------------------------

Total Solutions 5

n=5

--------------------------------

[(96,0) - (120,120)]

[(0,90) - (96,120)]

[(0,60) - (96,90)]

[(0,30) - (96,60)]

[(0,0) - (96,30)]

--------------------------------

[(96,0) - (120,120)]

[(0,90) - (96,120)]

[(0,60) - (96,90)]

[(48,0) - (96,60)]

[(0,0) - (48,60)]

--------------------------------

[(96,0) - (120,120)]

[(0,90) - (96,120)]

[(32,45) - (96,90)]

[(32,0) - (96,45)]

[(0,0) - (32,90)]

--------------------------------

[(96,0) - (120,120)]

[(0,90) - (96,120)]

[(64,0) - (96,90)]

[(32,0) - (64,90)]

[(0,0) - (32,90)]

--------------------------------

[(96,0) - (120,120)]

[(48,60) - (96,120)]

[(48,0) - (96,60)]

[(0,60) - (48,120)]

[(0,0) - (48,60)]

--------------------------------

[(84,40) - (120,120)]

[(48,40) - (84,120)]

[(48,0) - (120,40)]

[(0,60) - (48,120)]

[(0,0) - (48,60)]

--------------------------------

[(48,80) - (120,120)]

[(48,40) - (120,80)]

[(48,0) - (120,40)]

[(0,60) - (48,120)]

[(0,0) - (48,60)]

--------------------------------

[(96,0) - (120,120)]

[(72,0) - (96,120)]

[(48,0) - (72,120)]

[(24,0) - (48,120)]

[(0,0) - (24,120)]

--------------------------------

[(96,0) - (120,120)]

[(48,60) - (96,120)]

[(48,0) - (96,60)]

[(24,0) - (48,120)]

[(0,0) - (24,120)]

--------------------------------

[(84,40) - (120,120)]

[(48,40) - (84,120)]

[(48,0) - (120,40)]

[(24,0) - (48,120)]

[(0,0) - (24,120)]

--------------------------------

[(48,80) - (120,120)]

[(48,40) - (120,80)]

[(48,0) - (120,40)]

[(24,0) - (48,120)]

[(0,0) - (24,120)]

--------------------------------

Total Solutions 11

I have not yet got a chance to validate for n=5, but I think it should be correct.

SquareDivider.txt

[HoustonHokie]

I have written a program that uses brute force technique to generate the solutions for a given n. The program is horribly inefficient as of now (it takes a while for n=5 and did not get it to complete for n =6 ).

I will have to optimize it when I get time. I have attched the program as a text file. Its written in java so if anyone interested can help me get this optimized.

I have not yet got a chance to validate for n=5, but I think it should be correct.

Nice... I use CADD a lot, so having the coordinates from your program will make it easy for me to get a visual check on your output. I won't be able to work on it until Monday (at the earliest), so maybe the code will be a little more refined by then.

[Guest]

I think I have the formula:

2^(n-1)-(n-1)

[Guest]

I think I have the formula:

2^(n-1)-(n-1)

This doesn't work because you get f(5)=2^4-4=12 and f(6)=2^5-5=27. You f(5) includes the "square in the middle" arrangement but your f(6) doesn't include the arrangement of one "unit rectangle" and then the same "square in the middle" arrangement in the remaining space (even though it's no longer a square in the middle).

[Guest]

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

[Guest]

I agree. I edited the picture and it looks like this. Now f(6) = 29.

Arent these two solutions the same? its just the orientation of the rectangles that are different

[Guest]

Arent these two solutions the same? its just the orientation of the rectangles that are different

No, I think they are different sizes, too.