May be I dont understand the question correctly. I have the rectangle ABDC. I draw two parallel lines EF and GH parallel to AB.This partitions the rectangle ABDC into ABFE,EFHG,GHDC. Now I draw the line IJ that passes that has some points common with interior of each of the rectangles. But all the three rectangles have common points with the boundary of ABDC.

freemind wrote: Given that any line parallel to one of the sides of $ D$.... In particular, your line EF fails this condition.

Joel writes: Line EF fails the condition. There is some confusion regarding whether EF shares some interior points with a rectangle. 1.Considering the way I drew lines in rect.jpg (see my previous post), when EF is drawn there is no other line drawn previously,so it is not in the interior of any rectangle (of course exempting ABCD). 2.When I later draw GH, does EF not lie in the rectangle ABHG ? If (2) is not accepted, then the only way to make the initial line EF (which by a priori does not lie within a rectangle) lie within a rectangle is by drawing four lines, two on either sides of EF and parallel to EF and two perpendicular to EF ,all in the interior of ABCD. The rectangle defined by these four lines has no common points with D's boundary.

srikanth wrote: 2.When I later draw GH, does EF not lie in the rectangle ABHG ? "Partition" means non-overlapping parts. And your comment that follows isn't a proof of anything.

An answer without word Domi

Another solution, I think:

Did you all understand what Domi meant? I'm asking because, I solved the problem myself first, which I believe is the exact same thing Domi meant (I think I understand what he meant now) But I am at a loss about how to write out such a solution in a contest. Would someone check the solution I wrote out, like a grader in a contest and suggest something to do better? Or is a solution like this not allowed at all?

I really want replies, especially from experienced people like Dariz etc.

The "traveling" solution is really awesome... here's my much less inspiring solution though... Assume for the sake of contradiction that all rectangles touch a side of $D$, and WLOG scale so that $D$ is the unit square $[0,1]\times[0,1]$. Because no fault lines exist, no rectangle can touch opposite sides of $D$. Let $P=\{P_1,\ldots\}$ and $Q=\{Q_1,\ldots\}$ (from top to bottom) be the rectangles touching the left and right sides of $D$, and let $U=\{U_1,\ldots\}$ and $V=\{V_1,\ldots\}$ (from left to right) be the rectangles touching the upper and lower sides of $D$ (we have $|P\cap Q|=|U\cap V|=0$). Let $f(R),g(R)$ denote the width and height of rectangle $R$, respectively (width is horizontal and height is vertical). Case 1: $f(P_i)+f(Q_j)\le1$ and $g(U_k)+g(V_l)\le1$ for all $i,j,k,l$. WLOG $f(P_i),f(Q_j),g(U_k),g(V_l)$ are maximal. Consider the region \[X=[f(P_i),1-f(Q_j)]\times[g(V_l),1-g(U_k)].\]Since $X$ is uncovered by assumption, it must be a point or a line segment; WLOG $f(P_i)=1-f(Q_j)$. To prevent $x=f(P_i)$ from being a fault line, we need it to intersect the interior of, WLOG, $U_m$. WLOG $i,j$ are minimal; then WLOG $P_i$ and $U_m$ touch on $y=1-g(U_m)$ and the top of $Q_j$ lies strictly below $y=1-g(U_m)$. Now consider the region $Y$ formed by $x=f(P_i)$, the right sides of $U_m$ and $P_i$, and the upper side of $Q_j$. Clearly $Y\cap(P\cup U\cup V)=\emptyset$. But by the minimality of $j$, $Y\cap Q=\emptyset$ also, so $Y$ is left uncovered. Case 2: Otherwise, WLOG $f(P_i)+f(Q_j)>1$ for some $i,j$. WLOG $P_i$ is above $Q_j$ and $j-i$ is minimal. $P_i$ and $Q_j$ don't touch or else we get a fault line, so consider the region $X$ bounded by the lower and right sides of $P_i$ as well as the upper and left sides of $Q_j$. By the minimality of $j-i$, $X$ and $P\cup Q$ are disjoint. But clearly $X$ and $U\cup V$ are disjoint as well, so $X$ is uncovered.

