This is a pretty ambiguous problem. "Each rectangle has parallel sides and the sides of distinct rectangles lie on distinct lines." I'll take to mean that any two rectangles have two pairs of respectively parallel sides and that no four vertices are collinear, but I need a few other clarifications as well: - Are we counting the "unbounded" region which is not included in any rectangle? - Are we only counting regions which don't have any lines passing through their interiors, or all regions?

i cannot understand this question?! what does region mean? for example if the rectangles ABCD and EFGH have intersection and their intersection (that is a rectangle) named KFLD, then ABCD and KFLD both are region or only KFLD is region? can any body help me to understand... (i dont need solution!!)(sorry for my poor english!!)

I think the problem statement is pretty clear. "Regions" are the regions into which the plane is cut by the rectangles (no more inner lines), including the infinite one. Note that the sum only counts the regions that contain vertices of the rectangles, e.g. for the four rectangles in the attached image, only the grey regions (and the surrounding infinite one) are counted. (and the sum would be here $12\cdot4+28=76$.)

Attachments:

Here's a solution that cwein3 came up with. Let $R=\{R_1,R_2,\cdots,R_{|R|}\}$ be the regions satisfying the condition, and let $c(R_i)$ be the number of corner vertices that region $R_i$ has on its border. Notice that since each exterior angle of a region is $\pm \frac{\pi}{2}$ and the sum must be $2\pi$, we have that $v(R_i)$ is always even. Lemma: For a given $R_i$, let $v(R_i)=2k$. Then $c(R_i)\ge k-2$. Proof: First, realize that every angle of a region is either $\frac{\pi}{2}$ or $3\frac{\pi}{2}$; note that any $\frac{3\pi}{2}$ angle must be the corner of a rectangle, as if the edges leading up to it corresponded to different rectangles and stopped at that vertex their sides would lie on the same lines; contradiction. This gives us that the number of square corners is at least the number of obtuse angles. Thus, we show that for $v(R_i)=2k$, the number of such obtuse angles is at least $k-2$. In fact, it is equal to $k-2$, which can be seen again by the exterior angles argument: each obtuse angle contributes $-\frac{\pi}{2}$ and each right angle contributes $\frac{\pi}{2}$. As the sum is $2\pi$, there must be exactly four more right angles than obtuse ones, and the result follows. $\square$ From this lemma, it is immediately clear that $c(R_i)\ge \frac{v(R_i)}{2}-2$. Let $X,Y$ be the set of non-rectangular and rectangular regions in $R$. Using the lemma, it is apparent that $\sum_{R_i\in X} \left (\frac {v(R_i)} {2} - 2 \right) + |Y| \le 8n$, or $\sum_{R_i\in X} v(R_i) \le 16n+4|X|-2|Y|\Rightarrow \sum v(R) \le 16n+4|X|+2|Y|$. Note a region is a member of $X$ iff it has an obtuse angle, each of which requires a corner, so $|X|\le 4n$. Then $16n+4|X| + 2|Y| \le 16n+8n+2|R|\le 40n$, as desired.

Let $r(R)$ be the number of "real" vertices of a region $R$. We are asked to prove $ \sum v(R)-5r(R) \le 0$. For any $R$ that isn't a hexagon, this is quickly verified to be negative, since a $270º$ angle vertex must always be a real vertex. When $R$ is a hexagon, look at its one $270$º angle vertex, which also belongs to another region. Let $r_1,...,r_{\ell}$ be these "another regions", and let $r_i$ be the "counterpart" of $a_i$ hexagons. Then since $v(R)-5r(R)=1$ for $R$ hexagon, and there are $a_1+...+a_{\ell}$ hexagons, it is enough to prove $\sum_{i=1}^{\ell} v(r_i)-5r(r_i)+a_i \le 0$. Let $r_i$ have $2k_i$ sides, then it has $k_i-2$ $270º$ angle vertices (which must all be real), and also at least $a_i$ extra real vertices. Thus it suffices to prove (if $K=\sum k_i, A=\sum a_i$) that $\sum_{i=1}^{\ell} 2k_i -5(k_i-2+a_i)+a_i \le 0$, i.e. $-3K-4A + 10 \ell \le 0$, whch is easy, since $4A+3K = \sum (4a_i+3k_i) \ge \sum (4+3(2)) = 10 \ell$. Funny enough, my proof doesn't work for $(40-\epsilon)n$, even though it seems $40$ is kinda arbitrary.

