Segments on a line

[BMAD]

Given 50 segments on the line. Prove that one of the following statements is valid:

• 1. Some 8 segments have a common point.
• 2. Some 8 segments do not intersect each other.

[plasmid]

Suppose you have a set of 50 segments with no point shared by more than seven segments. Find the segment with the smallest maximum value and call it S1 with maximum value M1. Because S1 has the smallest maximum value, every other segment on the line must either contain M1 or contain only points that are greater than M1. Since we're starting out with a set of segments with no point shared by more than seven segments, there may be no more than seven segments that include point M1 (counting S1). Remove them, and you'll be left with at least (50-7 = 43) segments that only contain points greater than M1. Find the segment out of those remaining with the smallest maximum value and call it S2, and keep repeating this procedure. You will eventually choose seven segments (S1-S7) and for each of them you will have removed at most seven segments that contain their maxima. You will have removed at most (7*7 = 49) segments and will have at least one segment left over that only contains points greater than M7. That set of S1-S7 plus any leftover segment would constitute a set of eight segments with no points in common.

[Perhaps check it again]

BMAD, it looks like your problem statement is incomplete. 

 

I read it as "Given 50 [line] segments on the [a] line."

 

It seems you left out a key word or words, because these line segments could be intersecting each other,

or not intersecting each depending on where they are.

[bonanova]

I think what BMAD means by intersect is overlap.

So, "do not intersect" probably should be taken to mean "are mutually disjoint."

[Perhaps check it again]

I didn't question that "do not intersect each other" means that they do not overlap,

meaning that the [line] segments do not have any points in common.

 

But I can always have a situation where condition 2 occurs.  That is why I claim

there are other words/conditions/restrictions/qualifiers left out.

[BMAD]

You need to show that in any situation either #1 is true or #2 is true

[k-man]

You need to show that in any situation either #1 is true or #2 is true

 

Both #1 and #2 can be true at the same time. I guess you're looking for a proof that #1 and #2 cannot be both false.

[BMAD]

yes!

[gavinksong]

I would guess that Erdos-Szekeres Theorem is applicable here.

 

Let us label each of the left-bounds of the 50 line segments by a natural number signifying their order. Then, pair each of these numbers with a natural number signifying the order of the right bounds of their respective line segments.

 

For example, if the left bounds A, B, and C and their right bounds A', B', and C', are in the following relative positions:

 

A, B, A', C, C', B'

 

Then we would get the pairs (1, 1), (2, 3), and (3, 2).

 

Next, let these pairs describe an orderable sequence of natural numbers, where the first number in each pair describes the second number's position in the sequence.

 

Continuing with the above example gives us the pattern 1, 3, 2.

 

According to the Erdos-Szekeres theorem, a pattern of length (r-1)(s-1) + 1 or longer either contains an increasing subsequence of r or a decreasing subsequence of s. We can set r = 8 and s = 8 for a pattern of 50 elements. In other words, for a pattern of 50 elements, such as in the OP, there must be either 8 elements whose positions and values both increase or 8 elements whose positions increase while their values monotonically decrease. Both can be true, but both cannot be false.

 

The reason this result is significant to the OP is because a monotonically increasing subsequence is necessary for statement 1 to be true, while a monotonically decreasing subsequence necessarily means that statement 2 is true.

 

... which tells us nothing.

 

Man, I really thought I was onto something here.

[gavinksong]

Given the nature of these line segments, a set of line segments all share a common segment if and only if they all overlap with each other.

To see how this is true, first note that if all of the line segments share a common segment, then any two line segments can be said to overlap at the common segment. Now, note that given two overlapping line segments, it is impossible to add a third that overlaps with both line segments that does not also overlap with their common segment. This proves that any set of line segments that all overlap with each other must share a common segment, thus completing the lemma.

 

Perhaps using a graph would help. If we say that each vertex is a line segment, and edges between vertices represent overlapping of the respective line segments, then using the above lemma, a set of line segments share a common segment if their respective vertices on the graph form a clique. This suggests Ramsey's theorem may be relevant, especially since it is also closely related to the Erdos-Szekeres theorem I tried above.

Edited February 9, 2015 by gavinksong

[gavinksong]

Suppose you have a set of 50 segments with no point shared by more than seven segments. Find the segment with the smallest maximum value and call it S1 with maximum value M1. Because S1 has the smallest maximum value, every other segment on the line must either contain M1 or contain only points that are greater than M1. Since we're starting out with a set of segments with no point shared by more than seven segments, there may be no more than seven segments that include point M1 (counting S1). Remove them, and you'll be left with at least (50-7 = 43) segments that only contain points greater than M1. Find the segment out of those remaining with the smallest maximum value and call it S2, and keep repeating this procedure. You will eventually choose seven segments (S1-S7) and for each of them you will have removed at most seven segments that contain their maxima. You will have removed at most (7*7 = 49) segments and will have at least one segment left over that only contains points greater than M7. That set of S1-S7 plus any leftover segment would constitute a set of eight segments with no points in common.

 

Wow. I had seriously overthunk. I literally just realized that plasmid's proof is a finished solution.

Silly old me thought that we also had to prove 2 being false implies 1 being true.

Let's look at the first 49 segments. For both statements 1 and 2 to be false, there must be seven

cliques, or a group of segments that share a common point, of exactly seven segments each. If there are any more cliques, then one segment may be drawn from each one to prove statement 2. Note that if a segment does not belong in a clique, it forms a clique by itself. If there are any fewer cliques, or if a segment belongs to more than one clique, then there is a clique containing at least eight segments, proving statement 1. When the last line segment is added (a.k.a. line segment #50), it will either fall outside of a clique, making statement 2 true, or join a clique, making statement 1 true. Thus, one of the two statements is always true.