There are $n>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? Proposed by Boris Frenkin - Russia
Problem
Source: 6th Iranian Geometry Olympiad (Elementary) P3
Tags: IGO, Iran, geometry, combinatorics
JBMO2020
22.09.2019 13:24
Could this be proved by induction?
zephyr7723
22.09.2019 14:43
No need for induction. This problem can be proved by a single claim. Claim: Given any point $A$ in the set of marked points $\exists \, 2 $(exactly) set of $n-2$ points, such that these two sets of points form two separate straight lines with $A$. The claim can be proved by assuming the contradictory statement to be true and then applying some trivial size bounds.
Saucepan_man02
05.11.2021 07:21
Just a little knowledge of Combinatorics, is enough....
Since no three lines are concurrent, there are $ \binom{n}{2} $ points in the plane, and each line consists of $ (n-1) $ points, as no three lines are concurrent (i.e. This plane has maximum possible no. of points in a plane of $n$ non-parallel lines). Since $ n > 2 \Rightarrow n \ge 3$, we can restore the diagram by making lines that pass through many different possible $ n-1 $ points.
Saucepan_man02
05.11.2021 07:41
The answer is $ \boxed{Yes!} $.
Now we prove that we can restore the diagram...
CLAIM: There are $ (n-1) $ points on any line.
The key observation is that no three lines are concurrent, which means that this is plane of $ n $ lines with the maximum no. of intersections, and further there are $ \binom{n}{2} $ points in the plane. Hence, there are $ (n-1) $ points on any line.
CLAIM: The diagram can be restored.
From the hypothesis $ n > 2 $, there is exactly one distinct line that passes through $ n-1 $ points. Hence, the diagram can be restored.
blackbluecar
05.11.2021 08:30
We claim the answer is yes. This is achieved by greedily drawing lines between $n-1$ collinear intersection points. Indeed, given any $n-1$ intersection points, you can clearly find a pair of points on the same line since $2(n-1) > n$. So, if $n-1$ points are collinear they must all be on one of our original lines as desired.