Challenge 2: Covering the Triangle

  • #1
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,750
99

Main Question or Discussion Point

Suppose A1, A2 and A3 are closed convex sets, and let Δ be a triangle with edges F1, F2 and F3 such that
[tex] A_1 \cup A_2 \cup A_3 = \Delta[/tex]
and
[tex] F_i \cap A_i = \emptyset \text{ for } i=1,2,3[/tex]

Prove there exists some point [itex] x\in \Delta [/itex] such that
[tex] x\in A_1 \cap A_2 \cap A_3 [/tex]

Figurative bonus points if your solution involves a weakening or generalization of the hypothesis.
 
Last edited:

Answers and Replies

  • #2
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
let Δ be a triangle with faces F1, F2 and F3
Can you please define this terminology? Does face = edge, or is this a generalization to a higher dimension (or generalization of the classical notion of triangle)?
 
  • #3
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,750
99
Yeah, those were supposed to be edges, I edited the OP with that change.
 
  • #4
210
10
  • #5
AlephZero
Science Advisor
Homework Helper
6,994
291
My topology is too long forgotten to make a proper proof, but to get started,

Let ##v_1## be the vertex of the triangle defined by ##F_2 \cap F_3##.

Then ##v_1 \notin A_2## and ##v_1 \notin A_3##, so ##v_1 \in A_1##

and similarly for the other two vertices.

So it's intuitively clear how the triangle must be "filled in" by the three sets, and that it's possible that there is only one point ##x## as defined in the OP. (Of course there may be more than one).
 
  • #6
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,750
99
Boorglar, it's just a regular triangle with straight edges but if you think you have a proof that can handle a more general case I'd love to see it!
 
  • #7
160
21
I think I've got it (although it uses a named theorem, so it might not be the kind of elementary proof you're looking for):

For each ##n##, construct an ##1/n##-fine triangulation of the triangle and color the vertices with ##\left\{1, 2, 3\right\}## such that ##\chi(v) = i## only if ##v \in A_i##. By Sperner's lemma, every such triangulation has a triangle with all three vertices colored differently. Let ##a_n, b_n, c_n## be these vertices. Take a sequence of indices ##\left\{n_k\right\}_{k=1}^\infty## so that the subsequences ##\left\{a_{n_k}\right\}_{k=1}^\infty, \left\{b_{n_k}\right\}_{k=1}^\infty, \left\{c_{n_k}\right\}_{k=1}^\infty## are all convergent; this can be done since each set ##A_i## is compact. All three subsequences converge to the same point because ##\left|a_{n_k} - b_{n_k}\right| < 1/n_k \to 0## and ##\left|b_{n_k} - c_{n_k}\right| < 1/n_k \to 0##. This point must be in all the sets ##A_i, \Delta##, because they are all closed. That is the desired point.

If I'm right, this doesn't require the sets to be convex, and it doesn't really require the covered set to be a triangle either (once you throw away convexity you should be able to apply any sufficiently nice transformation).

EDIT: Fixed notation error.
 
Last edited:
  • #8
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
My topology is too long forgotten to make a proper proof, but to get started,

Let ##v_1## be the vertex of the triangle defined by ##F_2 \cap F_3##.

Then ##v_1 \notin A_2## and ##v_1 \notin A_3##, so ##v_1 \in A_1##

and similarly for the other two vertices.

So it's intuitively clear how the triangle must be "filled in" by the three sets, and that it's possible that there is only one point ##x## as defined in the OP. (Of course there may be more than one).
So for example, the edge ##F_1## has endpoints ##v_2\in A_2## and ##v_3\in A_3##. Now consider the interior ##I_1 = F_1 \setminus \{v_2 \cup v_3\}##, i.e., ##F_1## minus its endpoints. I claim that ##I_1## must contain points of both ##A_2## and ##A_3##. If not, assume WLOG that it contains only points of ##A_2##. Then every point of ##F_1## is in ##A_2##, except for the one endpoint ##v_3##. But this violates the fact that ##A_2## must be closed.

We can argue similarly for the other edges. Thus:
* ##I_1## must contain points of ##A_2## and ##A_3##
* ##I_2## must contain points of ##A_1## and ##A_3##
* ##I_3## must contain points of ##A_1## and ##A_2##

Rearranging this:
* ##A_1## must contain points of ##I_2## and ##I_3##
* ##A_2## must contain points of ##I_1## and ##I_3##
* ##A_3## must contain points of ##I_1## and ##I_2##

By convexity:
* ##A_1## must contain a nondegenerate triangle with one vertex at ##v_1## and the other two on ##I_2## and ##I_3##
* ##A_2## must contain a nondegenerate triangle with one vertex at ##v_2## and the other two on ##I_1## and ##I_3##
* ##A_3## must contain a nondegenerate triangle with one vertex at ##v_3## and the other two on ##I_1## and ##I_2##

