Maths Olympiad Prep

Library / /2 of 3

Geometry Difficulty 6.5 National Olympiad Prove it Japan

3 rectangles are placed on a plane, and any 2 rectangles have their edges that are parallel to each other. They divide the plane into several parts. Determine the maximum possible number of such parts. (We consider the area that are contained in no rectangles as one part. For example, if we have only 1 rectangle, the plane is divided into 2 parts.)

Solution

We will show that in case of nn rectangles the answer is 2n22n+22n^2 - 2n + 2. We call each divided part region.

nn rectangles R1,n,,Ri,n+1i,,Rn,1R_{1,n}, \dots, R_{i,n+1-i}, \dots, R_{n,1} divide plane into 2n22n+22n^2 - 2n + 2 regions, where Rx,yR_{x,y} is a rectangle with corners at (x,y)(x, y), (x,y)(x, -y), (x,y)(-x, y), (x,y)(-x, -y). Therefore we only have to show that nn rectangles cannot divide the plane into more than 2n22n+22n^2 - 2n + 2 regions.

Induction. The case n=1n = 1 is trivial. Suppose that the case n=kn = k is true. Let R1,,Rk+1R_1, \dots, R_{k+1} be k+1k+1 rectangles with the property in the problem, and D1,,DmD_1, \dots, D_m be the regions divided by R1,,RkR_1, \dots, R_k. By the induction's hypothesis, we have m2k22k+2m \le 2k^2 - 2k + 2.

Let CiC_i be the border of RiR_i. Suppose that for iji \ne j, CiC_i and CjC_j shares finitely many points. (The proof goes the same way if it's not satisfied). Let P1,,PlP_1, \dots, P_l be the intersection of Ck+1C_{k+1} and C1,,CnC_1, \dots, C_n, ordered along Ck+1C_{k+1}. l4kl \le 4k since CiC_i and Ck+1C_{k+1} crosses at 4 or less points. Add polygonal lines P1P2,,PiPi+1,,PlP1P_1P_2, \dots, P_iP_{i+1}, \dots, P_lP_1 one by one to D1,,DmD_1, \dots, D_m. One line increases the number of region by 1 or less, So adding all polygonal lines increases the number of region by ll or less.

Since adding P1P2,,PiPi+1,,PlP1P_1P_2, \dots, P_iP_{i+1}, \dots, P_lP_1 is equivalent to adding Ck+1C_{k+1}, the number of regions divided by R1,,Rk+1R_1, \dots, R_{k+1} is
m+l(2k22k+2)+4k=2(k+1)22(k+1)+2. m+l \le (2k^2 - 2k + 2) + 4k = 2(k+1)^2 - 2(k+1) + 2.
So we have completed the induction. Therefore, the answer of the problem is 14.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.