Define a leg to be a maximal contiguous segment in the dissection (other than the sides of $R$); by assumption there need to be at least $n$ legs. The endpoint of each leg is the intersection of two corners; there are two endpoints and neither is a vertex of the rectangle $R$. Hence if $m$ is the number of rectangles (for a total of $4m-4$ usable corners), we deduce the inequality $4m -4 \ge 2 \cdot 2n$, hence $m \ge n+1$.

The rectangles cannot contain the points in their interior, but can have them as vertices or lying on their edges.

I had an incorrect solution: There must be at least $n$ lines in the rectangle $R$, so we use induction to prove that a rectangle $R$ with at least $n$ lines will have $n+1$ smaller rectangles. The induction solution uses the fact that if we start with any $n+1$ lines, we can 'remove' a line forming a configuration with $n$ lines, and thus we can apply the induction hypothesis. However, we cannot apply this argument to all configurations. Does anyone have any suggestions to how you can figure out that your argument does not cover all cases? Thanks!

Anyone know how? Thank you.

Hi, does this work?

@zhuangzhuang: How do you ensure that every possible dissection can be obtained by adding lines in that manner?

@zhuangzhuang unfortuately your statement that adding a line must increase the # of regions is false for example consider cutting a corner off a rectangle. If you get rid of one of the segments and extend the other there are 2 regions either way. here is the "official solution" (as in, the solution they gave at MOP) Notice that there must be at least $n$ line segments inside the big rectangle. Lemma 1: Each vertical/horizontal line segment inside the big rectangle must "stop" at 2 horizontal/vertical segments. Proof: The only way a line segment does not "stop" at two other horizontal segments is if two perpendicular segments "stop" when they meet. However, this is not possible as there is no way to "rectangulate" the region if this happens, so the lemma is true. Thus, for each vertical/horizontal segment, there are 2 corners. The total number of corners is then at least $4n$ plus the four corners on the big rectangle for a total of $4n+4$ However, each rectangle has 4 corners for a total of at least $n+1$ rectangles, as desired.

i don't know how can we disesected the rectangle R. can anyone help me? thank

Is this too easy or am I missing something.We know that $n$ distinct lines which intersect $R$ divides $R$ into $n+1$ regions.Now suppose that there exists such an arrangement of $n$ points in which there are atmost $n$ rectangles.Then there are atmost $n-1$ intersecting lines parallel to either the length or breadth of $R$.By PHP some line contains atleast two points and the line joining those two points are parallel to a side of $R$,a contradiction.

v_Enhance wrote: Define a leg to be a maximal contiguous segment in the dissection (other than the sides of $R$); by assumption there need to be at least $n$ legs. The endpoint of each leg is the intersection of two corners; there are two endpoints and neither is a vertex of the rectangle $R$. Hence if $m$ is the number of rectangles (for a total of $4m-4$ usable corners), we deduce the inequality $4m -4 \ge 2 \cdot 2n$, hence $m \ge n+1$. Mi idea is to proof that if you draw $n$ legs (a maximal contiguous segment in the dissection not divided by other segment) to make the disection, then you have at least $n+1$ rectangles, this is similar to v_Enhance´s idea. I proof this by induction. The case $n=1$ is easy. Suposse is true for $n=k-1$. Consider the case $n=k$. Consider a leg. Let $m_1$ the number of segments above the leg and ending at the leg, and $m_2$ the number of segments below the leg and ending at the leg (do not count the segments at the endpoints of the leg, only those touching the leg in its interior, also note that this numbers could be cero). Then this leg has al least $m_1+1$ rectangles above it and at least $m_2+1$ rectangles below it, a total of $m_1+m_2+2$ rectangles. Remove the leg (and extend the segments ending at the leg until they end in another leg). Now you have exactly $k-1$ legs, and in the space occupied by the $m_1+m_2+2$ rectangles now you have only $m_1+m_2+1$ rectangles. Since $m_1+m_2+2>m_1+m_2+1$ the number of rectangles before the leg was removed is $1$ more than than the number of rectangles after removing it. Since after removing it we have $k-1$ legs we have at least $k$ rectangles, then now we have at least $k+1$ rectangles, done. This also proofs that the number of rectangles is equal to the number of legs (with our definition of leg).

