User:Hakerh400/Rectangle with rational side length

Statement

Any rectangle that is tiled with finitely many rectangles, each having at least one rational side, also has at least one rational side.

Proof

We perform strong induction on the number of small rectangles. Suppose the big rectangle is tiled with n small rectangles.
.If n = 1, the small rectangle is equal to the big rectangle, so the condition is trivially satisfied.
.If n = 2, the two small rectangles must share a side. If the common side is rational, then that side of the big rectangle is also rational, because it has the same length as the corresponding side of the big rectangle. If the common side is irrational, then both rectangles must have rational other sides. Since one of the sides of the big rectangle consists exactly of the rational sides of the small rectangles, and since rational numbers are closed under addition, the corresponding side of the big rectangle is also rational.
.Suppose n >= 3.
.If there exists a proper sub-rectangle inside the big rectangle consisting of two or more rectangles, then by the induction hypothesis that sub-rectangle has at least one rational side. Therefore, we can remove all rectangles from that sub-rectangle and replace the sub-rectangle with a single rectangle. That new rectangle has at least one rational side and the new configuration of the big rectangle represents a valid tiling. The new configuration has fewer rectangles, so we can directly apply the induction hypothesis.
.Suppose there is no sub-rectangle inside the big rectangle consisting of two or more rectangles. Consider the set of all small rectangles touching the top side of the big rectangle. Pick any of them whose vertical side is the shortest and name it x. The top side of x does not cover the entire top side of the big rectangle, because otherwise everything below x would form a sub-rectangle consisting of at least two small rectangles, violating the assumption.
.If the vertical side of x is rational, then extend the bottom side of x to the left and right sides of the big rectangle, forming new rectangles. Each rectangle that is split into two new rectangles touches the top side of the big rectangle, because x has the shortest vertical side among all rectangles that touch the vertical side of the big rectangle. Consider a rectangle that is split into two new rectangles by the line we drew. If it has rational horizontal side, the two new rectangles also have rational horizontal side. If it has rational verical side, the upper new rectangle also has vertical rational side, because x has rational vertical side and the split rectangle shares the top y-coordinate with x, and the lower rectangle also has vertical rational side, because the split rectangle had rational vertical side and rational numbers are closed under subtraction. The line that we drew divides the big rectangle into upper and lower sub-rectangle consisting of small rectangles. The lower sub-rectangle consists of no more than n - 1 small rectangles, because it contains all lower parts of the split rectangles and all non-split rectangles except x, so we can directly apply the induction hypothesis. The upper sub-rectangle consists only of small rectangles that share vertical side, so we can recursively apply induction hypothesis to each consecutive pair of small rectangles, since they form a sub-rectangle of exactly two small rectangles.
.Suppose the vertical side of x is irrational. Consider the set of all small rectangles touching the bottom side of x. Pick any of them whose vertical side is the shortest and name it y. The top side of y does not cover the entire bottom side of x, because otherwise x and y would form a sub-rectangle.
.If y has rational vertical side, extends the bottom side of y such that it represents a vertical translation of the bottom side of x, forming new rectangles. Each rectangle that is split in two parts by the line we drew touches the bottom side of x. Each of the new rectangles have at least one rational side for the same reasons it held when extending the bottom side of x. A new sub-rectangle is formed. The top side of that sub-rectangle is the bottom side of x and the bottom side is the line we drew. The left and right sides of the sub-rectangle are the vertical sides of the small rectangles touching the bottom of x. The sub-rectangle consists of at least 2 and no more than n - 1 small rectangles, because it must contain y and at least one upper part of a split rectangle horizontally adjacent to y, but does not contain the rectangle on the left or right of x. We can replace the sub-rectangle with a single small rectangle. The remaining configuration of the big rectangle contains no more than n - 1 small rectangles, so we can directly apply the induction hypothesis.
.Suppose y has irrational vertical side. y cannot touch the bottom side of the big rectangle, because the set of small rectangles that touch the bottom side of x has at least two small rectangles (otherwise x and y would form a sub-rectangle), the top side of each small rectangles that touches the bottom side of x completely belongs to the bottom side of x (otherwise either x would not have the shortest vertical side, or it would form a sub-rectangle with adjacent small rectangles), and every small rectangle that touches the bottom side of x and a vertical side of y must have longer vertical side than y (otherwise it would form a sub-rectangle with y). Thus, there exists a rectangle that touches the bottom side of y.
.If there exists a small rectangle b that touches the bottom side of y, but its top side does not completely belong to the bottom side of y, perform the transformation described in this paragraph, otherwise skip this step. If b exists, it means the top-left corner of y must overlap with the bottom-left corner of x, or the top-right corner of y must overlap with the bottom-right corner of x, otherwise y would not have the shortest vertical side. There can exist at most one b, otherwise y would form a sub-rectangle with adjacent rectangles. Either the top-left corner of b is the bottom-left corner of y, or the top-right corner of b is the bottom-right corner of y, otherwise y would form a sub-rectangle with adjacent small rectangles. Without loss of generality, suppose that the top-left corner of b overlaps with the bottom-left corner of y. Perform the following transformation. Extend the right side of y to the bottom side of b, splitting b into left and right part. If the vertical side of b is rational, then each of the new ractangles has at least one rational side. If the horizontal side of b is irrational, the horizontal side of the left part is rational because the x-coordinate of its left side is the same as the x-coordinate of the left side of y and the length of its horizontal side is equal to the length of the rational horizontal side of y, and the horizontal side of the right part is rational because the horizontal side of b is rational and rational numbers are closed under subtraction. The new configuration has n + 1 small rectangles. Now apply the induction hypothesis to the subrectangle containing y and the left part of b, replcaing it with a single small rectangle, This new configuration again has n small rectangles. The difference is that the condition for performing this transformation no longer holds.
.Regard y as the new x and repeat the steps when x has irrational vertical side. This process must terminate, because in each step the y-coordinate of the top side of x increases, it must be equal to the y-coordinate of the top side of some of the small rectangles from the initial configuration, no rectangles with a new y-coordinate of their top side are introduced in the process, and there exists a finite number of rectangles in the initial configuration.