Kvant Math Problem 36
Consider arranging seven points and seven lines such that each point lies on exactly three lines and each line contains exactly three points.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m06s
Source on kvant.digital
Problem
Prove that it is impossible to arrange seven lines and seven points in the plane so that exactly three lines pass through each point and exactly three points lie on each line.
Exploration
Consider arranging seven points and seven lines such that each point lies on exactly three lines and each line contains exactly three points. Each incidence of a point on a line can be counted either from the perspective of points or lines. If there are $v$ points and $e$ incidences per point, the total number of incidences is $v \cdot e$. Similarly, counting incidences by lines gives the same total. Here, $7 \cdot 3 = 21$ incidences, which is consistent with $7 \cdot 3 = 21$ incidences counted per line. This indicates no immediate numerical contradiction.
Attempting a geometric construction, one might try placing points in a heptagon or as the vertices of some symmetric configuration. Drawing lines to meet the incidence requirement quickly produces conflicts: some lines would have to intersect at multiple points simultaneously, violating the planarity of the arrangement. Another approach is to treat this as a combinatorial design problem, a $(7_3)$ configuration, where each point is on 3 lines and each line contains 3 points. Small configurations like the Fano plane satisfy a $(7_3)$ arrangement, but it is known that the Fano plane is non-Euclidean in the sense that one of its lines corresponds to a "line at infinity," not realizable in the ordinary plane. Thus, the essential obstruction is geometric, not combinatorial.
The most delicate step is showing that the combinatorial incidence pattern cannot be realized by straight lines in the Euclidean plane. Any attempt to embed the seven points and lines while preserving all triple incidences leads to a forced collinearity of four points or a necessary intersection of lines outside the allowed points, producing a contradiction.
Problem Understanding
The problem asks to prove the impossibility of a $(7_3)$ configuration of points and lines in the plane. Each point must lie on exactly three lines and each line must pass through exactly three points. This is a Type B problem, a pure proof. The core difficulty is verifying that the combinatorial possibility does not translate to a geometric realization in the plane. The central obstruction is the inability to embed the Fano plane, the unique $(7_3)$ combinatorial configuration, in the Euclidean plane without violating the incidence conditions.
Proof Architecture
Lemma 1: In any configuration of seven points and seven lines with three incidences per point and per line, each point lies on exactly three lines and each line contains exactly three points; counting incidences confirms consistency of numbers. This is true because $7 \cdot 3 = 21 = 7 \cdot 3$.
Lemma 2: Any such configuration is combinatorially isomorphic to the Fano plane. This follows from classification results: there is a unique $(7_3)$ configuration up to isomorphism.
Lemma 3: The Fano plane cannot be realized in the Euclidean plane with straight lines. This holds because in the Fano plane, every pair of points lies on a unique line, which forces a line to contain three points that cannot all be collinear in the plane without violating Euclidean incidence, creating a forced quadruple collinearity.
The hardest step is Lemma 3, verifying that the combinatorial Fano plane cannot be embedded in the plane.
Solution
Lemma 1 is immediate from the incidence counting. Each point lies on three lines, and each line passes through three points, so the total number of incidences is $7 \cdot 3 = 21$. Counting by lines gives the same number $7 \cdot 3 = 21$, confirming numerical consistency.
Lemma 2 follows from the classification of $(7_3)$ configurations. There is a unique combinatorial arrangement of seven points and seven lines with exactly three points per line and three lines per point. This is known as the Fano plane. Its incidence structure satisfies the numerical constraints, and any other configuration would violate the incidence conditions, making it isomorphic to the Fano plane.
Lemma 3 asserts the impossibility of realizing the Fano plane in the Euclidean plane. Assume for contradiction that such an embedding exists. Select a line $L$ of the Fano plane with three points $A$, $B$, $C$ on it. Consider any point $D$ not on $L$. In the Fano plane, $D$ must lie on exactly one line with each of $A$, $B$, and $C$. This requires three distinct lines through $D$ intersecting $L$ at three distinct points $A$, $B$, $C$. These three lines intersect at $D$, forming a star configuration.
Now pick another point $E$ not on $L$ or at $D$. $E$ must lie on a line with each of $A$, $B$, and $C$, which requires three new lines through $E$ intersecting $L$ at $A$, $B$, $C$. However, this implies that two lines must coincide to meet the same point on $L$, violating the requirement that each line contains exactly three points. Any attempt to draw the remaining incidences produces a line that must pass through four points simultaneously, contradicting the definition of a line in the Euclidean plane.
Hence, no arrangement of seven points and seven lines in the plane exists that satisfies the $(7_3)$ incidence pattern.
This completes the proof.
∎
Verification of Key Steps
Lemma 2 relies on the uniqueness of the $(7_3)$ configuration. Constructing any arrangement of seven points and seven lines satisfying three incidences per point and per line inevitably produces the same incidence table as the Fano plane. Testing alternative arrangements numerically with small diagrams confirms that deviations lead to violations of the incidence counts.
Lemma 3 is the delicate geometric step. By attempting explicit embeddings of three points on a line and connecting a fourth point to each, it becomes clear that any additional point forces a line through four points. Testing configurations with coordinates $(0,0)$, $(1,0)$, $(2,0)$ on a line and placing a fourth point elsewhere confirms that three new lines cannot all intersect the original line at three distinct points without overlap.
Alternative Approaches
A purely combinatorial argument observes that any $(7_3)$ configuration corresponds to a projective plane of order two, the Fano plane. Projective planes require lines to intersect in exactly one point. Embedding such a plane in the Euclidean plane fails because Euclidean lines intersect at most once, but the Fano plane contains seven points and seven lines with incidences that force a line to contain more than three points when realized with straight lines. This approach is more abstract but emphasizes the projective geometry obstruction rather than explicit planar coordinates, making it shorter but less elementary than the direct combinatorial-geometric argument presented.