Nice Problem! It's a bit hard to explain without pictures. I hope my presentation exhibits clarity. For any two rectangles in the dissection, if they share a boundary completely, delete this common boundary so as to merge them into one rectangle. Apply this operation until it can no longer be done. Note that the final dissection is non-trivial and has the stated property of the original one. Let $D_1, D_2, \dots, D_n$ (for $n \ge 2$) be rectangles having a side common with the lower boundary of $D$. Assign each $D_i$ a height $h_i$ and note that all heights are distinct. Take the rectangle $D_k$ having the least height among them. Note that at least two rectangles touch the upper side of $D_k$ and clearly, one of them has no common points with the boundary of $D$, as required. $\, \square$

Consider the lowest height for all rectangles with one side on the bottom side of $D$ . For that height, draw in a parallel line. Do the same thing for all four sides of $D$. By the problem condition, no two of them completely coincide. Let the rectangle created by the lines we drew in be $E$. First off, the corners of $E$ must be covered by rectangles not completely outside of $E$. Consider, wlog, the topmost possible rectangle who's rightmost side is on rightmost side of $D$ that which is also touching the right side of $E$. Since it is the topmost one, the rectangle above it must extend past the right side of $E$. This creates a "corner" inside $E$. Now consider the rectangle in the partition with this corner. Its bottom side must not be past $E$'s bottom side (by our choice of $E$). Its left side cannot be past $E$'s left side unless it touches the left side of $D$ which is impossible by the problem condition. Hence we created a rectangle entirely inside $E$ and by construction $E$'s sides don't touch $D$'s sides and we are done.

BTW, post #6, #8 is really nice

Say the opposite is true. Define a faultline as an edge of a rectangle involved in the partition of the square and a rectangle in the partition of the square as a fiber. Call a faultline major , if it starts from an edge of the square and ends at the opposite edge of the square and call a fiber, a k-fiber if it has k edges on the boundary. Note that, for the question property to follow, there can not be any majors in the partition of the square, because if there were, then the major itself is a line intersecting the square but not intersecting any fiber. So, No majors and no 0-fibers. Note that this immediately implies that there cannot be any fibers having 3 edges on the boundary. As 0 (a 0 fiber) and 4 (the square itself) are not allowed, there can only be two types of fibers in the partition: (i)Fibers having one edge on the boundary and (ii)fibers having two edges on the boundary. Note that there are exactly 4 fibers of the type (ii) in the partition (Ignoring those cases where there are two or three total fibers in the partition itself). Delete these 4. Then you can have residual shapes similar to (i)the white part and the stuff inside it in the figure, (ii)shape remaining in the white part and the stuff inside it in the figure after cutting along one of the red lines, (iii)shape remaining in the white part and the stuff inside it in the figure after cutting along two of the red lines and (iv)shape remaining in the white part and the stuff inside it in the figure after cutting along three of the red lines (If you cut all the red lines, then the remaining figure itself is a 0 fiber). Note that the region colored purple cannot be covered by any 1-fiber(the only allowed fiber now). So, the partition is incomplete(This argument needs a little bit of tweaking if you consider some special configurations. But all those tweaks are very natural). Contradiction! (In the figure, the rectangles filled black are the 4 2-fibers which were deleted, and the dotted blue lines refer to the possible 'range of covering' of the 1-fibers)