Hmm, that's not quite enough to conclude that the triangles have to intersect...but maybe this can be pushed farther.
 
  • #9
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,750
99
If I understand it correctly, those last three nondegenerate triangles could be arbitrarily close to being degenerate - it's like asking three arbitrary lines drawn from a vertex to the opposite side to all to intersect at a point.

EDIT: Woops, I realize now I didn't understand it correctly (despite jbunniii's acquiescence), so disregard this protest.
 
Last edited:
  • #10
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
Yes, you're right. I need something more: I need to ensure that, for example, ##I_1## contains points of ##A_2## and ##A_3## that are sufficiently far from ##v_2## and ##v_3##, respectively. And similarly for ##I_2## and ##I_3##. Will think about this some more.
 
  • #11
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
More can be said about the content of, for example, ##F_1##. Let's orient this segment from left to right so that ##v_2## is its left endpoint and ##v_3## its right endpoint. We already established that its interior must contain points of both ##A_2## and ##A_3##. Let ##x## denote the leftmost point such that there are no elements of ##A_2## to the right. Then by convexity and closure, the entire segment from ##v_2## to ##x## is in ##A_2##, and similarly, the entire segment from ##x## to ##v_3## is in ##A_3##. And ##x## is in both ##A_2## and ##A_3##.

Similarly, every edge is divided into two closed subintervals which overlap at one point somewhere in the interior of the edge, such that the left subinterval is contained in the same ##A_i## as the left vertex, and the right subinterval is contained in the same ##A_i## as the right vertex.

Thus we in fact partitioned the original triangle into four subtriangles. The subtriangle that includes ##v_i## is entirely contained in ##A_i##.

[edit] Remove false steps
 
Last edited:
  • #12
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
I think I only need one of the nondegenerate subtriangles constructed above.

Let's focus on the nondegenerate triangle ##T_1##. This is the subtriangle which has one vertex at ##v_1##. Let's call its other two vertices ##x_2## and ##x_3##, where ##x_2 \in I_3## and ##x_3 \in I_2##. By construction, ##x_2 \in A_2 \cap A_1##, and ##x_3 \in A_3 \cap A_1##. In particular, ##x_2 \in A_2## and ##x_3 \in A_3##.

Now let's consider the edge of ##T_1## which is opposite ##v_1##. This edge, let's call it ##E##, has as its endpoints ##x_2## and ##x_3## described above. And every point of ##E## is in ##A_1##.

So now we can repeat the convex/closed argument to show that ##E## is in fact partitioned into two closed segments, which overlap at one point. One of these segments is in ##A_2##, and the other is in ##A_3##. Moreover, both are in ##A_1##. Thus, the point of intersection of these two segments is in ##A_1 \cap A_2 \cap A_3##. Done.
 
Last edited:
  • #13
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
Note: I removed some of the false steps from my previous post so there will be less confusion.
 
  • #14
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,750
99
I realized that my original protest about your three triangles was not correct (I misunderstood what triangles were being constructed), although I have no idea whether they'll do what you want them to do.

If I understand your construction of E correctly it won't work, because E can be covered by A1, unlike F1 so the A2 and A3 may not intersect. I have attached a picture (I think, we'll see if I did it right) of what I think is a counterexample, if it's wrong let me know!
 

Attachments

  • #15
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
I realized that my original protest about your three triangles was not correct (I misunderstood what triangles were being constructed), although I have no idea whether they'll do what you want them to do.

If I understand your construction of E correctly it won't work, because E can be covered by A1, unlike F1 so the A2 and A3 may not intersect.
Crap, you're right. My argument for the original edge only worked because we knew that one of the ##A_i##'s had null intersection with it. That isn't the case for ##E##, as you pointed out.

OK, back to the drawing board!
 
  • #16
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
Here's my attempt to attach a picture of what I think has been established so far.

* ##A_1## contains the triangle defined by ##v_1##, ##x_{13}##, and ##x_{12}##, including vertices and edges
* ##A_2## contains the triangle defined by ##v_2##, ##x_{12}##, and ##x_{23}##, including vertices and edges
* ##A_3## contains the triangle defined by ##v_3##, ##x_{13}##, and ##x_{23}##, including vertices and edges

* the segment ##[v_3, x_{13})## contains only points of ##A_3##
* the segment ##[v_1, x_{13})## contains only points of ##A_1##
* the segment ##[v_1, x_{12})## contains only points of ##A_1##
* the segment ##[v_2, x_{12})## contains only points of ##A_2##
* the segment ##[v_2, x_{23})## contains only points of ##A_2##
* the segment ##[v_3, x_{23})## contains only points of ##A_3##
 

