I have an idea of how to do this, and I think it should work. I think you can prove this by induction.

The case where there are only two rectangles inside should be trivial since there are only a few cases that are possible with two rectangles inside. Then assume that this is true for n rectangles inside, and prove it for n+1 rectangles. The only thing you would have to prove at that point is that it is possible that you can conjoin two rectangles inside to make a larger rectangle with that property (since both rectangles that make it up have that property). Then look what you have! You have n rectangles inside with the property, so the whole rectangle has the property.

Hmm.. I was just thinking. This works if you have a countable set of rectangles inside of this larger rectangle. However, this proof does NOT work for an uncountable set. Is it possible to have an uncountable set of rectangles making up this larger rectangle? This proof may be much harder to prove for an uncountable set.

There should not be a limit in the number of rectangles inside, but they can grow upto very big numbers. The way you use "induction" sounds reasonable BUT as the number of rectangles increase we may have different combinations / different shapes. Imagine it this way: First number is the number of rectangles, second is "different" combinations (relative positions): 1 -> 1 2 -> 1 3 -> 2 4 -> 4 (I think) 5 -> ? 15 -> must be a very very big number.

Also we may have a situation in which sub-rectangles can NEVER form a bigger rectangle other than the biggest one.

I'm not sure that the number of different combinations will matter much with the induction I used. Since n represents ANY combination with n rectangles. And if I were to combine two rectangles with n+1 rectangles, then that certainly is a combination with n rectangles.

I think the proof lies at the fact that it is ALWAYS possible to conjoin two or more rectangles inside this larger rectangle. I'll work on the proof later though. I need to do something else atm.

i have tried to attack the problem by coloring the voronoï graph corresponding to a general puzzle (see example here: http://bleaug.free.fr/8foxes/8foxes320.png). E.g. green arcs for horizontally adjacent rectangles, orange for vertically adjacent rectangles.

This graph can be partitioned into green cells (resp. orange cells) which correspond to each longest horizontal (resp. vertical) segments inside the rectangle.

My gut feeling is that there is a general proof based on these graphs... but no success so far. Maybe a starting point.

I was shocked when I saw your graph, since I had the "very same" approach to find a solution. The closeness of our souls is making me nervous -with all due respect!

In addition to that I have checked the DUAL of the graph (a simpler one will be more helpful). I have tried to see if this problem can be reduced to one of the classical problems, such as Maximum-Flow or Edge-Coloring problems. But I could not see an immediate reduction.

Similarly, I am smelling that this problem can be smartly-reduced to a known/solved graph theory problem.

Sorry for the delayed response. I believe I have come up with a general solution to the problem using induction, though not pretty.

On the way, I found some interesting properties that I probably should have known beforehand. First of all, I am not correct about conjoining two rectangles inside to make a larger rectangle always being possible. Secondly, if you include the boundary of the larger rectangle, then you can't have an infinite number of subrectangles inside of this larger rectangle, only a finite number. Anyways, I will post the proof when I feel confident enough in its worth. Also, I like the approach you are using, Bleaug. You are probably right too, in that there is a general proof in those graphs.

Here you go. You don't have to read the first part of the post, it was just some interesting features I noticed with the rectangle and sub-rectangles in general. I wrote the post rather quickly, so please let me know if you see some errors. I think the general proof is pretty clear and understandable. Thank you.

Alright, it's fixed. I will probably continually edit the post to make it better, so any suggestions is definitely welcome. And if someone finds a better way to combine two rectangles inside and still retain Property P, let me know.

Alright, sorry for the five posts in a row. I keep finding holes in my argument though. Just ignore my proof for the time being. I need to think this thoroughly and make sure I have everything correct before I post again.

I think your induction approach is good. Playing with the idea, I may have found a similar proof.

First I established through tedious enumeration not explained here that every rectangle puzzle of order N >= 2 contains one of the two following sub-figures (modulo symmetries): http://bleaug.free.fr/8foxes/8foxes320b.png i.e.: a) two adjacent rectangles with a matching side, or b) one rectangle matching two rectangles.

Unfortunately my proof of this is really ugly. Maybe someone can come up with something short and elegant for this step?

We then show that these two sub-figures can be redrawn as sub-figures having one rectangle less, figures being made of rectangles with property (P). This is summarized in the following enumeration of cases: http://bleaug.free.fr/8foxes/8foxes320c.png

Then the induction argument becomes: - A 1-rectangle puzzle obviously has property P - Assume all (N-1)-puzzles have property P, since a N-puzzle contains either a) or b) sub-figure it can be transformed into a (N-1)-puzzle which has property P, so it has property P.

Yeah, that does seem to work. I'll try to see what I can come up with in proving your assertion. But, we still have to consider the case of a rectangle with uncountably many sub-rectangles. If we consider the large rectangle whose boundaries are included, then there can only be a finite number of sub-rectangles. But if we consider a large rectangle whose boundaries are not included, then we allow for an infinite number of sub-rectangles.

Though, I'm starting to consider that it isn't possible to have an uncountable number of sub-rectangles. I think I can give it an order. Consider the four corners of the large rectangle. There must only be one sub-rectangle for each corner, make those the first four. Now consider your second shape, there should be eight corners on it, again there is only one sub-rectangle per corner; label them 5 - 12. Continue this process, and there you go. I have given it an ordering, which makes it countable.

Now, I guess the only thing I'm concerned about with this proof is if I didn't leave a rectangle out. I'm not sure, what do you guys think?

Actually, I don't think that's a good proof at all. Since the sub-rectangles must have their boundaries contained, and the larger rectangle's boundaries are not contained, there can't be a single sub-rectangle whose side is on the "edge" of the larger rectangle.

I tend to agree that the only infinite rectangles are countable. But the only way to pack an infinite number of rectangles with property P into a larger rectangle is to align them along their matching integer side and thus form a larger rectangle. For example: http://bleaug.free.fr/8foxes/8foxes320d.png Obviously this larger rectangle has property P and we are back to finite case. This reasoning works whether the total number of rectangles is countable or not.

I have an idea of how to do this, and I think it should work. I think you can prove this by induction.

ReplyDeleteThe case where there are only two rectangles inside should be trivial since there are only a few cases that are possible with two rectangles inside. Then assume that this is true for n rectangles inside, and prove it for n+1 rectangles. The only thing you would have to prove at that point is that it is possible that you can conjoin two rectangles inside to make a larger rectangle with that property (since both rectangles that make it up have that property). Then look what you have! You have n rectangles inside with the property, so the whole rectangle has the property.

Hmm.. I was just thinking. This works if you have a countable set of rectangles inside of this larger rectangle. However, this proof does NOT work for an uncountable set. Is it possible to have an uncountable set of rectangles making up this larger rectangle? This proof may be much harder to prove for an uncountable set.

ReplyDeleteThere should not be a limit in the number of rectangles inside, but they can grow upto very big numbers.

ReplyDeleteThe way you use "induction" sounds reasonable BUT as the number of rectangles increase we may have different combinations / different shapes.

Imagine it this way:

First number is the number of rectangles, second is "different" combinations (relative positions):

1 -> 1

2 -> 1

3 -> 2

4 -> 4 (I think)

5 -> ?

15 -> must be a very very big number.

Also we may have a situation in which sub-rectangles can NEVER form a bigger rectangle other than the biggest one.

I'm not sure that the number of different combinations will matter much with the induction I used. Since n represents ANY combination with n rectangles. And if I were to combine two rectangles with n+1 rectangles, then that certainly is a combination with n rectangles.

ReplyDeleteI think the proof lies at the fact that it is ALWAYS possible to conjoin two or more rectangles inside this larger rectangle. I'll work on the proof later though. I need to do something else atm.

@six