We'll prove that if there is no interior rectangle, then there is some line parallel to the sides that touches the interior of $D$, but does not touch the interior of any of the partition rectangles. Call such a line good. The first reduction comes from the idea of Combinatorial Optimization. We claim that we may assume without loss of generality that no two partition rectangles exactly share a side. Indeed, if two rectangles did exactly share a side, we could combine them into one rectangles, as that would make the partition strictly harder than before. Consider all the rectangles that touch the leftmost side of $D$. If there is only such one rectangle, then the rightmost side of this rectangle is a good line, so we're done. Thus, we may assume that there are at least two. Starting from the top, let the rectangles be $r_1,r_2,\ldots,r_n$, with lengths $x_1,\ldots,x_n$ and heights $y_1,\ldots,y_n$. Note that $x_i\ne x_{i+1}$, else they would exactly share a side. The key idea is to select the $r_i$ with smallest $x_i$ (if there are many, pick one arbitrarily). There are two cases. Case 1: The smallest $x_i$ is either $x_1$ or $x_n$. Due to symmetry, we may assume that it is $x_1$. [asy][asy] draw((0,0)--(0,1.5)); draw((0,1.5)--(3,1.5)); pair A=(1.2,1.2); draw(A--(0,1.2)); draw(A--(1.2,1.5)); draw(A--(2,1.2)--(2,0.8)--(0,0.8)); label("$x_1$",(0.6,1.35)); label("$x_2$",(0.6,1)); dot("$A$",A,dir(-90)); label("$\vdots$",(0,-0.1)); label("$\vdots$",(0.6,0.6)); label("$\cdots$",(3.3,1.5)); [/asy][/asy] Since $x_2\ne x_1$, we have $x_1<x_2$ (this is all we need in fact). Consider the corner $A$ in the picture above. Let $E$ be the rectangle with bottom left corner $A$. We see that $E$ must have one of its edges on a side of $D$. That edge cannot be $E$'s left or bottom edge. If it's $E$'s top edge, then the height of $E$ is exactly $y_1$, so $E$ and $r_1$ exactly share a side, which is not allowed. If it's $E$'s rightmost edge, then the bottom edge of $E$ (the horizontal line through $A$) is good, so we're done. Case 2: The smallest $x_i$ is not $x_1$ nor $x_n$. Then, we have $x_i<x_{i-1},x_{i+1}$. [asy][asy] draw((0,0)--(0,2.5)); draw((0,1.5)--(1.2,1.5)); pair A=(1.2,1.2); draw(A--(0,1.2)); draw(A--(1.2,1.5)); draw(A--(2,1.2)--(2,0.8)--(0,0.8)); draw((0,1.5)--(2.5,1.5)--(2.5,2)--(0,2)); label("$r_i$",(0.6,1.35)); label("$r_{i+1}$",(0.6,1)); label("$r_{i-1}$",(0.6,1.75)); dot("$A$",A,dir(-90)); label("$\vdots$",(0,-0.1)); label("$\vdots$",(0.6,0.6)); label("$\vdots$",(0.6,2.4)); label("$\vdots$",(0,2.8)); [/asy][/asy] Again, let $E$ be the rectangle with bottom left corner $A$. This time, the only edge of $E$ that could touch a side of $D$ is $E$'s rightmost edge. Then, we see that the horizontal line through $A$ is good, so we're done. This completes the proof.

Is this true and clear? I am having trouble with writing combinatorics solution so I would be glad if you help me. In a partition we will perform the following move as far as we can: If there exists two rectangles with the same edge(call these a couple) delete this edge. Observe that assumptions are still true in the modified partition. We will prove that there exists a rectangle which does not touch any side of $D$. Assume that there does not exist such rectangle. $D$'s corner' cordinates are $(0,0),(0,m),(n,0),(n,m)$. There is a rectangle $A$ which has $(0,m)$ as a corner. $(c,m)$, $c\neq 0$, is a corner of $A$. $(c,m)$ is a corner of $B$. $d(A,x-axis) \neq d(B,x-axis)$ -$d()$ is distance- because of the moves we performed. $i)$ $d(A,x-axis) < d(B,x-axis)$ Rectangle $C$ has corner $(c,k)$ where $(c,k)$ is a corner of $A$ different from $(c,m)$. If $C$ touches $x$-axis, then there exists a line $x=c$ does not pass through interior of a rectangle. If $C$ touches $y$-axis then there is a couple. Contradiction. $ii)$ $d(A,x-axis) > d(B,x-axis)$ $(c,k)$ is a corner of $E$. If $E$ touches $x$-axis then there exists a line $x=c$ does not pass through interior of a rectangle. If $E$ touches $x=n$, we have the same situation in $i)$. This is because we can treat all rectangles between bottom line of $E$, $x=c$ as a one big rectangle (call this new rectangle $F$) and $d(A,x-axis) \neq d(F,x-axis)$. Both $A$ and $F$ are corner rectangles so we can choose one of them to be $A$ in $i)$. Contradiction.

