Maths Olympiad Prep

Library / /484 of 520

Combinatorics Difficulty 7.4 National olympiad, round 2 Prove it

A square is divided into n>1n>1 rectangles such that the sides of the rectangles are parallel to the sides of the given square. Each line that is parallel to one of the sides of the square and intersects the interior of the square shall also run in the interior of at least one of the rectangles.

Prove that there is then always a rectangle in this division that has no point in common with the boundary of the square.

Solution

We prove the contraposition and assume that every rectangle in the partition has at least one point in common with the boundary of the square. According to the conditions, it then has at least one of its sides in common with the boundary of the square. Therefore, the boundary of the square can be uniquely assigned to the rectangles of the partition in segments. Two non-connected segments cannot belong to the same rectangle; otherwise, they would be opposite each other, and lines on the other sides of this rectangle would intersect the interior of the square without running inside a rectangle.

The number n n of these segments thus matches the number n n of the rectangles. At the n n endpoints of the segments, two rectangles meet on the boundary of the square and have a corner there. Four additional corners of the rectangles coincide with the corners of the square, so that a total of 2n+4 2n + 4 rectangle corners lie on the boundary of the square. Thus, 4n(2n+4)=2n4 4n - (2n + 4) = 2n - 4 corners remain for the interior of the square. Now consider one of the n n points on the boundary of the square where two rectangles meet. The line perpendicular to the respective side of the square through this point P P
!
initially runs inside the square on one side of each of the two rectangles. For this line to run inside a rectangle within the square, it must intersect a side of a rectangle that is parallel to the side of the square from which we started. At this branching point Q Q , the two rectangles, whose boundary the line was previously (these do not have to be the two rectangles with the corner point P P ), each have a corner point. Such a point Q Q exists for each starting point P P , and two different starting points cannot have the same branching point Q Q . Therefore, at least 2n 2n rectangle corners must lie in the interior of the square, contradicting the previously determined maximum number 2n4 2n - 4 . Thus, there is always a rectangle that has no point in common with the boundary of the square.

Notes: The outer rectangle was only raised to a square so that the formulation of the solution is simpler. The frequently presented solutions involving the construction of impossible cases could easily leave gaps if arguments were made about the relative positions of rectangles or the course of paths.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.