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

mathematically, i calculated that there are 59 iterations for 7 divisions, but i have no formula, i simply organized it much the same way that flowstoneknight organized the drawings of 6 divisions, just without drawing them

the difficulty is that when you higher than seven divisions, the formula begins to rely on more lower level recursions i.e. n-3,n-4 etc. multiple times. the trick is calculating which lower level recursions and how many times.

[HoustonHokie]

Another difficulty, in addition to the repeating issue, is that dividing a rectangle isn't necessarily the same as dividing a square. For instance, dividing a square into two sections yields only one unique solution. Dividing any other rectangle into 2 parts gives 2 solutions - cutting it the long way and the short way. This makes it more complicated, because you can't reduce it recursively to some rectangle and then say, "this rectangle must be subdivided n times, and I've solved the problem for dividing a square n times, so now I can just multiply that number by the number of ways of getting down to that n-division."

Long story short, I have no idea.

Chuck, I think you're on to something that I started to see yesterday. If you'll see my last post, I postulated that rect(n)=2*square(n), for precisely the reason that you mentioned - you get one solution for dividing it lengthwise and another for dividing it widthwise, but I think the solutions should be equal in terms of the actual number of different solutions. I'm trying to confirm that you'd never end up with the same solution if your initial cuts were along two axes of different lengths, but there might be some specific geometric proportions of the rectangle where that occurs (not that we'd necessarily find them in this problem - that's the next step if I find proportions that give the same results).

[Guest]

Hi. I have been following along.... and still have no idea!! Thanks Flowstoneknight for drawing out the combinations for 6 that really helped. But I think you may have missed one. You got all the combinations with the first two rectangles split horizontally not vertically (Your last line of pics) but I think there is one new way to make a combination with the first three rectangles split horizontally (you need a new line) and the others in one of the f(3) combinations. Am I right? I think the formula is in here somehow.... feels like it is on the tip of my tongue but not quite there. I have to go get kids to school, but will be here later. Something along the lines of 2^(n-2) + f(n-1) minus the repeats (there must be a pattern to this also) and plus one for all the even (or is it odd) n's.

[HoustonHokie]

Hi. I have been following along.... and still have no idea!! Thanks Flowstoneknight for drawing out the combinations for 6 that really helped. But I think you may have missed one. You got all the combinations with the first two rectangles split horizontally not vertically (Your last line of pics) but I think there is one new way to make a combination with the first three rectangles split horizontally (you need a new line) and the others in one of the f(3) combinations. Am I right? I think the formula is in here somehow.... feels like it is on the tip of my tongue but not quite there. I have to go get kids to school, but will be here later. Something along the lines of 2^(n-2) + f(n-1) minus the repeats (there must be a pattern to this also) and plus one for all the even (or is it odd) n's.

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

[HoustonHokie]

Well, I might venture a new guess, although I'm unsure how to express it eloquently. From what I can see, if you are trying to come up with n divisions, you end up breaking the original square into predictable groupings of 2 smaller rectangles, which have to be further divided. I still postulate that rect(n)=2*square(n), and based on that, here's what I'm seeing:

for 7 divisions: 1 rectangle divided 4 times, 1 rectangle divided 3 times

1 rectangle divided 5 times, 1 rectangle divided 2 times

1 rectangle divided 6 times, 1 rectangle divided 1 time

for 6 divisions: 1 rectangle divided 3 times, 1 rectangle divided 3 times

1 rectangle divided 4 times, 1 rectangle divided 2 times

1 rectangle divided 5 times, 1 rectangle divided 1 time

for 5 divisions: 1 rectangle divided 3 times, 1 rectangle divided 2 times

1 rectangle divided 4 times, 1 rectangle divided 1 time

for 4 divisions: 1 rectangle divided 2 times, 1 rectangle divided 2 times

1 rectangle divided 3 times, 1 rectangle divided 1 time

Then, if rect(n)=2*square(n), I think you can express:

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

square(5)=rect(4)+rect(3)-3 =10+4-3=11

square(6)=rect(5)+rect(4)+rect(3)-5=22+10+4-5=29

for square(7), the answer would be 83 - not sure I want to draw that out to confirm!

As far as an expression goes, I guess this might do:

square(n)=rect(n-1)+rect(n-2)+...+rect(n/2)-[(n-3)*2-1]

where rect(n) = 2*square(n)

Of course, rect(n/2) is only defined for even values of n, so the recursion would have to stop with rect(n/2+0.5) for odd numbers. I can't figure out if my last term is correct - the subtraction of an ever-increasing odd number - because I can't understand a geometric reason for it. Also, the formula doesn't work for square(3), which makes me more suspicious of that term. But the geometry seems good to me for the recursion.

And if I'm wrong, well - I've been wrong before. I think the last time was yesterday!

[Guest]

Sorry Hokie, only partially right with your new picture.

The picture you put up has four new solutions. However, of the 4 new solutions you put up, I initially see that two of them are exact duplicates of the other two. Take a look, and you'll see what I mean. The top right new solution is identical to the bottom left new solution except for the order the boxes appear in. Same with the other two.

As of right now, I think that f(6) = 27 unless anyone sees other duplicates.

[HoustonHokie]

Well, I guess the last time I was wrong was just a few minutes ago...

[HoustonHokie]

Substituting in the corrected value of square(6)=27, I've got another possible solution:

square(n)=rect(n-1)+rect(n-2)+...+rect(n/2)-3^(n-4)

where rect(n) = 2*square(n)

