Coat and Patches Area Problem?

Question

A coat of area 5 has five patches on it each with an area of at least 2.5. Prove there is some pair of patches whose common (overlapping) area is at least 1.

Disposable, I think you're misinterpreting the problem. It asks to prove that there exists 2 patches such that their common area is at least 1.

Zo Maar: The total area of the region common to 2 patches cannot actually equal 10.

Zo Maar: Sorry, you are right. I'm a little unclear how you determined that the arrangement with 2 patches covering 1/2 of the coat and 3 patches covering the other 1/2 of the coat gives minimal area.

Answer 1

EDIT 4 (topology):

Your are right, Duke. We need to resolve also the topology issue.

Let's draw a five point star on the coat. Then we have 10 cells: 5 cells are vertices of the outer pentagon and 5 cells are vertices of the inner pentagon. Something like that:

......................1

.............2.....3...4.....5
..................6......7
......................8
...............9 .........10

Patches start from an outer cell, go three cells along a straight line, turn and finish at another outer cell. Explicitely:

A: 1, 3, 6, 8, 10
B: 1, 4, 7, 8, 9
C: 2, 3, 4, 7, 10
D: 2, 6, 8, 7, 5
E: 5, 4, 3, 6, 9

All the patches are simply connected and they intersect with the other patches at two cells. Clearly, we can deform cells in such a way that they occupy the whole coat and that each cell has the area of 0.5.


EDIT 3:

Absird, the original explanation is in the paragraph starting from: "Suppose, we place a piece of patch "a" of area S on the coat...". Seemingly this point is unclear. I try again.

Suppose we have two regions with N and M>N layers of the same area. In these regions we have N(N-1)/2 and M(M-1)/2 pairwise overlappings. Let's re-arrange the covering, by replacing one patch from M to N. Since M has more patches, we can always choose a patch to replace, which does not belong to N. Then we will get (N+1)N/2 and (M-1)(M-2)/2 pairwise overlappings. The difference is: (1/2) ( N(N-1) + M(M-1) - (N+1)N - (M-1)(M-2) ) = M-N-1. If M>N+1, then the total number of pairwise overlappings reduces. If the regions N and M have different areas, we consider their smaller sub-regions of the same area, and repeat the same arguments.

Thus, if we have a covering such as the difference in the number of layers in some regions is greater than 1, then this covering does not give the minimal area of pairwise overlappings. The best strategy is to cover the coat consequitively layer by layer, until all the patches are finished. In our case, this gives a half (at least) of the coat covered with three layers and the remaining part covered with two layers.


One more remark. The condition that the area of each patch is at least 2.5 is not actually used. What is required for the proof is that the total coverage area is at least 12.5 and patches do not overlap with themselves.

*******************************************************

EDIT 2:
Duke, what do you think about the following covering?

The patches are A,B,C,D,E. Suppose that they all have the area of 2.5. Let's split the coat in 10 cells, numbered from 1 to 10. Each cell has the area of 0.5. Then each patch occupies 5 cells. The table below shows cells numbers occupied by each patch. I write cell's number, if the patch occupies this cell, and I write "-" otherwise. For example, patch A occupies cells 1,2,3,4,5. Every patch overlaps with all the other patches exactly at two cells (the overlapping cells are counted below the table). Then all 2 by 2 common areas are 1.


Patch A: 1 2 3 4 5 - - - - -
Patch B: 1 2 - - - 6 7 8 - -
Patch C: - - 3 4 - 6 7 - 9 -
Patch D: 1 - - - 5 - 7 - 9 10
Patch E: - - 3 - 5 6 - 8 - 10

Common cells:
(AB)=(1,2); (AC)=(3,4); (AD)=(1,5); (AE)=(3,5);
(BC)=(6,7); (BD)=(1,7); (BE)=(6,8);
(CD)=(7,9); (CE)=(3,6);
(DE)=(5,10).

***************************************************************


EDIT:

Absird, could you tell me whether I read the problem incorrectly, or there is a mistake in my reasoning?

Please note, that I count the total area S of pairwise overlappings. When a region is common to 2 patches, it is taken into account with the factor of 1. When a region is common to 3 patches, it is taken into account with the factor of 3, because it contains 3 pairwise overlappings.

If a half of the coat is covered with three layers and a half of the coat is covered with two layers, then the total area of pairwise overlappings will be S = 1*2.5 + 3*2.5 = 10.

S can be larger than 10 if we have more than three layers somewhere, but it cannot be smaller than 10.

********************************************

I use the term "double layer" to denote the part of the coat occupied by two patches. If a part of the coat is occupied by three patches "1", "2", and "3", then this part is considered as three "double layers": (1,2), (1,3), and (2,3).

Suppose, we place a piece of patch "a" of area S on the coat. If this piece is placed on the part, which is already occupied by N patches, "1", "2", ... "N", then N new "double layers" are formed: (a,1), (a,2), ... (a,N). The area of the new added "double layers" is N*S. It means, that if we want to minimize the total area of the "double layer", we should avoid multiple overlappings.

Let's cover the coat of area 5 by 5 patches with the area of 2.5. The "double layer" has the minimum area S_{min}, when the area of 2.5 of the coat is covered by two layers, and the remaining area of 2.5 is covered by three layers (2*2.5 +3*2.5 = 5*2.5 = the total area of all the patches). The area of this "minimal double layer" is equal to S_{min}= 2.5 +3*2.5 = 10 (recall that tripple layer is equal to 3 "double layers").

From 5 patches we can choose 10 different pairs: (1,2), (1,3), ... (4,5). Hence, there exist 10 different types of "double layers". Suppose, that the area of each type is less than 1. Then the total area of the "double layer" will be less that 10. However, we have shown that the minimal area of the "double layer" is 10.

