Tek-Tips is the largest IT community on the Internet today!
Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!
-
Congratulations SkipVought on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!
Square splitting
- Thread starter cobolist
- Start date
Let's see if I understand this. You're given a square with length n per side and you're told to split it into a number of rectangles with different areas. What is the condition? That the single square be split up into a number of rectangles at ONCE? Or just to see how many different sets of rectangles you can make with different areas.
One thing I will say: The number of rectangles would be infinite unless you specified a limit upon the conditions. If we let X and Y be the dimensions of a rectangle made out of this square, X and Y (for example) would have to be made integers before a limited result could be obtained.
I guess it's clear that I'm not quite understanding the problem as you have specified it. Of course, one of the key rules of computer science is that a well-stated problem is a problem half-solved. So you might want to clarify yourself.
Measurement is not management.
One thing I will say: The number of rectangles would be infinite unless you specified a limit upon the conditions. If we let X and Y be the dimensions of a rectangle made out of this square, X and Y (for example) would have to be made integers before a limited result could be obtained.
I guess it's clear that I'm not quite understanding the problem as you have specified it. Of course, one of the key rules of computer science is that a well-stated problem is a problem half-solved. So you might want to clarify yourself.
Measurement is not management.
- Thread starter
- #4
I meant that I have an nxn-board (or chessboard). Then I have to find rectangles A_1,...,A_m with integer sides such that A_i intersection A_j = emptyset for every i < j, |A_1|<|A_2|<...<|A_m| (|A_i| means the size of A_i, 2-dimensional Lebesgue measure) if they are ordered by size, and A_1 union A_2 ... union A_m equals nxn-board. Now I have to list the lengths of every A_i and determine what is the maximum of m as a function of n.
- Thread starter
- #5
I have to list the lengths of every A_i "
Sorry. Sctually I have to list width and height of every A_i and their position on a board. So for example 6x6 board can be split into four pieces like this:
SSSS))
SSSS))
hhhh))
$$$$$$
$$$$$$
$$$$$$
Sorry. Sctually I have to list width and height of every A_i and their position on a board. So for example 6x6 board can be split into four pieces like this:
SSSS))
SSSS))
hhhh))
$$$$$$
$$$$$$
$$$$$$
What does that mean in English?
As I understand it, you have to split up an integer-sized square into the maximum number of integer-sized rectangles, where no two rectangles have the same size.
Do the rectangles have to be, well, rectangles? Are squares allowed?
-- Chris Hunt
Webmaster & Tragedian
Extra Connections Ltd
- Thread starter
- #7
As I understand it, you have to split up an integer-sized square into the maximum number of integer-sized rectangles, where no two rectangles have the same size."
True. And no two rectangles overlaps.
"Do the rectangles have to be, well, rectangles? Are squares allowed?"
Squares are allowed as they are rectangles.
True. And no two rectangles overlaps.
"Do the rectangles have to be, well, rectangles? Are squares allowed?"
Squares are allowed as they are rectangles.
SkipVought
Programmer
cobolist,
Unfortunately, you have made yourself irrelevant to many browsers, by your careless inattention to relevant details in your original post.
What other requirements are you going to change? Few are going to waste their time dabbling in your uncertainties.
Skip,
[sup]
![[glasses]](/data/assets/smilies/glasses.gif "[glasses] [glasses]")
Don't let the Diatribe...talk you to death!
![[tongue]](/data/assets/smilies/tongue.gif "[tongue] [tongue]")
[/sup][sub]Just traded in my old subtlety...for a NUANCE!
[/sub]I don't know if the Lebesgue Measureis the right word for it?
I have a question to your example:
SSSS))
SSSS))
hhhh))
$$$$$$
$$$$$$
$$$$$$
Do you mean hhhh on chessboard has Lebesque Measure of dimension 2?
I think in the plain geometry a point would be a object with Lebesgue Measure of 0, a line Lebesgue Measure of 1 and a part of plain would have Lebesgue Measure of 2.
Transfered to the chess board, which is however differently to the plain a discrete set, instead of a point we can take a field, instead of a line we can take a row or column etc...
So IMHO your hhhh, which is a part of row has a measure (in Sence of Lebesgue) of 1 and not 2 as you explain.
Now apart of the Lebesgue Measure: Is this problem generally solvable or not?
Let us take a trivial example: square board of 2x2. Then there isn't a solution.
If I try e.g.
AB
xB
I have 2 rectangles A and BB, |A| < |BB| but x is invalid because |x| =|A|
INHO: this task doesn't have a solution.
Now let us take a task of 3x3:
The possible solutions are:
AAB
CCB
CCB
or
ABB
CCC
CCC
I.e. the maximum of rectangles is 3.
I have a question to your example:
SSSS))
SSSS))
hhhh))
$$$$$$
$$$$$$
$$$$$$
Do you mean hhhh on chessboard has Lebesque Measure of dimension 2?
I think in the plain geometry a point would be a object with Lebesgue Measure of 0, a line Lebesgue Measure of 1 and a part of plain would have Lebesgue Measure of 2.
Transfered to the chess board, which is however differently to the plain a discrete set, instead of a point we can take a field, instead of a line we can take a row or column etc...
So IMHO your hhhh, which is a part of row has a measure (in Sence of Lebesgue) of 1 and not 2 as you explain.
Now apart of the Lebesgue Measure: Is this problem generally solvable or not?
Let us take a trivial example: square board of 2x2. Then there isn't a solution.
If I try e.g.
AB
xB
I have 2 rectangles A and BB, |A| < |BB| but x is invalid because |x| =|A|
INHO: this task doesn't have a solution.
Now let us take a task of 3x3:
The possible solutions are:
AAB
CCB
CCB
or
ABB
CCC
CCC
I.e. the maximum of rectangles is 3.
lionelhill
Technical User
Since no one has suggested an algorithm yet, I'll give a brute-force solution, but it's horrible.
Consider the square as being divided up into 1*1 integer cells, each bounded by walls. The walls can be "on" or "off". The idea is to find situations where all the shapes left between the walls are rectangular (including square), and all are of different area. Therefore go through every combination of walls being on or off, and test for this condition.
For a square of side n, there are 2(n-n)n walls, so the algorithm would appear to scale as n-squared, which is already not nice (though almost to be expected from a problem dealing with area). However, it's worse than this, as the number of cases increases with n-squared, but so does the complexity of testing each case, so it may well scale as badly as n to the fourth.
Of course you can do a few simple optimisations, such as failing the test as soon as two rectangles have the same size, or a shape fails to be a rectangle. Whole ranges of wall combinations can be rejected, because if the walls at the top left corner already form a non-rectangle, changing a wall outside this shape will never correct the situation. Further, once you've found a "good" combination, you may be able to reject many bad combinations early, because if the remaining area to test is too small to contain enough rectangles to reach the "good" value, it must already be bad.
Consider the square as being divided up into 1*1 integer cells, each bounded by walls. The walls can be "on" or "off". The idea is to find situations where all the shapes left between the walls are rectangular (including square), and all are of different area. Therefore go through every combination of walls being on or off, and test for this condition.
For a square of side n, there are 2(n-n)n walls, so the algorithm would appear to scale as n-squared, which is already not nice (though almost to be expected from a problem dealing with area). However, it's worse than this, as the number of cases increases with n-squared, but so does the complexity of testing each case, so it may well scale as badly as n to the fourth.
Of course you can do a few simple optimisations, such as failing the test as soon as two rectangles have the same size, or a shape fails to be a rectangle. Whole ranges of wall combinations can be rejected, because if the walls at the top left corner already form a non-rectangle, changing a wall outside this shape will never correct the situation. Further, once you've found a "good" combination, you may be able to reject many bad combinations early, because if the remaining area to test is too small to contain enough rectangles to reach the "good" value, it must already be bad.
lionelhill
Technical User
For those who didn't read the previous post beyond the first line (who wants to spoil the fun by getting a bad solution early?), here's an extra twist to the original problem:
The maximum number of rectangles of different area we can put into any shape is clearly 1+2+3+4...+x (since this uses all possible areas). A square has area n-squared. So presumably somewhere there are squares where:
n^2 = 1+2+3...+x.
Firstly: can we find which values of n will do this?
Secondly: can we prove whether or not there is any practical way to arrange the rectangles so they'll fit?
Actually the second part is very easy for most specific squares.
The maximum number of rectangles of different area we can put into any shape is clearly 1+2+3+4...+x (since this uses all possible areas). A square has area n-squared. So presumably somewhere there are squares where:
n^2 = 1+2+3...+x.
Firstly: can we find which values of n will do this?
Secondly: can we prove whether or not there is any practical way to arrange the rectangles so they'll fit?
Actually the second part is very easy for most specific squares.
- Thread starter
- #12
Let us take a trivial example: square board of 2x2. Then there isn't a solution.
If I try e.g.
AB
xB"
There is a solution:
AA
AA
I'm sorry using the word Lebesgue measure. As a mathematician I just think areas as Lebesgue measures. So nxn board has measure n^2.
If I try e.g.
AB
xB"
There is a solution:
AA
AA
I'm sorry using the word Lebesgue measure. As a mathematician I just think areas as Lebesgue measures. So nxn board has measure n^2.
- Thread starter
- #14
For those who didn't read the previous post beyond the first line (who wants to spoil the fun by getting a bad solution early?), here's an extra twist to the original problem:
The maximum number of rectangles of different area we can put into any shape is clearly 1+2+3+4...+x (since this uses all possible areas). A square has area n-squared. So presumably somewhere there are squares where:
n^2 = 1+2+3...+x.
Firstly: can we find which values of n will do this?"
n=1 is the only solutions. You can get the Pell equation n^2-8x^2=1 and solve it via standard technique.
The maximum number of rectangles of different area we can put into any shape is clearly 1+2+3+4...+x (since this uses all possible areas). A square has area n-squared. So presumably somewhere there are squares where:
n^2 = 1+2+3...+x.
Firstly: can we find which values of n will do this?"
n=1 is the only solutions. You can get the Pell equation n^2-8x^2=1 and solve it via standard technique.
n=1 is the only solutions. You can get the Pell equation n^2-8x^2=1 "
Don't un understand. Wherefore is the above equation?
I used this approach:
Tried to construct rectangle of size 1, then rectangle of size 2,...
So if I have constructed rectangle of size k, I tried to construct rectangle of size k+1, if it was not possible then rectangle of size k+2,...etc
Results:
For n=1, we have only trivial solution i.e one rectangle of surface 1, because
1^2 = 1
For n=2, we have only trivial solution i.e one rectangle of surface 4, because
2^2 = 4
For n=3:
3^2 = 1 + 2 + 6 (3 rectangles - of sizes 1, 2 and 6)
For n=4:
4^2 = 1 + 2 + 3 + 4 + 6 (5 rectangles)
For n=5:
5^2 = 1 + 2 + 3 + 4 + 5 + 10 (6 rectangles)
For n=6:
6^2 = 1 + 2 + 3 + 4 + 6 + 8 + 12 (7 rectangles)
For n=7:
7^2 = 1 + 2 + 3 + 4 + 5 + 6 + 10 + 18 (8 rectangles)
For n=8:
8^2 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 12 + 24 (9 rectangles)
So, this leads me inductive to this presumption:
For n >= 4 the maximal number of rectangles is n+1.
You can proove if it's true or false using mathematical induction.
Don't un understand. Wherefore is the above equation?
I used this approach:
Tried to construct rectangle of size 1, then rectangle of size 2,...
So if I have constructed rectangle of size k, I tried to construct rectangle of size k+1, if it was not possible then rectangle of size k+2,...etc
Results:
For n=1, we have only trivial solution i.e one rectangle of surface 1, because
1^2 = 1
For n=2, we have only trivial solution i.e one rectangle of surface 4, because
2^2 = 4
For n=3:
3^2 = 1 + 2 + 6 (3 rectangles - of sizes 1, 2 and 6)
For n=4:
4^2 = 1 + 2 + 3 + 4 + 6 (5 rectangles)
For n=5:
5^2 = 1 + 2 + 3 + 4 + 5 + 10 (6 rectangles)
For n=6:
6^2 = 1 + 2 + 3 + 4 + 6 + 8 + 12 (7 rectangles)
For n=7:
7^2 = 1 + 2 + 3 + 4 + 5 + 6 + 10 + 18 (8 rectangles)
For n=8:
8^2 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 12 + 24 (9 rectangles)
So, this leads me inductive to this presumption:
For n >= 4 the maximal number of rectangles is n+1.
You can proove if it's true or false using mathematical induction.
Here Excel sheet with the squares
lionelhill
Technical User
n=1 is the only solutions. You can get the Pell equation n^2-8x^2=1 and solve it via standard technique. "
Not sure that's true. For example, it works for n=6, x=8
n^2 = 36
36 = 1+2+3+4+5+6+7+8
However, I'm utterly sure that you cannot divide a 6-by-6 square into 8 different sized rectangles (you can, of course, divide it into 8 shapes of different integer area if you don't mind non-rectangular shapes).
Also I'm not sure of the equation. The area of the sum of shapes area 1+2+3...x is given by
((x+1)/2)*x
=(x^2 + x)/2
The area of the square is n^2
So the equation is
n^2 = (x^2 + x)/2
=> 2(n^2) = x^2 + x
You'll notice that both sides of the equation = 72 for the example n=6, x=8
Not sure that's true. For example, it works for n=6, x=8
n^2 = 36
36 = 1+2+3+4+5+6+7+8
However, I'm utterly sure that you cannot divide a 6-by-6 square into 8 different sized rectangles (you can, of course, divide it into 8 shapes of different integer area if you don't mind non-rectangular shapes).
Also I'm not sure of the equation. The area of the sum of shapes area 1+2+3...x is given by
((x+1)/2)*x
=(x^2 + x)/2
The area of the square is n^2
So the equation is
n^2 = (x^2 + x)/2
=> 2(n^2) = x^2 + x
You'll notice that both sides of the equation = 72 for the example n=6, x=8
- Thread starter
- #18
This does not seem to be clearly true to me. In fact, it seems that it is incorrect, but I'm not certain I can prove it either way.
If I'm understanding you correctly, it seems that you are focusing exclusively on rectangles of size 1 by y (where y is an integer from 1 to x). Keep in mind that rectangles of size 1x4 and 2x2 both have the same area, but their differing dimensions permit both to be in the solution.
lionelhill
Technical User
KornGeek,
Thanks for the comment. To clear up possible misunderstanding, no, I'm just considering that no two rectangles are allowed to have the same area, so the absolute maximum number of rectangles into which we can divide any shape is 1+2+3... where these values are the areas, all possible areas being represented. I don't mind whether area 4 is represented by a 1*4 or a 2*2 block.
I'm also inclined to think no such square exists. When I suggested the first question, I think I meant "how do we find the pairs of values n and x satisfying n^2=1+2+..n".
The second part of the question is how do we prove whether there is actually a genuine square out there that can be divided this way.
The obvious thought that springs to mind is that no square n can be divided this way if there is a prime number between x and n, since prime numbers can only be rectangles 1 unit wide, and if this rectangle is bigger than n, it doesn't fit in the square. I'm pretty sure prime numbers appear a lot more frequently than squares! But the progression of prime numbers is way outside my knowledge.
Thanks for the comment. To clear up possible misunderstanding, no, I'm just considering that no two rectangles are allowed to have the same area, so the absolute maximum number of rectangles into which we can divide any shape is 1+2+3... where these values are the areas, all possible areas being represented. I don't mind whether area 4 is represented by a 1*4 or a 2*2 block.
I'm also inclined to think no such square exists. When I suggested the first question, I think I meant "how do we find the pairs of values n and x satisfying n^2=1+2+..n".
The second part of the question is how do we prove whether there is actually a genuine square out there that can be divided this way.
The obvious thought that springs to mind is that no square n can be divided this way if there is a prime number between x and n, since prime numbers can only be rectangles 1 unit wide, and if this rectangle is bigger than n, it doesn't fit in the square. I'm pretty sure prime numbers appear a lot more frequently than squares! But the progression of prime numbers is way outside my knowledge.
- Status
