Let F be a finite family of segments in R such that among any n of them there are two intersecting. Prove that it is possible to divide F into n−1 families such that any two segments in one family are intersecting.
Asked
Active
Viewed 237 times
0
-
@CalvinLin Hey. Yup, I tried to approach it in this way that if I take some segments like for example 5 segments out of which 2 are intersecting. And taking an assumption if the smallest segment is contained in a bigger segment and has an intersection. So I can omit the smallest segment resulting in the n-1 segment that satisfies the theorem – Logo Nov 25 '20 at 05:20
-
@CalvinLin But it was all wrong as you can see as I considered segments in case families. Like I need to divide it into n-1 families. Now I got stuck here. – Logo Nov 25 '20 at 05:22
-
@CalvinLin I am pretty new to all this subject and somehow I am not able to visualise beyond. Even though I have understood different types of Helly's theorem but somehow I have actually failed to understand it. Since I am able to prove it. – Logo Nov 25 '20 at 05:23
-
I can't "see" because you didn't show any work (for several of your posts), so I (and others) have no idea what you're thinking of, or even what you know. – Calvin Lin Nov 25 '20 at 05:24
-
@CalvinLin actually I had previously written my approach when I asked the question but then edited it out since I got it what was wrong in this. – Logo Nov 25 '20 at 05:25
-
@CalvinLin And thanks for pointing out the other question. I had almost forgotten about it. I have attached images of what I have solved for the same. Please go through it and give any valuable feedback. – Logo Nov 25 '20 at 05:36
-
FWIW Showing a wrong approach (and marking it as such) can still be helpful at times, as it gives an indication of what you're thinking about. – Calvin Lin Nov 25 '20 at 05:36
-
@CalvinLin Thanks I will keep that in mind from now on. – Logo Nov 25 '20 at 05:37
-
(I just realized that the 2 problems are not identical, so I deleted my original comment) – Calvin Lin Nov 25 '20 at 05:38
-
@CalvinLin Yes, they are pretty much different. – Logo Nov 25 '20 at 05:39
-
With my restatement of the problem, it becomes this post. – Calvin Lin Nov 25 '20 at 06:05
-
@CalvinLin thanks for your answer. – Logo Nov 25 '20 at 06:36
1 Answers
0
(Fill in the gaps as needed. If you're stuck, write out your working and thought process to demonstrate where you're at.)
Rephrase the statement to
Let F be a finite family of segments in R such that among any $n$ of them there are two intersecting. Prove that there are $n-1$ values, such that each segment contains at least 1 of these values.
You can do a proof by induction on $n$.
The case of $n=2$ is Helly's theorem (or you can prove it directly by considering the left most right endpoint).
Suppose the statement is true for some $k$. Consider $k+1$.
Given any $m \geq k+1$ segments $R_i = [a_i, b_i]$ that satisfy the condition that any $k+1$ segments have 2 segments what intersect.
WLOG, let $R_1$ be the segment with the left-most right endpoint (IE $b_1 = \min(b_i)$)
Any set which intersects $R_1$ must contain $b_1$.
Consider any $k$ sets which do not intersect $R_1$. By the assumption applied on these $k$ sets along with $R_1$, there exists 2 which intersect. $R_1$ cannot be involved, so it's 2 of these $k$ sets. Apply the induction hypothesis, and there are $k-1$ points such that these sets contain at least 1 of these values.
Take the union of these $k-1$ points along with $b_1$, and we are done.
Calvin Lin
- 68,864