Assume, for the sake of contradiction, that there exists a partition where every rectangle has common points with $D$'s boundary and no line parallel to one of the sides of $D$ is made entirely of boundaries of rectangles of the partition. Suppose there are $k$ rectangles in this partition. Each rectangle touches the boundary and thus has two vertices on sides of $D$ (not counting corners, there are two cases, both of which have two vertices on the side). Since each side vertex is the vertex of two rectangles, there must be $k$ side vertices. Using the parallel line condition, for each side vertex, there must be an interior vertex found by traversing the line through the side vertex parallel to other sides of the rectangle, and it must be a vertex of two different rectangles of the partition and on the side of a third. Additionally, each interior vertex can only correspond to one side vertex, which is uniquely found by traversing the line through it perpendicular to the side it is on. Thus, there must be $k$ interior vertices. If we count the total number of rectangle-vertices, we see that each side vertex is $2$ and each interior vertex is $2$. Additionally, the $4$ corners must also all be vertices of rectangles. This totals to $4k+4$ vertices. However, there are only $k$ rectangles, so there should only be $4k$ vertices. This is a contradiction, as desired.

Call a point nontrivial if it is a vertex of a rectangle in the partition, but not a vertex of $D$. Call a line segment good if it connects two nontrivial points it is contained within an edge of a rectangle there are no nontrivial points on the interior of it and it is not on the boundary of $D$. Create a graph with vertices as nontrivial points and edges as good line segments. In this graph, we keep the notion of direction. A vertex has degree one in this graph if and only if it is on the boundary of $D$. All other vertices have degree three or four. Start on one of these vertices and apply the following algorithm repeatedly: Walk straight until you can't. By the condition of the problem, we are not on the boundary of $D$. Then, look to the left and right, which both must have paths. If both of these paths lead straight to a vertex of degree one, contradiction with the condition of the problem. Turn in whichever direction that doesn't lead to a dead end. Since this algorithm never ends, and traces out a path in which no edge is backtracked, there exists a cycle. We are done.

By scaling and rotating $D$ appropriately, let us assume without loss of generality that $D$ is exactly the unit square with vertices at $(0,0)$, $(1,0)$, $(0,1)$, and $(1,1)$ in the coordinate plane., so that every line segment involved in the partition of $D$ is either horizontal or vertical. Also, let us refer to a line segment as being involved in our partition iff it is strictly contained in $D$ and is also a side of some rectangle of the partition of $D$. Let a splitting segment be a line segment involved in our partition such that its endpoint set is either of the form $\{(0,k),(1,k)\}$ or $\{(k,0),(k,1)\}$, where $0<k<1$. If there exists some splitting segment in $D$, then the line given by the extension of our segment has common points with the interior of $D$ but has no nonempty intersection with the interior of any rectangle in our partition, contradicting the given properties of our partition; it is also easy to see that the converse of the same observation holds as well. Hence our given condition is equivalent to the restriction that $D$ has no splitting segments at all. Consider an infinite abyss surrounding $D$, so that it occupies every point on or outside $D$. Suppose that there exists a hedge maze strictly contained in the interior of $D$, with paths located exactly at the segments involved in our partition of $D$ and vision-obscuring hedge located at all other points. Because our partition of $D$ contains no splitting segments, there does not exist any straight, unbending path connecting one side of the hedge maze to its opposite side, with both sides touching the abyss. Now, place a robot on some path of our hedge maze. We program it according to three rules: first, if our robot is walking in some direction, it will continue walking until it either reaches the edge of the abyss or meets a hedge; second, if the robot reaches the abyss, it will immediately backtrack by walking along the same path in the opposite direction; third, if the robot hits a hedge, then it must have come to a T-shaped crossroad, so let our robot turn left and continue walking. For the third rule, note that L-shaped crossroads are impossible by nature of our partition of $D$ into smaller rectangles. Due to the above three rules, one can easily see that the path of the robot is well-defined. In addition, observe that the robot can never stop walking, as our three rules prevents it from halting or falling into the abyss. Since our hedge maze is finite, we deduce that the robot must eventually cycle around a polygon $P$, such that its edges correspond to paths in the maze. Furthermore, our partition of $D$ into smaller rectangles does not form any splitting segments, so we find that any segment involved in our partition must intersect some other segment going in a perpendicular direction. Hence, our robot cannot endlessly pace back and forth along some fixed path, and so that $P$ is of nontrivial area. Using the above observations, it follows that the robot must eventually cycle around a polygon $P$ of nontrivial area, such that its edges correspond to paths in the maze. But this implies that $P$ is formed by segments involved in our partition and has no common points with the boundary of $D$. By definition, $P$ must clearly be composed of at least one rectangle in our partition of $D$; these rectangles have no common point with the boundary of $D$, as desired. $\blacksquare$

