Question

2n + 1 segments are marked on a line. Each of these segments intersects at least n other segments. Prove that one of these segments intersects all other segments.

Answer 1

The question is to be done by induction. Let's take k = 1

=> There are three segments such that all segments intersect at least one segment.

Only possibility is as follows :

Here 2 intersect both (1) & (3).

Hence, statement is true for k = 1

Note: This is the worst case in which every segment is intersecting k segments. If we can prove in this one, then it can be proved otherwise as well.

Let if be true for k = n - 1, it implies that 2 (n - 2) segments intersect (n - 1) segments and 1 segment intersect all other.

Now, we add 2 segments such that all the segments intersect with n segments. It means one of these segments will intersect with (n - 1) segments and other with another (n - 1) segments.

This way 2(n - 2) segments intersect with n segments.

Now, these two segments have (n - 1) intersection.

They have to intersect with the segment intersecting all other to satisfy. Hence proved by PMI.