Attachments

  • #17
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,750
99
I agree that everything in that post is correct.
 
  • #18
269
24
Whoops.
 
Last edited:
  • #19
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
[edit] Nope, that won't work...
 
Last edited:
  • #20
269
24
I really want a proof using the minimax theorem.
 
  • #21
34,074
9,975
Here's my attempt to attach a picture of what I think has been established so far.

* ##A_1## contains the triangle defined by ##v_1##, ##x_{13}##, and ##x_{12}##, including vertices and edges
* ##A_2## contains the triangle defined by ##v_2##, ##x_{12}##, and ##x_{23}##, including vertices and edges
* ##A_3## contains the triangle defined by ##v_3##, ##x_{13}##, and ##x_{23}##, including vertices and edges

* the segment ##[v_3, x_{13})## contains only points of ##A_3##
* the segment ##[v_1, x_{13})## contains only points of ##A_1##
* the segment ##[v_1, x_{12})## contains only points of ##A_1##
* the segment ##[v_2, x_{12})## contains only points of ##A_2##
* the segment ##[v_2, x_{23})## contains only points of ##A_2##
* the segment ##[v_3, x_{23})## contains only points of ##A_3##
The attachment
Quoted to have it on the same page.

x12 can be extended to a line segment on the edge where A1 and A2 intersect. Proof by contradiction: Suppose they would intersect at a single point only: Then their whole intersection is just this point (as they are convex), and x12 would be the boundary of ##A_1 \cup A_2##. A3 cannot include x12, but would have to include points arbitrarily close to this -> it would not be closed, contradiction.

This allows to extend the triangles a bit, and ##A_1 \cap A_2## is a closed, convex set with non-empty interior. The same is true for the other two sides, of course.

Now consider the set ##((\partial A_1) \cap A_2) \cup ((\partial A_1) \cap A_3)## as subset of ##\partial A_1##, the boundary of A1 (marked with the two arrows in the attachment). If the set is connected, we are done (the existence of a point in all Ai is then equivalent to the proof that a point x12 exists).
If the set is not connected, there has to be some point in between which is at the boundary of A1, but neither A2 nor A3 cover it (marked with a question mark). This is a boundary of ##A_1 \cup A_2 \cup A_3## in the interior of the triangle, which violates the condition that the union covers the whole triangle.

Alternatively: There is at least one point of ##\partial A_1 and \partial A_2## that is also in ##\partial (A_1 \cup A_2)## (not sure how to prove this). If this point is in A_3, we are done, otherwise it is a boundary of ##A_1 \cup A_2 \cup A_3## and we get the same contradiction as above.



I think we can replace the triangle by an arbitrary convex shape, where we divide the boundary in three regions that get the conditions the edges had in the original problem.
 

Attachments

  • #22
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
x12 can be extended to a line segment on the edge where A1 and A2 intersect. Proof by contradiction: Suppose they would intersect at a single point only: Then their whole intersection is just this point (as they are convex), and x12 would be the boundary of ##A_1 \cup A_2##. A3 cannot include x12, but would have to include points arbitrarily close to this -> it would not be closed, contradiction.
Reading over my earlier argument, I think I am persuaded that ##A_1## and ##A_2## can have more than one point of intersection (hence a segment of nonzero length) on the side formed by ##v_1## and ##v_2##. But I'm not persuaded that they must do so. What precludes the configuration in the attached figure?
 

Attachments

  • #23
34,074
9,975
Hmm right, I forgot that case.
I think the following argument still holds. The boundary of A1 is connected, so either the two parts are connected and therefore the whole boundary (with at least one common point) or the three sets do not cover the whole triangle.
 
  • #24
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,750
99
Nice work mfb, I agree that that works and doesn't require having extra intersection on the boundaries of the triangle.
 
  • #25
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
If the set is not connected, there has to be some point in between which is at the boundary of A1, but neither A2 nor A3 cover it (marked with a question mark). This is a boundary of ##A_1 \cup A_2 \cup A_3## in the interior of the triangle, which violates the condition that the union covers the whole triangle.
I'm probably missing something, but isn't such a point in ##\partial A_1##, and therefore in ##A_1## since ##A_1## is closed? So it's in the union, and there's no contradiction.
 

Related Threads on Challenge 2: Covering the Triangle

Replies
23
Views
2K
Replies
13
Views
1K
Replies
40
Views
10K
Replies
86
Views
13K
Replies
82
Views
7K
Replies
62
Views
5K
Replies
16
Views
3K
Replies
41
Views
6K
Replies
97
Views
13K
Top