A large rectangle in the plane is partitioned into smaller rectangles, each of which has either integer width or integer height (or both). Prove that the large rectangle also has this property.

im gonna assume the arrows mean that that dimension of the rectangle is integer
>picrel
you can see that the pink rectangles all have integer widths and that they can be line together to form the exact length of the large rectangle
so the length of the large rectangle is a sum of integers and therefore an integer

I think OP was asking about the general case, not this particular example

I think the proof is based on the fact that integer+integer can never be non-integer. This results in contagious integers or else OP's rule of "has either integer width or integer height (or both)" would be broken.

I can't prove this but it feels correct.

this sounds like some group theory argument

P10679
That's definitely involved, but you'll need to show that there will always be some rectangles whose widths or heights add (or perhaps subtract?) up to that of the full rectangle, like the red ones in P10652. That's the critical part.

P10679

This and by induction QED.

P11141
What do you mean?

The obvious induction argument would be to first claim that you can make any such arrangement of rectangles by either starting with a single small rectangle or combining two previously made large rectangles vertically or horizontally. The desired result would follow easily, but the claim is not true.

P11282

*waves hands*

It is clear.

Qed.

What we are asked to prove is not true. Counterexample: picrel.

The arrows indicate the dimension that is integer-denominated. Here we see that the rectangle has a non-integer height (integer + non-integer) and a non-integer width (integer + non-integer).

P11289
In that case the central square would also have non-integer width and height (integer - non-integer), violating the conditions of the problem.

P11330
Wrong. That doesn't follow. The central rectangle (widen or stretch the image and all of this still holds) can have arbitrary dimensions and my counterexample holds.
>integer - non-integer
What integer are you subtracting a non-integer from here?

P11343
If you claim red and orange are integers and green is a non-integer, then magenta = orange - green is also a non-integer.

P11344
from the OP
>each of which has either integer width or integer height (or both)
so green can be an integer, therefore magenta is also an integer

P11371
In that case, the complete rectangle also has an integer height (red + green = height)

P11385
well shit thats true

Tell me why I'm wrong because this reasoning seems to proof it very easily but I think there's some flaw somewhere:
* Assume origin is at the lower left corner of the rectangle.
* Project all horizontal sides of all partitioned sub-rectangles whose sides are integers on the x axis.
* Project all vertical sides of all partitioned sub-rectangles whose sides are integers on the y axis.
* There can't be a gap on both the x axis and the y axis at the same time, or else that would mean there's some rectangle inside the big one whose sides are non-integers, which is a contradiction.
* Even if there's the following situation (# represents some arbitrary rectangle):
_____
| |
| #|
| # |
|____|

