2004 Indonesia MO Problems/Problem 8

Problem 8

A floor with an area of $3 \text{ m}^2$ will be covered by $5$ rugs with various shapes, each having an area of $1 \text{ m}^2$ . Show that there exist $2$ overlapping rugs with the overlapped area at least $1/5 \text{ m}^2$ .

Solution

Let the first 3 rugs occupy the entire floor, then the next rug that you add in, by the pigeon hole principle, it must overlap with another rug. Let a, b and c be the overlapping region with rug 1, rug 2 and rug 3 respectively, a+b+c = 1, thus at least one of a, b and c must be greater than 0.2.

Solution

Suppose that a, b, c, d, e are the area each rag covers. Then, by principle of inclusion-exclusion,

$(a+b+c+d+e) - (a\cap b + a\cap c + a\cap d + a\cap e + b\cap c + b\cap d + b\cap e + c\cap d + c\cap e + d\cap e)$ $+(a\cap b\cap c + ...+c\cap d\cap e) - (a\cap b\cap c\cap d + ...+ b\cap c\cap d\cap e)$ $+(a\cap b\cap c\cap d\cap e) = 3$

Let p, q, r, s indicate the area overlapped by at least 2 rags, 3 rags, 4 rags, and 5 rags, respectively, then the above equation can be replaced as $5+p-q+r-s=3$

We will use contradiction

Suppose it is indeed possible for an arrangement such that each overlap of 2 or more rags covers less than 0.2 area and the total covered area is equal to 3.

Then, $0\le s < 0.2$ .

Since r represents the sum of 5 intersecting rags, with each overlapped area < 0.2, $s\le r < 1$ .

Similarly, $r\le q < 2$ , since q is the sum of ${5 \choose 3} = 10$ overlapped area, where each area < 0.2.

$q\le p < 2$ , since p is the sum of ${5\choose 2} = 10$ areas.

From the restrictions, we know that the total area = $5-p+q-r+s \ge 5-p+r-r+s > 5-2+s = 3+s \ge 3$ . Thus, Total Covered Area $= 5-p+q-r+s > 3$ , which is a contradiction.

Page

Toolbox

Search

2004 Indonesia MO Problems/Problem 8

Problem 8

Solution

Solution