Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2004 Indonesia MO Problems/Problem 8"

(→‎Problem 8)
(→‎Solution)
 
(2 intermediate revisions by 2 users not shown)
Line 4: Line 4:
  
 
==Solution==
 
==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,
 +
 +
<math>(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)</math>
 +
<math>+(a\cap b\cap c + ...+c\cap d\cap e) - (a\cap b\cap c\cap d + ...+ b\cap c\cap d\cap e)</math>
 +
<math>+(a\cap b\cap c\cap d\cap e) = 3</math>
 +
 +
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 <math>5+p-q+r-s=3</math>
 +
 +
 +
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, <math>0\le s < 0.2</math>.
 +
 +
Since r represents the sum of 5 intersecting rags, with each overlapped area < 0.2, <math>s\le r < 1</math>.
 +
 +
Similarly, <math>r\le q < 2</math>, since q is the sum of <math>{5 \choose 3} = 10</math> overlapped area, where each area < 0.2.
 +
 +
<math>q\le p < 2</math>, since p is the sum of <math>{5\choose 2} = 10</math> areas.
 +
 +
From the restrictions, we know that the total area = <math>5-p+q-r+s \ge 5-p+r-r+s > 5-2+s = 3+s \ge 3</math>. Thus, Total Covered Area <math>= 5-p+q-r+s > 3</math>, which is a contradiction.

Latest revision as of 19:57, 13 September 2024

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2004_Indonesia_MO_Problems/Problem_8&oldid=227140"