Let us look at another way to solve previous problem:
Q: A unit square is dissected into n > 1 rectangles such that their sides are parallel to the sides of the square. Any line, parallel to a side of the square and intersecting its interior, also intersects the interior of some rectangle. Prove that in this dissection, there exists a rectangle having no point on the boundary of the square.
A: We suppose the contrary that such dissection does result in a rectangle with no points on the boundary of the square. We will consider an arbitrary counterexample. We know that each rectangle is attached to at least one side of the square. No rectangle can be attached to opposite sides otherwise one of its sides lies on a splitting line.
We call two rectangles as opposite if they are attached to the opposite sides of ABCD. We claim that there exists two opposite rectangles having a common point.
Consider the union L of all rectangles attached to the left. and assume that they have no common points with the rectangles attached to the right. Now if we take a polygonal line P that connects the top and bottom of the square and passing close to the right boundary of L then it is easy to visualize that the rectangles of L do not have opposites per our assumption. This means there are rectangles to the right of P and before the rectangles attached to the right. We call them buffer rectangles. Some of these buffer rectangles are attached to the top and some are attached to the bottom. Consequently there is a point on P within the square where the top and the bottom rectangles meet. So there always exists a pair of opposite rectangles
and more importantly no buffer rectangles exist.
Having established that there are opposite rectangles within a square, let us take two arbitrary rectangles within the square that are opposites and say one is connected to the left which we call a and another is connected to the right which we call b. Let X be a common point that lies on the edge shared between a and b.
If X belongs to their horizontal sides, say when a and b are passing over each other horizontally, then X lies on a horizontal splitting line along the common edge.
If X belongs to their vertical sides, say when a and b are meeting each other horizontally, then the lie on which X lies is not a splitting line. Consequently it intersects the interior of some rectangle. we call this line l.
we can assume an aribitrary rectangle c higher than both a and b that this line intersects. Let the lowermost point of c that lies on the line l be called Y. Then between Y and rectangles a and b, they may be buffer rectangles unless Y lies on a or b. If Y lies on a or b, then the top sides of two rectangles pass through Y and this provides a splitting line again.
If Y lies on two buffer rectangles a' and b' then they a' has to be to the left of b or b' has to be the right of a. Either way the buffer rectangles a' and b' are attached to the opposite sides and are opposites having a common point on l.
Since the top sides of the two rectangles pass through Y, we again have a splitting line.
The presence of a splitting line means the rectangles can be combined and there is at least one rectangle with edges on opposite sides.
Since we have proved that splitting lines exists in all cases, our arbitrary counterexample cannot hold. In such a case we have proved by contradiction that such dissection results in a rectangle having no points on the boundary of the square simply by eliminating splitting lines.
Q: A unit square is dissected into n > 1 rectangles such that their sides are parallel to the sides of the square. Any line, parallel to a side of the square and intersecting its interior, also intersects the interior of some rectangle. Prove that in this dissection, there exists a rectangle having no point on the boundary of the square.
A: We suppose the contrary that such dissection does result in a rectangle with no points on the boundary of the square. We will consider an arbitrary counterexample. We know that each rectangle is attached to at least one side of the square. No rectangle can be attached to opposite sides otherwise one of its sides lies on a splitting line.
We call two rectangles as opposite if they are attached to the opposite sides of ABCD. We claim that there exists two opposite rectangles having a common point.
Consider the union L of all rectangles attached to the left. and assume that they have no common points with the rectangles attached to the right. Now if we take a polygonal line P that connects the top and bottom of the square and passing close to the right boundary of L then it is easy to visualize that the rectangles of L do not have opposites per our assumption. This means there are rectangles to the right of P and before the rectangles attached to the right. We call them buffer rectangles. Some of these buffer rectangles are attached to the top and some are attached to the bottom. Consequently there is a point on P within the square where the top and the bottom rectangles meet. So there always exists a pair of opposite rectangles
and more importantly no buffer rectangles exist.
Having established that there are opposite rectangles within a square, let us take two arbitrary rectangles within the square that are opposites and say one is connected to the left which we call a and another is connected to the right which we call b. Let X be a common point that lies on the edge shared between a and b.
If X belongs to their horizontal sides, say when a and b are passing over each other horizontally, then X lies on a horizontal splitting line along the common edge.
If X belongs to their vertical sides, say when a and b are meeting each other horizontally, then the lie on which X lies is not a splitting line. Consequently it intersects the interior of some rectangle. we call this line l.
we can assume an aribitrary rectangle c higher than both a and b that this line intersects. Let the lowermost point of c that lies on the line l be called Y. Then between Y and rectangles a and b, they may be buffer rectangles unless Y lies on a or b. If Y lies on a or b, then the top sides of two rectangles pass through Y and this provides a splitting line again.
If Y lies on two buffer rectangles a' and b' then they a' has to be to the left of b or b' has to be the right of a. Either way the buffer rectangles a' and b' are attached to the opposite sides and are opposites having a common point on l.
Since the top sides of the two rectangles pass through Y, we again have a splitting line.
The presence of a splitting line means the rectangles can be combined and there is at least one rectangle with edges on opposite sides.
Since we have proved that splitting lines exists in all cases, our arbitrary counterexample cannot hold. In such a case we have proved by contradiction that such dissection results in a rectangle having no points on the boundary of the square simply by eliminating splitting lines.
No comments:
Post a Comment