welp hopefully not a fakesolve Use proof by contradiction; suppose that every rectangle touches the boundary of $D$ and also that there is no line crossing two opposite sides of $D$. First some basic information. There are four distinct rectangles at each of the four corners of $D$. Consider any side of $D$. The rectangles touching this side have heights $h_1,\dots,h_n$, where $h_1$ and $h_n$ represent the corner rectangles. We can actually find that $h_i<\min\{h_{i-1},h_{i+1}\}$ is impossible. In particular, the sequence has a single peak at $h_k$ for some $k$ (which is allowed to be $1$ or $n$) with $h_1\le \dots \le h_k\ge \dots\ge h_n$. Now for the meat of the proof. Consider the "mountains" with bases on the left and right sides. Let $\ell$ be the distance from the left peak to the left side. Define $r$ similarly. We must have $\ell+r$ be less than the horizontal side length of $D$. Repeat the same argument for the mountains with bases on the top and bottom sides. Thus there exists some empty rectangular space in the interior of $D$, a contradiction. Seems too good to be true.

We prove the contrapositive: given a partition in which each rectangle touches $D$'s boundary, we will cut $D$ into two rectangles.

in the partition that border each other and both border the left edge of $D$; by our initial assumption, these rectangles have different widths: [asy][asy] unitsize(0.8cm); draw((0,0)--(0,5)--(5,5)--(5,0)--cycle); filldraw((0,1)--(2.5,1)--(2.5,2)--(0,2)--cycle, lightgreen, black); filldraw((0,2)--(2,2)--(2,3)--(0,3)--cycle, lightblue, black); draw((0,2)--(2,2), black+linewidth(2)); dot((2,2), black+6); [/asy][/asy] Consider the other rectangle in the partition with a corner at the marked dot. This rectangle must either border the right side of $D$ or the top side of $D$; in the former case, we already have our desired line; the latter case is actually impossible due to our initial assumption, as we have a set of rectangles forming a larger rectangle: [asy][asy] unitsize(0.8cm); draw((0,0)--(0,5)--(5,5)--(5,0)--cycle); filldraw((0,1)--(2.5,1)--(2.5,2)--(0,2)--cycle, lightgreen, black); filldraw((0,2)--(2,2)--(2,3)--(0,3)--cycle, lightblue, black); filldraw((2,2)--(4,2)--(4,5)--(2,5)--cycle, lightred, black); draw((0,5)--(4,5)--(4,2)--(0,2)--cycle, linewidth(2)); [/asy][/asy]

Define a rectangle to be $\textit{down}$ if it is touching the bottom side of the rectangle, likewise we defined $\textit{left}, \textit{right}, \textit{up} $ rectangles. The problem is asking us to prove if there are no lines for which the entire intersection of the line and the rectangle is spanned by boundaries of rectangles in the dissection, then there is at least one rectangle that is not up, down, left, or right. We then prove the contrapositive: if all rectangles are up, down, left, or right, then some line exists whose entire intersection with the rectangle is spanned by boundaries of rectangles in the dissection. We also only consider dissections that have no two rectangles that can be combined into one by removing one segment, clearly if we prove it for just these dissections it clearly extends for the other ones (we can transform other dissections into these by just combining said rectangles, clearly if there is such a line in the transformed dissection there is one in the original) Consider the set of all left rectangles, and take one with a local minimum width. Note that no two adjacent left rectangles can have the same width since these rectangles can be combined by removing one segment, so there must be a local minimum width. If the rectangle is right, we get such a line and we are done. If said rectangle is both left and up or left and down, we consider the rectangles to its direct right. If any rectangle is not up or down, it must be right, meaning that either it borders the left rectangle adjacent to the said rectangle, or there is a rectangle between it and the said left rectangle, and clearly such a rectangle must be right since if it were up or down it would pass through the said right rectangle. This forces such a line to exist. Otherwise, if there exists no right rectangles directly adjacent to the said left rectangle, we can see that there is an up or down rectangle that has the same height and completely borders the height of the said left rectangle, which is impossible by our assumption. Otherwise, considering the rectangle that borders the width of the adjacent left rectangles, we see that this rectangle must be right, thus considering the border of this rectangle and the adjacent left rectangle we see that the line going through this border fully extends to the right edge of the rectangle via the border of said right rectangle and the adjacent left rectangle, done.