Guest User

Untitled

a guest
Nov 6th, 2022
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.38 KB | None | 0 0
  1. Okay finally came to a solution! It's not super formal as the formal solution requires more rigor, but this is an outline.
  2.  
  3. Big assumption: if the endpoint of an arc is at a point a, the arc covers the point a. If not, this solution might need to be reworked.
  4.  
  5. Consider the pink arcs. There are either a) two pink arcs that are disjoint, or b) all pink arcs also intersect each other.
  6.  
  7. Case b:
  8. Consider the situation where all pink arcs also intersect each other. Let's consider the smallest pink arc . For this smallest pink arc, it cannot contain any arc by definition, but it intersects with all n green arcs and all n-1 other pink arcs.
  9. All these arcs can either intersect our pink arc from one endpoint or the other, possibly both. But at least from one endpoint. As there are 2n-1 arcs, and 2 endpoints, one of the endpoints must have n arcs containing it by the pigeonhole principle.
  10.  
  11. Case a:
  12. Consider the situation where there are two disjoint pink arcs - p1 & p2. Note that for a green arc to overlap with both of them, it has to at least overlap with the extreme endpoints of two pink arcs, or the two closer endpoints of the pink arcs. Note that this means that there's at least one set (extremes or closer) with n/2 (green) + 1 (pink) arcs covering it.
  13.  
  14. Picture to help:
  15. https://www.screencast.com/t/CPkMijMWSpay
  16.  
  17. Now looking at the above picture, if all green arcs either take the longer path or the shorter path, we are done as there are n green arcs that cover a point. Note that a green arc can completely encirle the circle, but that doesn't hurt our math as it only helps by covering more points.
  18.  
  19. So let's assume that there's at least one green arc in the longer path and one in the smaller.
  20.  
  21. Then, for a pink arc (that's not among the two disjoint p1 bad p2) to overlap with all green arcs, it needs to cover the longer and shorter green arcs. Which means it needs to cover the parts of p1 that are covered by green or the parts of p2 that are covered by green.
  22.  
  23. So there's at least one set (endpoints of p1 or p2) that has n-2/2 (pink) + 1 (p1 or p2) arcs covering it.
  24.  
  25. Let the endpoints of p1&p2 be p1a and p1b, and p2a and p2b.
  26.  
  27. The extremes are p1a and p2b, the middle are p1b and p2a.
  28.  
  29. Note that each of these sets has one point in common. So at least one point has n/2 + 1 + n-2/2 = n arcs covering it (not adding the second 1 as that's double count) .
  30.  
Advertisement
Add Comment
Please, Sign In to add comment