Do there exist two points seeing one another?

Question

Let $n\ge1$ be an integer number. Let $n$ nonoverlapping closed line segments and $n+2$ distinct points which do not belong to those line segments be given in the plane $\mathbb{R}^2$.

Can two points among the $n+2$ given points be chosen such that the ones see one another i.e. the closed line segment connecting these points does not intersect any of the given $n$ line segments? In the case $n=1$ the affirmative answer is simple. However, I don't know the answer even for $n=2$.

Addition. Here is a modification of Joseph picture which demonstrates the difficulties when realizing the idea by Per

If the points $A(\frac {38} {20},\frac {38} {20}) $ and $B(\frac {32} {10},\frac {32} {10} ) $ are assumed to belong to $\{(x,y):y \ge x,y\ge 3-x\} $, then the proof suggested by Per fails.

Addition 2. I'd like to demonsrate another difficulty which appears in the Per's approach. Let us consider three segments $S_1:=[(-1,-1),(1,-1)],\,S_2:=[(1,1),(1,2)],\,S_3:=[(-1,0),(2,1)]$. The points are not of importance here. After the first step the plane is divided into two regions $R_1$ and $R_2$.

After the second step we obtain the regions $R_1$ and $R_3$, where the latter is not convex.

It is unclear for me whether after the final step we obtain the convex regions only (the larger the value of $n$, the more complicated the situation). One more problem consists in the definitions of the borders of the regions. In order to apply the pigeonhole principle the regions considered with their borders must not intersect. My advice to Per is to read the book I. Lakatos. Proofs and Refutations. Cambridge: Cambridge University Press.(1976). https://books.google.com.ua/books/about/Proofs_and_Refutations.html?id=1n6SFdXCOBQC&redir_esc=y

Answer 1

I was drawing this figure as Per Alexandersson replied and Jan-Christoph Schlage-Puchta commented, so I'll just leave it as an illustration of their idea that $n$ segments determine $\le n+1$ convex regions:

---

         

---

Assume no pair of segments are collinear. Extend them in any order, in both directions, until they hit a segment or a prior extension. This partitions the plane into $n+1$ convex regions, as is easily proved by induction.

If a pair of segments are collinear, and extension of one includes the other, then the convex partition has fewer than $n+1$ regions. If a pair of segments are parallel, nothing changes.

---

(Added later.) Below I try to illustrate the suggestion I made in a comment, repeated here: "Direct the extensions away from the segment [green below]. Assign a point on an extension to the convex region to the right of the extension. Then two points, one on the forward extension, one on the backward extension, are in two different regions and are invisible to one another." I use the OP's example:

---

         
          ^{$p_1,p_2,p_3,p_4$ are in $R_1,R_2,R_3,R_4$ (respectively).
          $p_4$ and $p_5$ cannot see one another, but $p_5 \in R_3$, the 2nd point in $R_3$.}

---

Answer 2

This very problem was proposed to St. Petersburg olympiad (selection round) in 2007 by Konstantin Kokhas (problem 6 for 10-th grade in the linked pdf). In the same year it was proposed - independently, I guess, - to the journal Matematicheskoe Prosveschenie (problem 5 in the linked pdf) by Maxim Kontsevich himself.

Here is a solution which is hopefully self-contained and complete.

Assume the contrary. At first, we slightly enlarge the segments so that new segments still do not overlap. After that each segment $AB$ between our $n+2$ points intersects one of $n$ segments in an interior point. This property is preserved under small perturbation of the $n$ segments. Such perturbation allows to get $n$ segments such that no three lines containing these segments have a common point, and no three out of $2n$ their endpoints lie on a line (for example, you may choose new endpoints one by one so that each time you fix an endpoint it does not lie on a line between two already fixed endpoints; and each time you fix both endpoints of a segment, the line containing it does not pass through a common point of other two lines. This is clearly possible, since already finitely many lines are forbidden and a small disc is allowed.)

Now we enlarge the segments one by one, each time either to infinity or to the intersection with another segment. We get a plane partitioned onto several convex regions. Let's prove that there are exactly $n+1$ regions and they are convex. Draw a large square and remove the parts of rays outside the square. Then we get a planar graph with all degrees equal to 3, and the number of vertices equals $2n$ (2 vertices at endpoints of each of extended segments). Each region is a convex polygon (since going along the boundary of each of the regions we see that all angles are less than $\pi$). Thus the number of edges equals $3n$, and the number of faces equals $n+2$ by Euler formula. One face is external, so $n+1$ inner faces as desired.

Answer 3

One can assume that all line segments are actually lines, or half-lines, since you can let the lengths of the line segment go to infinity. Note that one infinite line segment creates two disjoint (convex!) regions. Any additional segment bisects a region, so you'll end up with $n+1$ convex regions. With $n+2$ points, pigeon hole principle finishes the proof.

EDIT: To address non-crossing, this is the detailed construction: Enumerate the intervals, and extend each interval, one by one, in both directions until they hit another interval (or to infinity). It does not matter if the some intervals are parallel or not. The non-overlapping condition ensures that the number of regions is exactly $n+1$ (or less, it two intervals determine the same line). Joseph's illustration is exactly this construction.

I like this problem, perhaps I'll 'steal' it to a collection of nice math problems.

The argument can be generalized to the analogous $n$ non-degenerate (full-dimensional) $n$-gons in $R^n$, and $n+2$ points. E.g., triangles in $R^3$, and $n+2$ points.

Answer 4

You've already got n=1, we'll let that be our base case.

Fix n and suppose that for all i <= n-1 it is true that "for any i non-overlapping closed segments S_0,...,S_{i-1} and any i+2 distinct points p_0,...,p_{i+1} not on those segments there are always at least two points among them, say p_j and p_k, such that the closed segment joining L_{jk} joining p_j and p_k does not intersect any of the i non-overlapping segments".

Assume that the same is not true for n. Then there exist n segments S_0,...,S_{n-1} and n+2 points p_0,...,p_{n+1}, and for every pair of points p_i and p_j, the segment L_{ij} joining them intersects one of the S_k.

What happens when we remove S_{n-1}? I assert (see Lemma below) that no more than 2 points may now be joined by a segment that does not intersect S_0,...,S_{n-2}. Remove one of the two. We now have n-1 line segments and n+1 points such that no two points can be joined by a non-intersecting segment. This contradicts our induction assumption. QED.

Lemma: Given the conditions above, if we remove S_n-1, no more than two points may now be joined by a non-intersecting segment.

Proof: Suppose that there are at least three points, p_i, p_j, and p_k that can be joined by at least two non-intersecting segments (that is, up to index re-ordering, we have at least that L_{ij} and L_{ik} are non-intersecting). Then no matter what other line segment that does not include the points I choose (and specifically including S_{n-1}), at least two of them have a non-intersecting line segment (by the base case n=1; technically this relies on a slightly different statement, namely "If there are three points and any number of closed line segments such that at least two of the points can be joined by a non-intersecting line segment, then adding an additional line segment that does not contain one of the points must leave at least one pair of points that can be joined by a non-intersecting segment. I claim this is as easy to prove, and in a similar manner, as your base case n=1). This contradicts our assumption about S_0,...,S_{n-1} and p_0,...,p_{n+1}. QED