Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenge 2: Covering the Triangle

  1. Oct 2, 2013 #1

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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: Oct 2, 2013
  2. jcsd
  3. Oct 2, 2013 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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)?
     
  4. Oct 2, 2013 #3

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yeah, those were supposed to be edges, I edited the OP with that change.
     
  5. Oct 2, 2013 #4
  6. Oct 2, 2013 #5

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  7. Oct 2, 2013 #6

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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!
     
  8. Oct 2, 2013 #7
    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: Oct 2, 2013
  9. Oct 2, 2013 #8

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  10. Oct 2, 2013 #9

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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: Oct 2, 2013
  11. Oct 2, 2013 #10

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  12. Oct 2, 2013 #11

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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: Oct 2, 2013
  13. Oct 2, 2013 #12

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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: Oct 2, 2013
  14. Oct 2, 2013 #13

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Note: I removed some of the false steps from my previous post so there will be less confusion.
     
  15. Oct 2, 2013 #14

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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!
     

    Attached Files:

  16. Oct 2, 2013 #15

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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!
     
  17. Oct 2, 2013 #16

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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##
     

    Attached Files:

  18. Oct 3, 2013 #17

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I agree that everything in that post is correct.
     
  19. Oct 3, 2013 #18
    Whoops.
     
    Last edited: Oct 3, 2013
  20. Oct 3, 2013 #19

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    [edit] Nope, that won't work...
     
    Last edited: Oct 3, 2013
  21. Oct 9, 2013 #20
    I really want a proof using the minimax theorem.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Challenge 2: Covering the Triangle
  1. A little challenge (Replies: 8)

  2. Challenging problems (Replies: 6)

  3. Master's Challenge (Replies: 15)

  4. A Euclidean Challenge (Replies: 10)

Loading...