Note that each region's boundary is a polygon (or, in the case of the infinite region, many polygons) with vertices having angles either $90$ or $270$ (we use degrees throughout). Furthermore, each vertex can only be either a vertex of a rectangle (which we color red) or the intersection of two sides of different rectangles (we color these blue). Note that each red vertex has a $90$ angle and a $270$ angle, while blue vertices are $4$ $90$ angles: [asy][asy] size(8cm); dotfactor *= 2; fill((0,0)--(0,2)--(2,2)--(2,2.2)--(-.2,2.2)--(-.2,0)--cycle,pink); fill((0,0)--(.2,0)--(.2,1.8)--(2,1.8)--(2,2)--(0,2)--cycle,palecyan); draw((0,0)--(0,2)--(2,2)); dot((0,2),red); fill((5,1)--(5,.8)--(5.8,.8)--(5.8,0)--(6,0)--(6,1)--cycle,lightyellow); fill((5,1)--(5,1.2)--(5.8,1.2)--(5.8,2)--(6,2)--(6,1)--cycle,lightred); fill((7,1)--(7,1.2)--(6.2,1.2)--(6.2,2)--(6,2)--(6,1)--cycle,lightblue); fill((7,1)--(7,.8)--(6.2,.8)--(6.2,0)--(6,0)--(6,1)--cycle,lightgreen); draw((5,1)--(7,1)); draw((6,0)--(6,2)); dot((6,1),blue); [/asy][/asy] Now, suppose a closed portion of a region's boundary has $v$ vertices, $r$ of which are red and form a $270$ angle (when measured by the angle in the region in question). If the region is in the interior of this part of the boundary, then we have \[ 90(v-r) + 270r = 180(v-2) \implies 2v-4 = v+2r \implies v = 2r+4. \]Otherwise, if the region is exterior to this part of the boundary: [asy][asy] fill((0,0)--(5,0)--(5,5)--(0,5)--cycle,pink); filldraw((1,2)--(2,2)--(2,1)--(3,1)--(3,2)--(4,2)--(4,3)--(3,3)--(3,4)--(2,4)--(2,3)--(1,3)--cycle,orange); [/asy][/asy] We have, then, that $v-r$ have an angle of $90$ (measured from the exterior) and $r$ have an angle of $270$ (measured from the exterior). Thus, measured form the interior, they become $270$ and $90$, respectively; for reference, in the above image, the pink is the exterior region, and the orange is the interior. So, \[ 270(v-r) +90r = 180(v-2) \implies 3v-2r = 2v-4 \implies v = 2r- 4 \leq 2r+4. \]Summing over all connected boundaries of the region gives \[ \sum v \leq \sum(2r+4), \]Summing over all nice regions gives \[ \textnormal{\# of vertices over all regions}\leq 2\sum r + 4(\textnormal{\# of nice regions}) . \]But $\sum r$ counts each red vertex once (the pink region in the first diagram), so it equals $4n$. Furthermore, the number of nice regions is at most $8n$, so we get \[ \textnormal{\# of vertices over all regions} \leq 2(4n)+4(8n) = 40n. \]For equality to hold, we need $2r+4 = v$ for every connected part of every region, i.e. every region needs to be interior to every connected, closed part of its boundary, which is false for the infinite exterior region outside of all rectangles. So, equality cannot hold, and the number of vertices is less than $40n$.

We define the leakiness of a nice region to be one less than the number of rectangle vertices it contains. We will prove the stronger statement that $$\sum_{R\in\text{nice}}4\cdot\text{Leakiness}(R)+\text{\#Vertices}(R)\le 40n$$To do this, we use induction. The base case $n=1$ is trivial. Now, suppose we have an arrangement of $n$ rectangles and we add the $n+1$st. First, consider where the vertices land. We will only consider the case where vertices land in different regions, since it is not hard to show that vertices landing in the same region is strictly worse. In this case, the addition of each vertex divides the region it landed in into two parts, and since each part contains it, both regions are nice. As we add three new vertices to each region created (ie the vertex, and the intersection of the sides incident upon it with the boundaries of the region) the vertex sum increases by $6$ per vertex. Now, we claim that each vertex can increase leakiness by at most 1. This is pretty easy to show - if the region the vertex landed in had $a+b$ rectangle vertices and the vertex split it into groups of $a,b$, then the leakiness sum increases from $a+b-1$ to $(a+1-1)+(b+1-1)=(a+b-1)+1$ as desired. So, each vertex increases our sum by $6+4\cdot 1=10$, which is $40$ in total. Now, we consider how the edges of the new rectangle affect our leakiness/vertex sum. If an edge passes through a mean (ie not nice) region, then it partitions it into two mean regions, which contributes nothing to the sum. On the other hand, if it goes through a nice region, it can partition it into a nice region and a mean region, or two nice regions. In the former case, leakiness sum doesn't change, and it is clear that the vertex sum cannot increase. On the other hand, if we form two nice regions, note that each nice region gets two more vertices which increases the vertex sum by $4$. However, since the vertices of the nice region were split, the sum of the leakinesses decreased by $1$, meaning our sum changes by $4-4\cdot 1=0$. So, we have shown that the vertices can increase the sum by at most $40$ and the sides can change the sum by at most $0$, and the induction is complete.

Color a point nice-inducing if it is the vertex of a rectangle. A region has an outer boundary and perhaps inner boundaries, each of which are polygons. We assume the unbounded region to be bounded by some large imaginary rectangle, which we will never interact with. Note that this unbounded region has at least one inner boundary. By exterior angle theorem, in any outer boundary of a region there must be $2c+4$ vertices where $c$ is the number of concave vertices, and in any inner boundary this number is $2c-4$. Let $m$ be the number of nice regions. Each nice-inducing point can appear only once in a boundary as convex, so summing over all nice regions, the number of vertices in nice regions is at most $2(4n)+4m$ with equality if and only if every boundary is an outer one. In other words, equality is impossible. There are at most $8n$ nice regions since each nice-inducing vertex and induce at most two nice regions, so we are done.