That would give square(7)=59, which is the solution The Giant Panda came up with. Of course, the last term still gives me the heebie-jeebies. The problem is that it is so difficult to validate any solution without drawing it out for the next few values of n - just discovering patterns (which is a large part of what I've been doing) doesn't necessarily work more than a few iterations out. I wish I could come up with the geometric proof. It's out there somewhere...

[Guest]

Substituting in the corrected value of square(6)=27, I've got another possible solution:

square(n)=rect(n-1)+rect(n-2)+...+rect(n/2)-3^(n-4)

where rect(n) = 2*square(n)

That would give square(7)=59, which is the solution The Giant Panda came up with. Of course, the last term still gives me the heebie-jeebies. The problem is that it is so difficult to validate any solution without drawing it out for the next few values of n - just discovering patterns (which is a large part of what I've been doing) doesn't necessarily work more than a few iterations out. I wish I could come up with the geometric proof. It's out there somewhere...

I must be missing something from what you're thinking.

For square(7), according to your formula, it would equal 2*square(6) + 2*square(5) + 2*square(4) + 2*square(3) + 2*square(2) + 2*square(1) + 2*square(4) - 27. Not only do I get 77 for that, but it doesn't match up with the previous terms.

Instead of adding the second to last term, if I subtract it, then it matches up with all the previous terms, but I get 57 instead of 59.

Am I missing something or is there a mistake on your end with = 59? Either way, the formula is well thought out.

[HoustonHokie]

I must be missing something from what you're thinking.

For square(7), according to your formula, it would equal 2*square(6) + 2*square(5) + 2*square(4) + 2*square(3) + 2*square(2) + 2*square(1) + 2*square(4) - 27. Not only do I get 77 for that, but it doesn't match up with the previous terms.

Instead of adding the second to last term, if I subtract it, then it matches up with all the previous terms, but I get 57 instead of 59.

Am I missing something or is there a mistake on your end with = 59? Either way, the formula is well thought out.

What you're missing is that you have to stop recursing when you hit 2*square(n/2) (or for odd numbers, 2*square(n/2+0.5)). I included that qualifier in my previously unsuccessful formula, but failed to restate it last time. The reason is you stop recursing, I think, is that you begin double counting because, for example, rectangles of 5 and 2 are the same as rectangles of 2 and 5. So:

square(7) = 2*square(6) + 2*square(5) + 2*square(4) - 27 = 2(27+11+5) - 27 = 59.

I'm still not sure that 59 is correct though - no one's drawn it out.

For now, I'm thinking about other means to this same end - I've been looking at the possible side lengths and at whether I can recurse all the way down to square(1) in some logical fashion. Nothing so far... I'm hoping the recursion will work, though, because it might aid my drawing process when I go to prove that it works for square(7) or higher.

[Guest]

What you're missing is that you have to stop recursing when you hit 2*square(n/2) (or for odd numbers, 2*square(n/2+0.5)). I included that qualifier in my previously unsuccessful formula, but failed to restate it last time. The reason is you stop recursing, I think, is that you begin double counting because, for example, rectangles of 5 and 2 are the same as rectangles of 2 and 5. So:

square(7) = 2*square(6) + 2*square(5) + 2*square(4) - 27 = 2(27+11+5) - 27 = 59.

I'm still not sure that 59 is correct though - no one's drawn it out.

For now, I'm thinking about other means to this same end - I've been looking at the possible side lengths and at whether I can recurse all the way down to square(1) in some logical fashion. Nothing so far... I'm hoping the recursion will work, though, because it might aid my drawing process when I go to prove that it works for square(7) or higher.

Now I understand.

But your answer can't be correct.

If you take yours out to square(11), you will get square(11) = -1165.

The 3 to the power of term gets WAY too big too quickly.

[Guest]

Some thoughts on a recursive formula.

I believe the answer is f(n) = 2*f(n-1) + (some extra cases) - (minus 0 for most cases, but minus 1 for when n-1 is a square number).

For example, when we found f(6) = 27, that can be found by taking 11 * 2 = 22, plus 5 cases. If you look at that picture, 22 of the cases has at least one rectangle that is a full unit long, and only 5 cases (all at the bottom) without any "unit rectangles".

So, it's very easy to find many of the solutions, but finding the extra solutions that do not contain "unit rectangles" is the problem.

Also, while most times you can just double the previous term as a starting point, it does not work for n = 2 and n = 5, where there is one less case than you'd expect. This seems to me because if you take the case where all areas are perfect square (n = 1 with 1 square, n = 4 with 4 squares arranged 2x2), there is only one unique way to add a unit rectangle onto a similar picture, and not 2. I anticipate for the next few terms, that taking 2*f(n-1) will give you a starting point, but you'll have to subtract 1 at n = 10.

Hopefully, this is clear enough to have people build on it.

[Guest]

As a prediction, I'm getting 75 for f(7), and I'm starting to get confident I can predict beyond f(7) and have a semi-generalized solution. I'll try drawing out f(7) soon and see if I or anyone gets something else.

[Guest]

Ok, so I'm not ready to say I've got this for sure, but I think I'm close.

Any natural number n (where n>2) can be written as the sum of smaller integers.

For example, the number 5 can be written the following different ways:

---1+1+1+1+1

---1+1+1+2

---1+1+3

---1+4

---1+2+2

---2+3

This way of writing actually corresponds visually to the pictures and how they can be found recursively. I can't figure out the right words to explain why it does at the moment, but it does, and I'll try to post it when I find them.

To find the number of solutions (with only a little overcounting), all you have to do is take the recursive functions for each of the possibilities above and MULTIPLY for that solution, then ADD up all the results.

We've already found f(1) = 1, f(2) = 1, f(3) = 2, and f(4) = 5, so...

In other words:

---f(1)*f(1)*f(1)*f(1)*f(1) = 1*1*1*1*1 = 1

---f(1)*f(1)*f(1)*f(2) = 1*1*1*1 = 1

---f(1)*f(1)*f(3) = 1*1*2 = 2

---f(1)*f(4) = 1*5 = 5

---f(1)*f(2)*f(2) = 1*1*1 = 1

---f(2)*f(3) = 1*2 = 2

The sum of 1+1+2+5+1+2 = 12. There is one overcounting, which is the f(1)*f(2)*f(2) case visually corresponds to one of the five f(1)*f(4) cases.

This works with all cases so far. The overcounting can be accounted for visually and may be able to accounted for mathematically. I'm working on the overcounting mathematically, and when it occurs (I think I understand why, but again, am struggling to find the words for it).

[Guest]

f(6) case:

1+1+1+1+1+1 ==> f(1)*f(1)*f(1)*f(1)*f(1)*f(1) = 1

1+1+1+1+2 ==> f(1)*f(1)*f(1)*f(1)*f(2) = 1

1+1+1+3 ==> f(1)*f(1)*f(1)*f(3) = 2

1+1+4 ==> f(1)*f(1)*f(4) = 5

1+5 ==> f(1)*f(5) = 11

2+2+2 ==> f(2)*f(2)*f(2) = 1 [but all of these are double-counted below]

3+3 ==> f(3)*f(3) = 4 [but all of these are double-counted below; in fact, 2 of these 4 cases are identical already]

2+4 ==> f(2)*f(4) = 5 [this contains all of both of the above scenarios double-counting ... as all cases here AND the 2 immediately above can be drawn with 2 rectangles that are 1/2 unit by 1/3 unit along with 4 more rectangles]

1+1+2+5+11+0+0+5 = 27

Again, I'm still working on how to predict how things will be double-counted. My prediction of 75 for f(7) is based on this, but now I'm not sure.

[Guest]

Any natural number n (where n>2) can be written as the sum of smaller integers.

I noticed that also, but couldn't put it into words either so left it unsaid. You said it with less words that it would have taken me!! There has to be something to it though. Hmmmm.....

[HoustonHokie]

I think essentially what we are seeing is a combination, or a sum of combinations, which might be the mathematical means to express the solution. Working on it...

[Guest]

Here is what I get:

1-n+2^(n-1)

so for n=1 we get 1-1+1 = 1

n=2 1-2+2 = 1

n=3 1-3+4 = 2

n=4 1-4+8 = 5

n=5 1-5+16 = 12

n=6 1-6+32 = 27

fits all the ones you guys have drawn. I do see one potential arrangement missing from the n=5 drawings.

[Guest]

I was wondering if there is a polynomial time algorithm that would find the solution to the problem.

I have heard of problems such as the 0/1 knapsack problem, hamiltonian cycle etc that do not have polynomial time solutions.

I was thinking of writing a program that would generate the number of solutions for given n(1,2,3, etc) by using brute force (ie trying all possible combinations and filtering out duplicates and invalid solutions.) and seeing if there is a pattern in the sequence. Has anyone done that already?

Edited June 3, 2008 by vimil

[HoustonHokie]

I was thinking of writing a program that would generate the number of solutions for given n(1,2,3, etc) by using brute force (ie trying all possible combinations and filtering out duplicates and invalid solutions.) and seeing if there is a pattern in the sequence. Has anyone done that already?

I would love to see it done - problem is we don't have a mathematical means to filter out duplicates yet, so I'm not sure how the program would work.

I do see one potential arrangement missing from the n=5 drawings.

If that's the case, then we're wrong on n=6 as well, because all the n=5 cases are used in the n=6 drawings. We'd have to add at least one more solution to n=6 to account for the new n=5 solution you see. If it's unique, can you post an image?

My thoughts on combinations have come to a screeching halt - I keep running into the same duplicate filter issues we've been dealing with. What a good puzzle - I just hope it actually has an elegant solution.

[Guest]

So, all the listings of sums of lesser intergers that contain a 1 happens to be equal to all the previous terms.

So, when we're looking for the "extra" terms, we're really looking at sums of lesser integers that are 2 or more.

4 --> 2+2 --> f(2)*f(2) = 1 (the 2 by 2 squares)

5--> already posted, only duplicate is 1,2,2 combo is same as 1,4 combo

6--> already posted, the 2,4 combos happen to be the same as the 3,3 and 2,2,2 combos.

For 7, we take 27*2 = 54, and then need to add extra combinations without a 1. Those combinations are below:

2+2+3 = f(2)*f(2)*f(3) = 2

2+5 = f(2) * f(5) = 11

3+4 = f(3)*f(4) = 10

From what I can tell (and I'm still going to try to write a description of how these numbers represent the visual pictures), the 2,5 combos are unique from the 3,4 combos. The two 2,2,3 combos, I think, are the same as two of 3,4 combos. Meaining, I think f(7) is 54 + 11 + 10 = 75.

Instead of trying to draw out all 75 combinations, I'm going to try (ask anyone else who is) to try drawing the 21-23 possibilities that do NOT contain any "unit" rectangles. For an idea of what a unit rectangle is, take a look back at the last picture at many of the yellow rectangles that are the same height as the whole square, but a much smaller width. I think I (and hopefully y'all) are convinced that 2*f(n-1) calculates all the possibilities of those.

My next post will (hopefully) be a picture of 21 or more divisions of 7 rectangles that are unique based on these principles. After that, I might move onto 8, or I might delve into calculating how to figure out when things repeat cases (I think it has to do with factors ... as in since 2x2 = 4, that 2,2,3 has some of the same cases as 4,3).

[Guest]

i've been gone for a while, but have basically caught up. And have been turning a thought over in my mind. We have established that all iterations with a "unit rectangle" can be calculated using 2*f(n-1). By the same token, we have found that using f(n-2,3,4,etc.) can be used to help calculate the iterations without the unit rectangle. My thought was that maybe these functions of lower divisions could also be used to mathematically eliminate the duplicates?

This would be done by subtracting from the final sum (before eliminating duplicates) some function of f(n-x) or something along those lines. I'm not really sure how it would work exactly, but i'm working on some sort of tangible theory.

Edited June 4, 2008 by The Giant Panda

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

[HoustonHokie]

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.

oh boy. That brings a whole new level of complexity to this problem. If we call this the central square solution, I think we'll eventually find that there is a whole subset of central square solutions available for every n>=5. And the configuration of the central square is based on the available solutions for n-4 -- that is, the central square for n=5 is the same is the solution for n=1, but for n=6, you'll have all the solutions for n=2 contained in a central square with exterior dimensions sqrt(2/6). That adds two solutions to f(6) - one for the 12th f(5) solution with a unit rectangle and one for the f(6) solution with the central square, because f(2)=1. But when you look at f(7), you'll be adding even more, because the configuration of the central square is based on f(3)=2. And for f(8), the central square contains all the solutions for f(4)=5, and so on... And it may even be possible to have the central square be a rectangle instead (still working on the geometry here), which would add a whole other dimension to the problem, because the solutions would expand by rect(n) instead of square(n). [i insert here that I have now convinced myself that rect(n) does not equal 2*square(n) as I originally postulated - the four-square (or four-rectangle) solution to rect(4) throws a monkey wrench into that idea.]

In some ways, this confirms a suspicion that I've had for a while. I've been wondering about what happens when we reach the next square number (9), because the four-square solution for n=4 caught me by surprise. Every other f(4) solution is repeated twice in f(5) except that four-square solution, because it's 90-degree rotation is a duplicate of itself. The same will happen for the nine-square solution in f(9) and I wonder if we're prepared to adequately count these square solutions as n increases.

I'm beginning to think we have a post-graduate geometry problem on our hands here - I know that there is a significant body of work on efficient equal area divisions, but those tend to focus on finding the equal area subdivision while minimizing the cutting perimeter. Apparently there are industrial applications where they need to cut equal area shapes out of a larger shape, and these papers are trying to figure out how to do that with the least amount of cutting. See, for example, http://citeseer.ist.psu.edu/cache/papers/c...se98cutting.pdf.

[Guest]

Hi eveyone - I'm new here, but have been following this one with some interest.

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

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