Proving that we have to dissect R into at least (n + 1) smaller rectangles ( solution Problem 1 shortlist Problem IMO 2014 about Combinatorics )

Problem 1:

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.

Solution 1.

Also Read:

Let k be the number of rectangles in the dissection. The set of all points that are corners of one of the rectangles can be divided into three disjoint subsets:

  • A, which consists of the four corners of the original rectangle R, each of which is the corner of exactly one of the smaller rectangles,
  • B, which contains points where exactly two of the rectangles have a common corner (T-junctions, see the figure below),
  • C, which contains points where four of the rectangles have a common corner (crossings, see the figure below).

We denote the number of points in B by b and the number of points in C by c. Since each of the k rectangles has exactly four corners, we get

4k = 4 + 2b + 4c.

It follows that 2b\leqslant 4k-4, so b\leqslant 2k-2.

Each of the n given points has to lie on a side of one of the smaller rectangles (but not of the original rectangle R). If we extend this side as far as possible along borders between rectangles, we obtain a line segment whose ends are T-junctions. Note that every point in B can only be an endpoint of at most one such segment containing one of the given points, since it is stated that no two of them lie on a common line parallel to the sides of R. This means that

b\geqslant 2n

Combining our two inequalities for b, we get

2k-2\geqslant b\geqslant 2n,

thus k\geqslant n+1, which is what we wanted to prove.

Solution 2.

Let k denote the number of rectangles. In the following, we refer to the directions of the sides of R as ‘horizontal’ and ‘vertical’ respectively. Our goal is to prove the inequality k\geqslant n+1 for fixed n. Equivalently, we can prove the inequality n\leqslant k-1 for each k, which will be done by induction on k. For k = 1, the statement is trivial.

Now assume that k > 1. If none of the line segments that form the borders between the rectangles is horizontal, then we have k – 1 vertical segments dividing R into k rectangles. On each of them, there can only be one of the n points, so n\leqslant k-1, which is exactly what we want to prove.

Otherwise, consider the lowest horizontal line h that contains one or more of these line segments. Let R’ be the rectangle that results when everything that lies below h is removed from R (see the example in the figure below).

The rectangles that lie entirely below h form blocks of rectangles separated by vertical line segments. Suppose there are r blocks and ki rectangles in the ith block. The left and right border of each block has to extend further upwards beyond h. Thus we can move any points that lie on these borders upwards, so that they now lie inside R’. This can be done without violating the conditions, one only needs to make sure that they do not get to lie on a common horizontal line with one of the other given points.

All other borders between rectangles in the ith block have to lie entirely below h. here are ki – 1 such line segments, each of which can contain at most one of the given points. Finally, there can be one point that lies on h. All other points have to lie in R’

(after moving some of them as explained in the previous paragraph).

We see that R’ is divided into k-\sum_{i=1}^{r}k_{i} rectangles. Applying the induction hypothesis to R’, we find that there are at most

points. Since r\geqslant 1, this means that n\leqslant k-1, which completes our induction.

Also Read : Combinatorics : Shortlist problem of IMO 2014

%d bloggers like this: