Maths Olympiad Prep

Library / /5 of 7

Combinatorics Difficulty 6.5 National olympiad Find the answer

There are n>2n>2 lines on the plane in general position; Meaning any two of them meet, but no three are concurrent. All their intersection points are marked, and then all the lines are removed, but the marked points are remained. It is not known which marked point belongs to which two lines. Is it possible to know which line belongs where, and restore them all?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Given n>2 n > 2 lines on the plane in general position, such that every pair of lines intersects but no three lines are concurrent. All intersections are marked, and then the lines are removed, leaving only the intersection points. The task is to determine if it is possible to uniquely restore all original lines based on the marked points.

To consider this problem, follow these logical steps:

1. Intersection Points Calculation:
For n n lines in general position, each pair of lines intersects exactly once. The total number of intersection points is given by the combination of n n lines taken two at a time:
(n2)=n(n1)2 \binom{n}{2} = \frac{n(n-1)}{2}

2. Unique Identification of Lines:
Each intersection point corresponds uniquely to a pair of lines. Since no three lines are concurrent, each point is created by precisely two specific lines. Thus, we seek to recover the pairs from the points.

3. Graph Theoretical Approach:
Consider treating each intersection point as an edge of a graph where each line is a vertex. The problem is analogous to reconstructing a graph from its edge list:
- Each intersection point (edge) connects two distinct lines (vertices).
- The graph formed is complete Kn K_n because each pair of vertices is connected by a unique edge.
- For complete graphs, each connection (edge) can be tracked back, allowing the original n n lines (vertices) to be restored.

4. Resolution of Line Restoration:
Since Kn K_n is completely determined by its set of edges when no three lines (vertices) meet, the given intersection points allow us to unambiguously determine the structure of the original geometry:
- Each line is associated with specific points forming this complete graph.

Conclusion:
The problem can definitively be solved with the restoration of all original lines based on the marked intersection points. Thus, it is possible to uniquely restore all the lines given the condition that no three lines are concurrent:

Yes \boxed{\text{Yes}}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.