Challenge 2: Covering the Triangle

[Office_Shredder]

Suppose A₁, A₂ and A₃ are closed convex sets, and let Δ be a triangle with edges F₁, F₂ and F₃ such that
A_1 \cup A_2 \cup A_3 = \Delta
and
F_i \cap A_i = \emptyset \text{ for } i=1,2,3

Prove there exists some point x\in \Delta such that
x\in A_1 \cap A_2 \cap A_3

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

 

[jbunniii]

let Δ be a triangle with faces F₁, F₂ and F₃

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)?

 

[Office_Shredder]

Yeah, those were supposed to be edges, I edited the OP with that change.

 

[Boorglar]

Do the "edges" need to be straight lines, or could the figure look like this?
http://en.wikipedia.org/wiki/Reuleaux_triangle

Just asking, although I'm not sure that would make me understand the problem XD

 

[AlephZero]

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).

 

[Office_Shredder]

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!

 

[eigenperson]

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.

 

[jbunniii]

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.

 

[Office_Shredder]

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.

 

[jbunniii]

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.

 

[jbunniii]

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

 

[jbunniii]

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.

 

[jbunniii]

Note: I removed some of the false steps from my previous post so there will be less confusion.

 

[Office_Shredder]

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 A₁, unlike F₁ so the A₂ and A₃ 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!

 

[jbunniii]

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 A₁, unlike F₁ so the A₂ and A₃ 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!

 

[jbunniii]

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$

 

[Office_Shredder]

I agree that everything in that post is correct.

 

[economicsnerd]

Whoops.

 

[jbunniii]

[edit] Nope, that won't work...

 

[economicsnerd]

I really want a proof using the minimax theorem.

 

[mfb]

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.

x₁₂ can be extended to a line segment on the edge where A₁ and A₂ 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 x₁₂ would be the boundary of $A_1 \cup A_2$. A₃ cannot include x₁₂, 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 A₁ (marked with the two arrows in the attachment). If the set is connected, we are done (the existence of a point in all A_i is then equivalent to the proof that a point x₁₂ exists).
If the set is not connected, there has to be some point in between which is at the boundary of A₁, but neither A₂ nor A₃ 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.

 

[jbunniii]

x₁₂ can be extended to a line segment on the edge where A₁ and A₂ 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 x₁₂ would be the boundary of $A_1 \cup A_2$. A₃ cannot include x₁₂, 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?

 

[mfb]

Hmm right, I forgot that case.
I think the following argument still holds. The boundary of A₁ 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.

 

[Office_Shredder]

Nice work mfb, I agree that that works and doesn't require having extra intersection on the boundaries of the triangle.

 

[jbunniii]

If the set is not connected, there has to be some point in between which is at the boundary of A₁, but neither A₂ nor A₃ 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.

 

[Office_Shredder]

Yes but jbunniii, the key point of being on the boundary is that there is a sequence not in A₁ converging to that point. That sequence can't lie in A₂ or A₃ or by those sets being closed our original boundary point would be contained in one of those sets as well (this is a different perspective of the contradiction in mfb's post)

 

[jbunniii]

Yes but jbunniii, the key point of being on the boundary is that there is a sequence not in A₁ converging to that point. That sequence can't lie in A₂ or A₃ or by those sets being closed our original boundary point would be contained in one of those sets as well (this is a different perspective of the contradiction in mfb's post)

OK, I think I buy that. By definition of boundary, you can construct a sequence of distinct points, none of which are in $A_1$, which converges to $A_1$. This sequence cannot contain a subsequence of points in $A_2$ or a subsequence of points in $A_3$, because otherwise the point in question would be contained in one of these sets. Therefore all points in the sequence beyond a certain $N$ must be in none of the $A_i$'s, contradicting the fact that the triangle is covered by the three sets. So the other (connected) situation must hold, and as mfb said, we can argue as we did for the existence of $x_{12}$.

I'm slightly nervous that there is some case that this fails to address, but it looks valid to me.

 

[Office_Shredder]

Of course the thread is still open to other proofs, if anybody has good ideas post them up (or if you have a bad idea, we're equal opportunity idea-ists here).