JackXD wrote: Is this too easy or am I missing something.We know that $n$ distinct lines which intersect $R$ divides $R$ into $n+1$ regions.Now suppose that there exists such an arrangement of $n$ points in which there are atmost $n$ rectangles.Then there are atmost $n-1$ intersecting lines parallel to either the length or breadth of $R$.By PHP some line contains atleast two points and the line joining those two points are parallel to a side of $R$,a contradiction. You said that $n$ distinct lines which intersect $R$ divides $R$ into $n+1 regions$, I think this is not so trivial. Also consider that not all the line segmants have to intersect $R$.

The problem implies that every point within $R$ must lie on the edge of some rectangle. Therefore, each point lies on a segment. Define a segment of a point $X$ to be the longest line segment that runs through $X$ that is part of the dissection of $R$. Each segment must have a termination i.e. has two endpoints. That means the segment will hit some line and form two $90^\circ$ angles. It cannot form only one right angle because then we would have a rectangle with a 270 degree angle...not possible. If we have four right angles formed, then that doesn't work out because then that isn't the true endpoint of the segment. Therefore, each endpoint contributes $180^\circ$. Furthermore, no two points can lie on the same segment therefore, each point contributes $360^\circ$. Therefore, the total angles of the rectangles (dissected) is $360n + 360$ where we add on an extra 360 from the right angles of $R$. This tells us that we need at least $n+1$ rectangles.

SL 2014 C1 wrote: Let $n$ points be given inside a rectangle $R$ such that no two of them lie on a line parallel to one of the sides of $R$. The rectangle $R$ is to be dissected into smaller rectangles with sides parallel to the sides of $R$ in such a way that none of these rectangles contains any of the given points in its interior. Prove that we have to dissect $R$ into at least $n + 1$ smaller rectangles. Proposed by Serbia Extend all segments made by the edges of the rectangles in the tiling to obtain $m$ distinct fault-lines. (excluding the sidelines of $R$). Let the tiling contain $k$ rectangles. Claim: $m \le k-1$. (Proof) Induct on $k \ge 2$ and observe the trivial base cases. Suppose the claim holds till $k-1$; now take a tiling with $k$ rectangles. Fix the bottom edge of $R$ and look at all the rectangles having a side on it. Pick one of them with the minimal height, say $A$. Accordingly, we perform either of these operations until they can no longer be done: If $A$ has an adjacent rectangle with equal height then merge them into one. If $A$ has a taller adjacent rectangle $B$, cut it along the top-edge of $A$ and merge the lower portion with $A$. Now cut out the bottom rectangle we obtain at the end of the process. Note that the number of fault-lines stays the same if we do (ii) and stays the same or goes down by $1$ when we apply (i). Suppose the latter happens in $\ell \ge 0$ cases. Thus, at the end, once we've chopped off $A$, we conclude that $m$ changes to at least $m-\ell-1$ (since we also lose the top-edge of $A$) while $k$ drops down to $k-\ell-1$ (since we also lose at least $A$ itself); so induction hypothesis applies and $m-(\ell+1) \le k-(\ell+1)-1 \implies m \le k-1$ and we are done. $\blacksquare$ Notice that each fault-line contains at most one marked point; thus, $m \ge n$. Applying the lemma, we conclude $k-1 \ge n \implies k \ge n+1$ as desired. $\blacksquare$ Remark: The idea is to (a) ignore the pesky points and consider the global fault-lines, (b) make local optimisations; picking $A$ along the bottom row provides a convenient way to not lose more rectangles than lines. As a sidenote; when it appeared in 2015 India IMO TST, nearly all approaches with a local premise failed because the points have a clumsy structure. Note that all attempts that failed had one thing in common: the configuration with five rectangles placed in a square in a "Swastik" shape is a counterexample! Remark: I enlist a bunch of other problems that can be solved using exactly the same local idea. ISL 2007 C2 Tournament of Towns, Spring 2009, Senior A, problem 1 RMM 2017/5

My proof : We notice that whenever two line segments intersect , they either form a T-intersection, a 4-way intersection( call it X-intersection) or an L-intersection (only at the corners of $ R $). Since no two points lie on the same line segment, we need at least $n $ lines. Therefore, it suffices to show that $ n $ line segments in a dissection ensure $ n+1 $ rectangles. Note that every line segment that we make has its endpoints on a T - intersection. So if there are $ n $ lines, then there are $2n $ T-intersections (no two line segments can have a common endpoint). Also, there are $4$ L-intersections; the ones at the corners of $R$. Suppose there are $ x $ X-intesections. We assign, to every point , a number which is equal to the number of rectangles of which it is a corner. Points at L-intersections get the number $1$, those at T -intersections get the number $ 2$, and points at X- intersections get the number $ 4$. The sum of all numbers should be equal to $4r $, where $r$ is the number of smaller rectangles in $R$. Therefore $$4r = 4 \cdot 1 + 2 \cdot 2n + 4x,$$or $$ r= n+ 1+ x \geq n+1 ,$$which finishes the proof.