Hence, there is some pair of patches that has common area of at least 1.

Answer 2

There are 5C2 = 10 pairs of patches. If we could prove that the total area of the pairs of patches is at least 10, then we would be done. Let's introduce some variables before we go any further. Let the total area of the patches be A, the total common area of pairs of patches be B, the total area where 3 patches overlap be C, 4 patches overlap D, and 5 patches overlap E. Now let's apply the principle of inclusion-exclusion (PIE) to generate some inequalities that we can work with.

In terms of the variables we have defined, the total area of the coat covered by at least 1 patch is A - B + C - D + E (see why?). I'll assume the patches must not be hanging off of the coat in which case we have the inequality

A - B + C - D + E <= 5.

We are interested in B so let's isolate that to get

B >= A + C - D + E - 5.

Since the 5 patches each have an area of at least 2.5 we determine that A >= 12.5, and we can substitute this into our inequality above to get

B >= 7.5 + C - D + E. (1)

We need to introduce another expression involving C, D, and E so let's apply PIE again except this time let's generate an inequality for the area covered by at least 2 patches. Applying PIE, an expression for the area of the coat covered by at least 2 patches is B - 2C + 3D - 4E (verify this yourself). Like in our other PIE calculation we can say that this expression is less than or equal to 5.

5 >= B - 2C + 3D - 4E (which after some tweaking becomes)
C >= B/2 + 3D/2 - 2E - 5/2.

We can substitute this into (1): B >= 7.5 + C - D + E to get

B >= 7.5 + (B/2 + 3D/2 - 2E - 5/2) - D + E
B/2 >= 5 + D/2 - E
B >= 10 + D - 2E.

Now our task is reduced to showing D - 2E >= 0. We can do another PIE calculation for the area covered by at least 4 patches which yields the inequality D - 4E >= 0 (an even stronger inequality that's also true is D - 4E >= E). For our purposes, D - 4E >= 0 is sufficient to show that D - 2E is nonnegative so B >= 10. Thus, there exists some pair of patches whose common area is at least 1.

Answer 3

I think that the area in question is even greater, at least 1.25. Let the patches are P1, P2, P3, P4, P5, their areas A1, A2, A3, A4, A5 /Ai ≥ 2.5, i=1,2,3,4,5/. Let a /a < 1/ is the greatest of 2 by 2 common (overlapping) areas - suppose it is the common area of A1 and A2. Then
Area(P1 U P2) = Area(P1\P2) + Area(P1 ∩ P2) + Area(P2\P1) = (A1 - a) + a + (A2 - a)
If we add P3 now the area, covered by P1 U P2 U P3 will not be less than
A1 + A2 + A3 - Area(P1 ∩ P2) - Area(P2 ∩ P3) - Area(P3 ∩ P1) ≥ (A1 - 2a) + (A2 - 2a) + (A3 - 2a) + 3a
This configuration can be demonstrated by an equilateral triangle XYZ with 3 lines, parallel to the sides, intersecting in the centroid - the patches are the 3 trapezoids with bases XY, YZ and ZX, overlapping 2 by 2 in 3 rhombuses (area a each), small triangles with areas A - 2a each.
Adding P4 and P5 most economically (we cannot allow 3 regions area a per patch, but can 2) leads to something like a square with 4 pieces (area a) in the vertexes and 5 "bridges"
(areas Ai - 2a > 0 because of the values given) along the 4 sides and one of the diagonals, so
Area(A1 U A2 U A3 U A4 U A5) ≥
≥ (A1-2a) + (A2-2a) + (A3-2a) + (A4-2a) + (A5-2a) + 4a =
= (A1 + A2 + A3 + A4 + A5) - 10a + 4a ≥
≥ 5*2.5 - 6a and this minimal area should be less than the area of the coat, or
5*2.5 - 6a = 12.5 - 6a ≤ 5, or 7.5 ≤ 6a, finally
a ≥ 7.5/6 = 1.25
*** Sorry, this is not the most economical configuration ***

P.S.(EDIT - after having read Zo Maar's answer) I studied the table very carefully - it's indeed very interesting - we have to agree what is exactly "a patch"? Is it a CONNECTED plain region or not? Should we consider, say 2 circles, connected with a string (line segment - set with 0 area), or say something like "Z" with connected ends (2 touching triangles with common vertex only - formally this is a connected set) as a single patch, or as 2 patches? If we take the first alternative, I immediately agree with You - the example covering follows this approach. Then, if we take the second alternative comes the next question - may the patch have holes (is it a region, topologically equivalent to a circle, or a ring, etc.). Maybe the best is to leave the decision to the author.
My "patch" interpretation was other than Yours, but I tried to arrange Your covering so that every patch to be polygon-like without self-crossing (meanwhile by renumbering the pieces easily follows that A, B and C in the table are equivalent to the triangle XYZ in my answer above, so the question is how to add most economically D and E).
I'll be curious to know if this is possible.

EDIT 2: Excellent solution now by Zo Maar, congratulations! This is exactly what I wanted to know. It fully deserves the best answer.

Answer 4

We have 5 patches which each cover 2.5 units of area, for a total coverage of 7.5 units of area.

If the coat has 5 units of area, then at least 2.5 units of area must be overlap (7.5 - 5 = 2.5).

If two patches each overlapped 1.25 units of area, this would solve the problem. However, what if each patch overlapped another patch by .25? This would mean each patch would have to overlap the other 4 patches by .25 units of area, or a total of 1 unit of area (.25 * 4).

Thus, your proof!

Hope this helps.

Answer 5

Have her thyroid checked. A dermis scraping might must be completed to rule out specific dermis ailments. there's a genetic undertaking in pomeranians pronounced as black dermis affliction or Alopecia X. there is particularly slightly of examine happening now related to this difficulty.

Answer 6

lol