Maths Olympiad Prep

Library / /22 of 27

Combinatorics Difficulty 8.5 Shortlist Prove it Saudi Arabia

A rectangle RR is partitioned into smaller rectangles whose sides are parallel with the sides of RR. Let BB be the set of all boundary points of all the rectangles in the partition, including the boundary of RR. Let SS be the set of all (closed) segments whose points belong to BB. Let a maximal segment be a segment in SS which is not a proper subset of any other segment in SS. Let an intersection point be a point in which 4 rectangles of the partition meet. Let mm be the number of maximal segments, ii the number of intersection points and rr the number of rectangles. Prove that m+i=r+3m + i = r + 3.

Solution

Let a minor intersection be a point in SS where exactly three rectangles meet and let the number of minor intersections be jj. Let side segments be segments corresponding to a side of a rectangle in the partition and let proper segments be segments into which intersection points cut up maximal segments.
Let the number of side segments be ss and the number of proper segments be pp. If we start from maximal segments, we note that each addition of an intersection point forms two new segments. Ultimately, when all the intersection points are included, only proper segments remain and therefore p=m+2ip = m + 2i. We now multiply all proper segments by 2 to account for both sides of a proper segment and subtract 4 to account for the fact that the sides of the rectangle RR (which are by definition proper segments) are counted only once. Thereafter, each addition of a minor intersection increases the number of segments by 1 until we get only side segments and therefore s=2p+j4s = 2p + j - 4. Combining the two equations, we obtain
s=2m+4i+j4. s = 2m + 4i + j - 4.
Now, counting rectangles by side segments we obtain s=4rs = 4r and counting rectangles by their angles we obtain 4r=4i+2j+44r = 4i + 2j + 4, the final term accounting for the four corners of RR. We transform the equation into 2r6=2i+j42r - 6 = 2i + j - 4. Combining all the obtained equations we get 4r=s=2m+2i+2r64r = s = 2m + 2i + 2r - 6 which gives us 2r+6=2m+2i2r + 6 = 2m + 2i, i.e. m+i=r+3m + i = r + 3. \square

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.