My Proof: It's clearly that the points given should be on the lines of the dissection. The lines of the dissection are parallel to the sides of R and we must use at least n lines because no two selected points are on a line parallel to the sides of R. We define f(d)=(d+1)(n-d+1) where d is the non-negative difference between the number of lines parallel to vertical and the number of lines parallel to horizontal and f(d) is the number of smaller rectangles obtained in the dissection.For example , f(n)=n+1 , f(0)=n+1 , f(1)=2n , f(2)=3(n-1) , f(n-1)=2n. We have to find the minimum of f(d) and because f is a quadratic function with neagative leading coefficient it's minimum is at f(0) or at f(n).(that's because f:{0,1,...n} -> N) We conclude that the minimum of f is f(0)=f(n)=n+1.

Does this work? We prove the following more general statement, by strong induction on $n \ge 0$: Let $P$ be a polygon whose interior angles are all $90^\circ$ or $270^\circ$ (i.e. its sides are all aligned with a pair of perpendicular axes). Choose $n$ points inside $P$, no two of which lie on a line parallel to either axis, and partition $P$ into rectangles such that none of the points lies in the interior of any rectangle. Then any such partition must have at least $n+1$ smaller rectangles. For $n=0$, the statement is clearly true. Now assume the statement holds for all $0 \le n < k$, and consider some $P$ with $n=k$ interior points. Pick one of those points, call it $p$. Since $p$ lies in none of the smaller rectangles, it must lie on a line segment, which must itself be part of some path connecting two distinct points on the boundary of $P$. This path divides $P$ into two pieces with $a$ and $b$ sides, respectively, where $a, b \ge 0$ and $a+b = k-1$; furthermore, all of these sides are also aligned with the axes. Thus, applying the inductive hypothesis, the total number of smaller rectangles is at least \[(a+1) + (b+1) = (a+b) + 2 = k + 1\]which completes the induction. $\blacksquare$

I'm having trouble understanding the problem statement. Can someone explain what it is saying?

For $n = 2$, we might have 2 points in the rectangle as follows: [asy][asy] size(2cm); draw((0,0)--(1,0)--(1,1)--(0,1)--cycle); dot((0.3,0.4)); dot((0.7,0.5)); [/asy][/asy] When we dissect the rectangle, the points can't be in interiors, meaning they have to be on boundaries. So a valid way to partition the larger rectangle into rectangles might be: [asy][asy] size(2cm); draw((0,0)--(1,0)--(1,1)--(0,1)--cycle); dot((0.3,0.4)); dot((0.7,0.5)); draw((0.3,0)--(0.3,1)); draw((0.3,0.5)--(1,0.5)); [/asy][/asy] This partition has at least $n + 1$ (aka 3) rectangles, as the problem requires.

Thanks. I understand now.

does this work? Suppose there are k rectangles and $m\ge n$ segments; in total, the rectangles cover $4k-4$ endpoints (excluding corners of the large rectangle). On the other hand, each endpoint is the intersection of at least two segment, and there are two endpoints on any of the m segments, hence we have $4k-4\ge2\cdot2m\ge4n\implies k\ge n+1$.

We prove the contrapositive. Claim: A $n$ rectangle dissection of $R$ has at most $n-1$ distinct segments (as in different $x$ or $y$ coordinate). Proof. We prove this inductively. If any two rectangles share a segment, we can directly merge the two of them. Now, we can take the minimal height rectangle on one of the sides, then hydraulic press it out of existence, potentially removing some point as well. $\blacksquare$

Every maximal segment has $2$ corners and there are at least $n$ maximal segments so there are at least $2n$ corners from maximal segments and another $4$ from the original rectangle. The corners from maximal segments are a part of at least $2$ rectangles and the $4$ corners from the original rectangle are a part of $1$ rectangle. Since each rectangle has $4$ corners, there are at least $\frac{2(2n)+4}{4}=n+1$ rectangles, as desired.

YaoAOPS wrote: We prove the contrapositive. Claim: A $n$ rectangle dissection of $R$ has at most $n-1$ distinct segments (as in different $x$ or $y$ coordinate). Proof. We prove this inductively. If any two rectangles share a segment, we can directly merge the two of them. Now, we can take the minimal height rectangle on one of the sides, then hydraulic press it out of existence, potentially removing some point as well. $\blacksquare$ Bruh u fakesolved (think of the arrangement with four 2x1 rectangles arranged cyclically along the side of a 3x3 square)

My solution works for that arrangement

Any point lies on the sides of a rectangle, so we need to n sides inside R and that give at least n+1 rectangle iff there aren't intersections between any two sides.

We consider the planar graph formed by the edges along the drawn lines and vertices at the intersetion points. Observe that each vertex of this graph other than the four corners of the rectangle has degree at least $3$. (Roughly, two segments can't ``end" at the same point.) Hence we have $\operatorname{totdeg} \geq 3(V-4) + 4 = 3V-4$ or $E \geq \frac 32 V - 2$. Furthermore, since there exists a distinct segment $s_i$ passing through each point $P_i$ by hypothesis, each such segment contributes $2$ distinct vertices. It follows that there are at least $V \geq 2n+4$ vertices (including the four corners), thus \[F = E+2-V \geq \frac 12 V \geq n+2\]which means there are at least $n+1$ interior faces, as needed.

Use induction with $n = 1$ being true. Then consider taking the point that is the farthest left. Notice that the rectangle passing through this point can be extended to have a side length that is the left side of $R$, without violating any of the conditions or increasing/decreasing the number of rectangles in $R$. Thus we can remove this rectangle and induct down to $n-1$, so we are done.

Solved with BZB Let $n = 1$ be true Because $n = 1$ is true we know drawing a line between a point will create at least 2 line segments such a construction is here[asy][asy] size(2cm); draw((0,0)--(1,0)--(1,1)--(0,1)--cycle); dot((0.5,0.5)); draw((0.5,0)--(0.5,1)); [/asy][/asy] We know that by adding more points to such a diagram we cannot decrease the amount of rectangles and only increase them. Since for $n = 1$ the smallest possible partions of the larger rectangle is 2. For $n = 2$ we cannot have any less than 2 partions. So $m$ the total number of partions can be $m \ge n$ where $n$ is the number of lines. To complete we must prove $m \neq n$ this is clear by simply drawing a diagram and showing that with $n$ points you cannot construct $n$ partions of the larger rectangle this is because for the minimum $n = 1$ points drawn the minimum amount of partions is two rectangles. Inducting upwards we see that the total amount of partions must satisfy $m > n \implies m \ge n+1$, this is true because $m$ must be a whole number.

We will use induction. When $n=1$ we can just draw a line parallel to two sides of the rectangle that passes through the point, to create $1+1=2$ rectangles. Now assume that with $k-1$ points, we need to draw at least $k$ rectangles. Consider a rectangle with $k$ points in its interior. WLOG we fix its orientation. Then take the leftmost one, which is unique by the problem statement. Draw a line perpendicular to the horizontal bases through the leftmost point. What remains to the right is an rectangle with $k-1$ points in its interior. Therefore, we have to draw at least $k$ more rectangles, bringing our total count to at least $k+1$ rectangles. This completes our induction. P.S. n+1 is always achievable if we draw $n$ lines parallel to two of the sides and all parallel to each other.

Let there be $r < n + 1$ rectangles, we show we cannot possibly form such a dissection. Each of the $n$ points must lie on the segment of some rectangle in the dissection. Extend these segments, by the problem condition none of these $n$ lines can be the same line. We then bound the number of distinct lines that can be drawn that contain a segment of the dissection. We count the lines that form the sides of the rectangle and remove them later. Consider the vertices of the dissection. Clearly every vertex can be an endpoint of $2,3,$ or $4$ segments. Each of the lines that is drawn contains a segment, and thus passes through at least $2$ vertices. Call a vertex good if is extremal on the line that it lies, (if the line is horizontal, there either exist no vertices to the left or no vertices to the right of the vertex, or if the line is vertical there either exist no vertices above or no vertices below the vertex). Every line must then have exactly $2$ extremal vertices. In other words, the number of pairs of the form (extremal vertex, corresponding line) is exactly twice the number of rectangles. Now if a vertex is an endpoint of $4$ segments, there exists an endpoint above it, below it, to the left of it, and to the right of it, so it cannot be an extremal vertex. If a vertex is an endpoint of $3$ segments, it can be an extremal vertex of at most $1$ line (specifically the direction that goes only has one segment attached, the other one has a endpoint on both sides). If a vertex is an endpoint of $2$ segments, it can be an extremal vertex of at most $2$ lines, one in each direction. Now let the number of vertices with $2, 3,4$ segments attached be $x,y,z$. We wish to bound $2x + y$, which is the maximal number of pairs of the form (extremal vertex, corresponding line). We now double count the number of pairs of the form (vertex, corresponding rectangle). Counting by each rectangle gives $4r$ pairs. Counting by each vertex gives $x + 2y + 4z$ pairs, so we can write $x + 2y + 4z = 4r$. Lastly, we prove $x = 4$, namely the only vertices with two segments attached are the corners of the rectangle. This is trivial, just take a infinitely small square on the opposite side of the vertex from the two segments, then that square must be part of both the rectangles crossing the vertex in the horizontal and vertical directions, contradiction. We then want to bound $y + 8$ given $2y + 4z = 4r - 4$, or $y + 2z = 2r - 2$, so $y + 8 = 2r - 2z + 6$. The number of pairs of the form (extremal vertex, corresponding line) is then at most $2r - 2z + 6$ which is at most $2r + 6$, since $r < n + 1$ we see this is less than $2(n + 4)$, so there are less than $n + 4$ lines. Eliminating the $4$ lines that form the rectangle, this forces that there are less than $n$ lines inside the rectangle that contain some segments, so we cannot possibly place $n$ points on the segments inside the rectangle, since two of them would lie on the same line.

Consider all interior segments formed by the dissection. No points can be on the same segment, so there are at least $n$ segments. At its ends, each segment contributes $360^\circ$ of rectangle vertices, and the four vertices of $R$ add another $360^\circ$, so there must be at least $n+1$ rectangles.

Solution using induction. v_Enhance wrote: Define a leg to be a maximal contiguous segment in the dissection (other than the sides of $R$). Note that our dissection must have at least $n$ legs (each point lies on either 1 or 2 legs (the latter case happens if the point is on the corner of some rectangle), so at least $n$ legs are needed). We show inductively that if any dissection of $R$ admits $n$ legs, then it must contain at least $n+1$ rectangles. Without loss of generality, consider a horizontal leg $\ell$, which must be bounded by two vertical legs $k_l$ and $k_r$. Suppose that there are $a$ vertical legs with an endpoint on $\ell$ lying above it and $b$ vertical legs with an endpoint on $\ell$ and lying below it. Let these legs be $c_1,c_2,\dots,c_a$ and $d_1,d_2,\dots,d_b$ respectively, and set $c_0=d_0=k_l$ and $c_{a+1}=d_{a+1}=k_r$. For each $0\le i\le a$, let $C_i$ be the rectangle bounded by $\ell$, $c_i$, $c_{i+1}$, and some horizontal leg. Similarly, for all $0\le i\le b$, let $D_i$ be the rectangle bounded by $\ell$, $d_i$, $d_{i+1}$, and some other horizontal leg. Let $P$ be the union of all the $C_i$ and all the $D_i$. Then $P$ is dissected into exactly $a+b+2$ rectangles. Remove $\ell$, and in $P$ extend the $c_i$ and $d_i$ until they hit some horizontal leg, which redissects $P$ into at most $a+b+1$ rectangles (equality holds most of the time; if $c_i$ and $d_j$ are part of the same line for some $i,j$ (which is very inefficient) we get at most $a+b$ rectangles). We finish by induction hypothesis. $\blacksquare$ Clarifying example:

We proceed with induction on $n.$ The base case is trivial, so assume that the proposition holds for $n=k$ for some positive integer $k.$ Then if we have $k+1$ points, consider the left-most point, clearly there is a rectangle to the left of it, with the point on its perimeter. Then we can extend the rectangle up and down, and to the left, and then shorten/eliminate the other rectangles as appropriate. Then we can ignore the left side, and we are left with $k$ points in a rectangle, and we may finish by the inductive hypothesis. QED

For each point $(x_i,y_i)$, we must have at least one segment of the dissection lying on either $x=x_i$ or $y=y_i$, so we have at least $n$ interior segments. We bound the total number of degrees contributed by the rectangles, which is clearly equal to $360R$. Notice each interior segment contributes 360 degrees to the degree sum when it intersects with perpendicular segments at its endpoints, the corners collectively contribute 360 degrees, and more if two segments are perpendicular in their interior, so we have \[360R \ge 360n + 360 \implies R \ge n+1. \quad \blacksquare\]