ReplyDeletei have tried to attack the problem by coloring the voronoï graph corresponding to a general puzzle (see example here: http://bleaug.free.fr/8foxes/8foxes320.png). E.g. green arcs for horizontally adjacent rectangles, orange for vertically adjacent rectangles.

This graph can be partitioned into green cells (resp. orange cells) which correspond to each longest horizontal (resp. vertical) segments inside the rectangle.

My gut feeling is that there is a general proof based on these graphs... but no success so far. Maybe a starting point.

bleaug

Dear Bleaug,

ReplyDeleteI was shocked when I saw your graph, since I had the "very same" approach to find a solution. The closeness of our souls is making me nervous -with all due respect!

In addition to that I have checked the DUAL of the graph (a simpler one will be more helpful). I have tried to see if this problem can be reduced to one of the classical problems, such as Maximum-Flow or Edge-Coloring problems. But I could not see an immediate reduction.

Similarly, I am smelling that this problem can be smartly-reduced to a known/solved graph theory problem.

- Polar Fox

Sorry for the delayed response. I believe I have come up with a general solution to the problem using induction, though not pretty.

ReplyDeleteOn the way, I found some interesting properties that I probably should have known beforehand. First of all, I am not correct about conjoining two rectangles inside to make a larger rectangle always being possible. Secondly, if you include the boundary of the larger rectangle, then you can't have an infinite number of subrectangles inside of this larger rectangle, only a finite number. Anyways, I will post the proof when I feel confident enough in its worth. Also, I like the approach you are using, Bleaug. You are probably right too, in that there is a general proof in those graphs.

http://philosophiae88.blogspot.com/2010/12/rectangles-sub-rectangles-and-their.html

ReplyDeleteHere you go. You don't have to read the first part of the post, it was just some interesting features I noticed with the rectangle and sub-rectangles in general. I wrote the post rather quickly, so please let me know if you see some errors. I think the general proof is pretty clear and understandable. Thank you.

So there is a little problem with my stripping procedure, but I think I can fix it.

ReplyDeleteAlright, it's fixed. I will probably continually edit the post to make it better, so any suggestions is definitely welcome. And if someone finds a better way to combine two rectangles inside and still retain Property P, let me know.

ReplyDeleteAlright, sorry for the five posts in a row. I keep finding holes in my argument though. Just ignore my proof for the time being. I need to think this thoroughly and make sure I have everything correct before I post again.

ReplyDeleteI think your induction approach is good. Playing with the idea, I may have found a similar proof.

ReplyDeleteFirst I established through tedious enumeration not explained here that every rectangle puzzle of order N >= 2 contains one of the two following sub-figures (modulo symmetries):

http://bleaug.free.fr/8foxes/8foxes320b.png

i.e.: a) two adjacent rectangles with a matching side, or b) one rectangle matching two rectangles.

Unfortunately my proof of this is really ugly. Maybe someone can come up with something short and elegant for this step?

We then show that these two sub-figures can be redrawn as sub-figures having one rectangle less, figures being made of rectangles with property (P). This is summarized in the following enumeration of cases:

http://bleaug.free.fr/8foxes/8foxes320c.png

Then the induction argument becomes:

- A 1-rectangle puzzle obviously has property P

- Assume all (N-1)-puzzles have property P, since a N-puzzle contains either a) or b) sub-figure it can be transformed into a (N-1)-puzzle which has property P, so it has property P.

bleaug

Yeah, that does seem to work. I'll try to see what I can come up with in proving your assertion. But, we still have to consider the case of a rectangle with uncountably many sub-rectangles. If we consider the large rectangle whose boundaries are included, then there can only be a finite number of sub-rectangles. But if we consider a large rectangle whose boundaries are not included, then we allow for an infinite number of sub-rectangles.

ReplyDeleteThough, I'm starting to consider that it isn't possible to have an uncountable number of sub-rectangles. I think I can give it an order. Consider the four corners of the large rectangle. There must only be one sub-rectangle for each corner, make those the first four. Now consider your second shape, there should be eight corners on it, again there is only one sub-rectangle per corner; label them 5 - 12. Continue this process, and there you go. I have given it an ordering, which makes it countable.

Now, I guess the only thing I'm concerned about with this proof is if I didn't leave a rectangle out. I'm not sure, what do you guys think?

Actually, I don't think that's a good proof at all. Since the sub-rectangles must have their boundaries contained, and the larger rectangle's boundaries are not contained, there can't be a single sub-rectangle whose side is on the "edge" of the larger rectangle.

ReplyDeleteI tend to agree that the only infinite rectangles are countable. But the only way to pack an infinite number of rectangles with property P into a larger rectangle is to align them along their matching integer side and thus form a larger rectangle. For example:

ReplyDeletehttp://bleaug.free.fr/8foxes/8foxes320d.png

Obviously this larger rectangle has property P and we are back to finite case. This reasoning works whether the total number of rectangles is countable or not.

bleaug

The theorem may be more clear as a transposition.

ReplyDeletehttp://gene2.net/sup/images/1298465220_Single_Case.png

The general case.

http://gene2.net/sup/images/1298465252_General_Case.png

Thank you for the input Chonkin. Also see that non-integer side does not need to be an irrational number. It can be a fraction too.

ReplyDelete