and the gap of the projected segments happens to be have integer lengths on both axis (# are squares of side 1/2 for example), they must have come from non-integer sided rectangles, or else they would have been initially projected, and thus not part of a gap.
The rectangles don't have to necessarily touch only on a single point for this situation to arise, but it's easier to type.

P11404
Can you explain what it means to have a gap? Would the projections of the vertical sides in the OP image have a gap? Because they seem to completely cover the y-axis up to the top of the big rectangle, but that doesn't prove the big rectangle has an integer height.

P11405
OPs image wouldn't have "gaps", yeah, disregard.
[spoiler: https://en.wikipedia.org/wiki/Strong_law_of_small_numbers]

i was gonna work on my schizospammer, but this caught my eye because i think i can prove by absurd that the large rectangle cannot have both width and height be non-integer
i already made drawings to illustrate it, i just need to organize my explanation brb

ok here goes the proof by absurd
DEFINITION 1: the large rectangle's both width and height are non-integer
from there i will treat the area of the rectangle with non-integer dimensions as "free space" that shall be partitioned using rectangles with at least one integer side
so adding the first rectangle, there are 5 possibilities
>0. it is touching 0 sides of the large rectangle
>1. it is touching 1 side
>2. it is touching 2
>3. touching 3
>4. 4

#4 is literally impossible bc it contradicts DEF1
#0 makes the rectangle be floating in the middle of the free space
#3 means the big rectangle was cut in 2 (but not in equal parts)
#1 and #2 are actually very similar upon analysis, so they get a single drawing

when i add the new rectangle, i break the remaining free space into rectangles again, alongside the sides of the new rectangle, for simplicity's sake [spoiler: ah fugg, i just noticed i got a bit lazy with the bump figure and didnt make lines come out of all edges, but doesnt really matter, you are a big boy and can see the result is the same anyway]
and ok so basically you always end up with a smaller double-non-integer rectangle no matter what you do (the exact same problem you started with)
and since this happens with all possible cases, im pretty sure this proves that DEF1 is absurd and so the rectangle must have at least one side be an integer
ok maybe it can still work if you use infinite rectangles, but thats cheating, dont do that

>partitioned using rectangles with at least one integer side
i was gonna type this but i forgot
<partitioned using rectangles with at least one integer side, without contradicting DEF1
that was the entire reason i spelled the basic assumption as "DEFINITION 1" like a nerd
but whatevs, that went without saying anyway, just a typo meh

P11466
You cover all possible cases for the initial yellow rectangle, but I don't think you've covered all possible cases for how to partition the remaining space with the rectangles. For example, P11282 doesn't look like any of your cases.

P11470
*for how to partition the remaining space with the red rectangles

P11470
its just case0
but i getcha, i did a lot tests with other partitions behind the scenes, but idk if i really did all possible cases
also i cant really prove that simply extending the edges of the added rectangle and show by exhaustion that all cases result in leftover non-integer space is enough to prove there isnt some autistic shape you can make as a counter example
but intuitively i feel that creating several small spaces are just special cases of when you make the spaces as big as possible
i hope idoru-sensei can review my answer and maybe expand on it to make it not look like its really just cirno doing math

P11282
Just nest the four outer rectangles an infinite number of times. No need to make this all complicated, only a single counter-example is needed.

There is one thing that bothers me. What if the remaining space isn't a rectangle?

P11476
you can just break in into several rectangles, that's what i do when i create the red rectangles
since you start from a rectangle and add more rectangles, the space can always be composed of several rectangles bc all angles in it are 90 degrees

>all angles in it are 90 degrees
or 270, or 180...
but you got it what i meant

P11475
Problems:
1. I don't know if subdivisions of infinitely many rectangles is supposed to be within the scope of the problem. But then again we can examine that case for fun anyway.
2. I don't think your infinite nesting scheme is compatible with giving at least one integer dimension to all rectangles. As your rectangles get smaller, eventually they will be smaller than a 1x1 so neither side can be an integer.
3. What about the point in the center? It isn't contained in any rectangle, and isn't on the border of any rectangle. So I don't know if you can even say you've partitioned the rectangle.

btw in op's image, several rectangles can be merged
but even though it doesnt really look like one of my cases, idk if it really matters bc both P10629 and P11282 have been shown to violate DEF1 in P10652 and P11344

P11480
>1.
your 2. trivially shows the solution to that
you cant create infinite rectangles bc at some point they will get smaller than 1x1
and since infinite nesting is a big no-no, you cant have a partition scheme that leaves a non-interger rect remaining
>3.
im not using "partition" in the strict sense of the word, i just add a rectangle anywhere and then cut the big one along the small one's edges
and from the new rectangles that get formed, i try to see which ones i can give integer sides, and always find that one is left with both sides necessarily being non-integer, no matter how i cut and sort

P11478
Of course, but you may use many rectangles to create that rectangle space

P11483
>you cant create infinite rectangles bc at some point they will get smaller than 1x1
In the general case of infinitely many rectangles, only one dimension would be guaranteed to get smaller than 1, the other could still be an integer.

P11487
i just noticed that your example is equivalent to one of my cases and can be converted
in fact, in P11466 case #0 can be converted into case #3 by merging the rectangles
i will try the same approach, but instead of classifying by where the first rectangle touches the edges of the mother rect, i classify based on where the remaining free space touches it
P11488
i dont really see how it can get to a point where you can simply reduce a single dimension of the free space
you eventually have to stop the integer dimension at 1, but the problem is that the free space always ends up with both dimensions being non-integer
if you get to the point where you can use infinite rectangles, you dont need infinite rectangle, get what im saying? you can just merge the infinite rectangle into one that shares their integer side

P11498
>i will try the same approach, but instead of classifying by where the first rectangle touches the edges of the mother rect, i classify based on where the remaining free space touches it
just did that and yea, you always end up with the free space necessarily having both non-integer sides, starting the problem from scratch
im a bit lazy to put captions in my drawings rn so maybe later
but feel free to try on your own

>if you get to the point where you can use infinite rectangles, you dont need infinite rectangle, get what im saying? you can just merge the infinite rectangle into one that shares their integer side
That's my suspicion too, but I don't have a proof.