IMO Shortlist 2014 C1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

hajimbrak

209 posts

hajimbrak

#1 h Jul 11, 2015, 8:23 AM • 9 Y

Y by anantmudgal09, Davi-8191, tenplusten, Combi12345, Combi1234, mathleticguyyy, megarnie, Adventure10, Mango247

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

This post has been edited 1 time. Last edited by hajimbrak, Jul 23, 2015, 10:42 AM
Reason: Added proposer

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6877 posts

v_Enhance

#2 h Jul 11, 2015, 4:43 PM • 19 Y

Y by anantmudgal09, AdithyaBhaskar, emiliorosado, RadioActive, va2010, Tommy2000, MSTang, tenplusten, Combi12345, mathleticguyyy, Aryan-23, Alex_z_Awesome, math31415926535, megarnie, HamstPan38825, Mogmog8, Adventure10, Mango247, iamnotgentle

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DominicanAOPSer

31 posts

DominicanAOPSer

#4 h Jul 13, 2015, 3:37 AM • 7 Y

Y by AnonymousBunny, Smita, Booper, Arhaan, Combi12345, Adventure10, sabkx

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathPanda1

1135 posts

MathPanda1

#5 h Jul 30, 2015, 1:32 AM • 1 Y

Y by Adventure10

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!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathPanda1

1135 posts

MathPanda1

#6 h Aug 1, 2015, 10:06 PM • 2 Y

Y by Adventure10, Mango247

Anyone know how? Thank you.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

zhuangzhuang

679 posts

zhuangzhuang

#7 h Aug 11, 2015, 12:48 AM • 3 Y

Y by Smita, Adventure10, Mango247

Hi, does this work?

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

hajimbrak

209 posts

hajimbrak

#8 h Aug 11, 2015, 3:26 AM • 2 Y

Y by biomathematics, Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

stephcurry

2095 posts

stephcurry

#9 h Aug 11, 2015, 3:45 AM • 8 Y

Y by fatblotoutsun, siddigss, sa2001, Nelu2003, IceWolf10, Adventure10, Mango247, BVKRB-

@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.

This post has been edited 1 time. Last edited by stephcurry, Aug 11, 2015, 3:51 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jindoak10

59 posts

jindoak10

#10 h Aug 12, 2015, 1:27 PM • 2 Y

Y by Adventure10, Mango247

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

This post has been edited 1 time. Last edited by jindoak10, Aug 12, 2015, 1:28 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JackXD

151 posts

JackXD

#11 h Aug 29, 2015, 6:05 PM • 2 Y

Y by Adventure10, Mango247

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.

This post has been edited 1 time. Last edited by JackXD, Aug 29, 2015, 6:06 PM
Reason: xx

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

emiliorosado

8 posts

emiliorosado

#12 h Sep 18, 2015, 12:20 PM • 3 Y

Y by Adventure10, Mango247, smileapple

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).

This post has been edited 1 time. Last edited by emiliorosado, Sep 20, 2015, 11:27 PM
Reason: more information

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

emiliorosado

8 posts

emiliorosado

#13 h Sep 18, 2015, 12:59 PM • 3 Y

Y by Adventure10, Mango247, sabkx

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$ .

This post has been edited 1 time. Last edited by emiliorosado, Sep 20, 2015, 11:24 PM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

fclvbfm934

759 posts

fclvbfm934

#14 h Sep 24, 2015, 4:22 AM • 3 Y

Y by Booper, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

anantmudgal09

1980 posts

anantmudgal09

#15 h Nov 26, 2015, 1:09 PM • 12 Y

Y by biomathematics, TheOneYouWant, B.J.W.T, AlastorMoody, Kamran011, Limerent, guptaamitu1, CahitArf, Adventure10, Mango247, sabkx, NonoPL

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.

This post has been edited 3 times. Last edited by anantmudgal09, Apr 5, 2018, 7:22 PM
Reason: corrections in write-up; thanks to mofumofu for pointing them out

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

biomathematics

2568 posts

biomathematics

#16 h Feb 28, 2016, 6:28 PM • 6 Y

Y by anantmudgal09, PRO2000, phymaths, Aryan-23, Adventure10, Mango247

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.

This post has been edited 7 times. Last edited by biomathematics, Nov 25, 2017, 9:31 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

huashiliao2020

1292 posts

huashiliao2020

#52 h Sep 6, 2023, 7:08 PM

Y by

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$ .

This post has been edited 1 time. Last edited by huashiliao2020, Sep 6, 2023, 7:09 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

YaoAOPS

1541 posts

YaoAOPS

#53 h Sep 7, 2023, 11:22 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RedFireTruck

4223 posts

RedFireTruck

#54 h Jan 22, 2024, 4:48 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

qwerty123456asdfgzxcvb

1086 posts

qwerty123456asdfgzxcvb

#55 h Feb 4, 2024, 7:48 PM

Y by

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)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

YaoAOPS

1541 posts

YaoAOPS

#56 h Feb 4, 2024, 7:53 PM

Y by

My solution works for that arrangement

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

m.ljf2997

11 posts

m.ljf2997

#57 h Apr 10, 2024, 9:28 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8863 posts

HamstPan38825

#58 h Jun 28, 2024, 5:50 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dolphinday

1325 posts

dolphinday

#59 h Jun 29, 2024, 4:35 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Clew28

45 posts

Clew28

#60 h Jun 30, 2024, 6:53 PM • 1 Y

Y by duckman234

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] 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]$
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.

This post has been edited 4 times. Last edited by Clew28, Jul 19, 2024, 6:46 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

PEKKA

1848 posts

PEKKA

#61 h Jul 2, 2024, 10:19 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1271 posts

ezpotd

#62 h Sep 14, 2024, 3:02 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

OronSH

1746 posts

OronSH

#63 h Nov 5, 2024, 10:20 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

smileapple

1010 posts

smileapple

#64 h Jan 9, 2025, 6:23 AM

Y by

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:

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

575 posts

Maximilian113

#65 h Jan 11, 2025, 2:28 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

796 posts

shendrew7

#66 h Jan 12, 2025, 3:10 AM

Y by

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$

Z K Y