11
$\begingroup$

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

enter image description here

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$. enter image description here

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

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

$\endgroup$
  • 2
    $\begingroup$ This seems to handle points on extensions. Direct the extensions away from the segment. 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. $\endgroup$ – Joseph O'Rourke Nov 25 '17 at 16:59
  • $\begingroup$ @JosephO'Rourke: Sorry, don't understand. What are "to the right", "forward extention", "backward extention"? $\endgroup$ – user64494 Nov 25 '17 at 17:04
  • $\begingroup$ An extension is a ray from a segment endpoint, along the line containing the segment. "Direct the extensions away from the segment" means to aim the ray away from the segment. Then extensions have left and right sides. You can think of one extension as forward and the other backward, just for language convenience. $\endgroup$ – Joseph O'Rourke Nov 25 '17 at 17:33
  • $\begingroup$ @JosephO'Rourke: Sorry, I prefer accurate definitions over unclear words.There is a lot of cases even for $n=2$. $\endgroup$ – user64494 Nov 25 '17 at 17:38
  • $\begingroup$ Re "Addition 2": Per Alexandersson's proof only regards the final step. At that point, every region is bounded by line segments (or rays/lines) and, due to the construction, every point at which multiple segments intersect, one of the segments continues all the way through - thus the arrangement determine only angles less than $\pi$, so the determined regions must be convex. The issue of boundaries is not related to the pigeonhole principle (which is a purely combinatorial statement) and the boundaries are explicitly handled by Joseph O'Rourke's addition. $\endgroup$ – Milo Brandt Nov 27 '17 at 22:47
8
$\begingroup$

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:


          SegsPts
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:
          SegsPtsCollinear
          $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$.


| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry, don't understand you. The statement " This partitions the plane into $n+1$ convex regions" is unbased. $\endgroup$ – user64494 Nov 25 '17 at 14:20
  • $\begingroup$ @user64494: Added an explanation, but this is already in Per & Jan-Christoph's remarks. $\endgroup$ – Joseph O'Rourke Nov 25 '17 at 14:22
  • $\begingroup$ Can you explain "Assume no pair of segments are collinear" in details? TIA. $\endgroup$ – user64494 Nov 25 '17 at 14:36
  • $\begingroup$ @user64494: I will edit to explain further. $\endgroup$ – Joseph O'Rourke Nov 25 '17 at 14:42
  • 1
    $\begingroup$ One could add that we can consider points that are in between two collinear segments on a common extended segment to be in their own region (since having collinear segments decreases the number of "big" regions) - which , with your correction, then completely partitions the complement of the arrangement into exactly $n+1$ convex regions. $\endgroup$ – Milo Brandt Nov 25 '17 at 21:44
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I knew the problem as math folklore. Thank you for the info. It is kind of you. If you know its solution, please, present the proof to MathOverflow. $\endgroup$ – user64494 Nov 26 '17 at 13:55
  • $\begingroup$ I know the same solution as already posted, with continuation of segments and counting the parts. $\endgroup$ – Fedor Petrov Nov 26 '17 at 14:36
  • $\begingroup$ I have strong doubts concening the completeness of the answers by Per Alexandersson & Joseph O'Rourke (see the additions in my question). $\endgroup$ – user64494 Nov 26 '17 at 14:41
  • $\begingroup$ There is no solution of the problem under consideration at mccme.ru/free-books/matpros.html . It's a pity. $\endgroup$ – user64494 Nov 26 '17 at 15:06
  • $\begingroup$ Please, elaborate "This allows to suppose that no three lines containing these segments have a common point, and no three out of $2n$ their endpoints lie on a line" and "why convex? Because an angle greater than $\pi$ can not appear" in details. $\endgroup$ – user64494 Nov 26 '17 at 15:32
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your attention to the question. Can you state "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" in details? Do you pay your attention to "nonoverlapping"? $\endgroup$ – user64494 Nov 25 '17 at 14:10
  • 2
    $\begingroup$ You cannot let the lines become infinite, as that would violate the "non-crossing" condition, and without this condition, the statement becomes false. However, you can extend one segment until it meets another segment, that is, you may assume without loss that all segments are infinite or on another segment. Then your argument works. $\endgroup$ – Jan-Christoph Schlage-Puchta Nov 25 '17 at 14:15
  • $\begingroup$ @Jan-ChristophSchlage-Puchta: The segments are assumed to be closed. Can you state "However, you can extend one segment until it meets another segment" in details? $\endgroup$ – user64494 Nov 25 '17 at 14:18
  • 1
    $\begingroup$ Please, state your arguments for $n=2$. $\endgroup$ – user64494 Nov 25 '17 at 14:21
  • 1
    $\begingroup$ Points may become to belong to the extended segments. is not so? To which region do they belong? $\endgroup$ – user64494 Nov 25 '17 at 15:00
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you kindly state the case $n=2$ in details? $\endgroup$ – user64494 Nov 25 '17 at 19:59
  • $\begingroup$ This may not help: In the case n = 2, assume that are in fact 2 closed line segments S_0 and S_1 and 4 specific points p_0, p_1, p_2, and p_3 not in the segments such that all the L_{ij} intersect either S_0 or S_1. Remove S_1. By the Lemma, there is now a unique L_{ij} that is non-intersecting to S_0. If I take away p_j, then we have one segment (S_0) and the remaing three points, and there are no non-intersecting L_whatevers left. But that's not possible, so our assumption that there was such a situation (S_0 and S_1 and p_0 through p_3 with all the appropriate conditions) was false. $\endgroup$ – raydulany Nov 25 '17 at 20:06
  • $\begingroup$ "This may not help" because it's just me paraphrasing the induction above, using specifically n = 2. $\endgroup$ – raydulany Nov 25 '17 at 20:09
  • $\begingroup$ Sorry, can you add the proof of Lemma for $n=2$ in details? Pictures and $\LaTeX$ are welcome. $\endgroup$ – user64494 Nov 25 '17 at 20:27
  • 1
    $\begingroup$ Still don't understand. Your statement "Thus there are only two points that can now be joined" (How the ones can be connected?) is not based. We have one closed line segment $S_0$ and four points $p_0,\dots,p_3$. There may be 6 closed line segments linked them which do not intersect $S_0$. It' s high time to go to bed for me so I end this discussion today up to the local time of me. $\endgroup$ – user64494 Nov 25 '17 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.