Kvant Math Problem 200

For part (a), the six points are the intersection points of four lines in general position.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m24s
Source on kvant.digital

Problem

a) Figure 3 shows six points, with three points lying on each of four lines. Prove that there are 24 different ways to map this set of six points onto itself so that every triple of points lying on one line is mapped to a triple of points that also lie on one line.

Figure 3

b) In Figure 4, nine points lie three on each of nine lines, and through each point pass three such lines. These nine points and nine lines form the famous “Pascal configuration.” In how many ways can our set of nine points be mapped onto itself so that every triple of points lying on one of our nine lines is mapped to a triple of points that also lies on some line of our configuration?

Figure 4

c) The same question for the Desargues configuration (consisting of ten points and ten lines) shown in Figure 5.

Figure 5

A. N. Kolmogorov

Exploration

For part (a), the six points are the intersection points of four lines in general position. Each point is determined by the pair of lines passing through it. If the four lines are labeled $1,2,3,4$, then the six points are $p_{ij}=L_i\cap L_j$. A permutation of the four lines permutes the six intersection points. This already gives $4!=24$ symmetries. The only possible difficulty is showing that every admissible permutation of the six points comes from a permutation of the four lines.

For part (b), the configuration is the classical Pappus, or Pascal, configuration. A useful combinatorial model is obtained from the complete bipartite graph $K_{3,3}$. Its nine edges will be the nine points of the configuration. The six triples of edges incident with a fixed vertex of $K_{3,3}$ give six lines of the configuration. The three perfect matchings of $K_{3,3}$ give the remaining three lines. Every automorphism of $K_{3,3}$ permutes the nine edges and preserves these nine triples. Since

$$|{\rm Aut}(K_{3,3})|=2(3!)^2=72,$$

this suggests the answer $72$. The delicate point is proving that every automorphism of the configuration comes from an automorphism of $K_{3,3}$.

For part (c), the Desargues configuration has a remarkably simple abstract description. Let the five symbols be $1,2,3,4,5$. The ten points correspond to the $2$-element subsets, and the ten lines correspond to the $3$-element subsets. A point ${i,j}$ lies on a line ${i,j,k}$ exactly when the former is contained in the latter. Then every permutation of the five symbols preserves incidence, giving $120$ symmetries. The crucial issue is showing that every symmetry arises this way.

The step most likely to conceal an error is the converse direction in parts (b) and (c), namely reconstructing the underlying combinatorial object uniquely from the incidence structure.

Problem Understanding

This is a Type A problem. For each configuration we must determine all incidence-preserving permutations of the set of points.

In part (a), the configuration consists of six points lying three on each of four lines. We must count all permutations of the six points that send every collinear triple to another collinear triple.

In part (b), the same question is asked for the $9_3$-configuration of Pappus.

In part (c), the same question is asked for the Desargues $10_3$-configuration.

The main difficulty is proving that every incidence-preserving permutation is forced by a symmetry of a simpler underlying combinatorial structure.

The answers are

$$24,\qquad 72,\qquad 120.$$

The reason these numbers are plausible is that the three configurations can be encoded respectively by four lines, by the graph $K_{3,3}$, and by a set of five symbols. Their full symmetry groups have orders $4!$, $2(3!)^2$, and $5!$.

Proof Architecture

First, for part (a), prove that the four collinear triples are intrinsically determined by the incidence structure, hence every automorphism permutes these four triples. Then identify the six points with the pairs of lines among four lines and show that every automorphism is induced by a permutation of the four lines.

Second, for part (b), represent the nine points as the nine edges of $K_{3,3}$. Show that the nine configuration lines are exactly the six stars at vertices together with the three perfect matchings. Every automorphism of $K_{3,3}$ gives a configuration automorphism. Then prove conversely that the six star-lines are characterized combinatorially and therefore any configuration automorphism induces an automorphism of $K_{3,3}$.

Third, for part (c), represent the ten points by the $2$-subsets of a $5$-element set and the ten lines by the $3$-subsets. Every permutation of the underlying $5$-element set gives a configuration automorphism. Then show that the five families

$$F_i={{i,j}:j\ne i}$$

are determined intrinsically, so every configuration automorphism induces a permutation of the five symbols.

The hardest step is the converse argument in part (c), where one must recover the underlying $5$-element set from the incidence structure alone.

Solution

a)

Let the four lines be $L_1,L_2,L_3,L_4$. Since every two of them meet, the six points are

$$p_{ij}=L_i\cap L_j,\qquad 1\le i<j\le4.$$

The line $L_i$ contains exactly the three points

$$p_{ij},\ p_{ik},\ p_{i\ell},$$

where ${j,k,\ell}={1,2,3,4}\setminus{i}$.

Any permutation of the four lines induces a permutation of the six points $p_{ij}$, and collinear triples are carried to collinear triples. Thus there are at least

$$4!=24$$

admissible permutations.

Now let $\sigma$ be any admissible permutation of the six points.

The four triples of points lying on the lines $L_1,L_2,L_3,L_4$ are precisely the four collinear triples occurring in the configuration. Hence $\sigma$ permutes these four triples.

Therefore $\sigma$ induces a permutation of the set ${L_1,L_2,L_3,L_4}$. If $L_i$ is sent to $L_{\pi(i)}$, then the point

$$p_{ij}=L_i\cap L_j$$

must be sent to

$$L_{\pi(i)}\cap L_{\pi(j)} =p_{\pi(i)\pi(j)}.$$

Thus $\sigma$ is completely determined by the permutation $\pi$ of the four lines.

Hence every admissible permutation arises from a unique permutation of the four lines, and the number of such permutations equals

$$4!=24.$$

b)

Let the two parts of $K_{3,3}$ be

$$A_1,A_2,A_3, \qquad B_1,B_2,B_3.$$

Identify the nine points of the configuration with the nine edges

$$e_{ij}=A_iB_j.$$

There are six triples of edges incident with a fixed vertex:

$${e_{i1},e_{i2},e_{i3}}, \qquad {e_{1j},e_{2j},e_{3j}}.$$

These correspond to six lines of the Pappus configuration.

The remaining three lines are the three perfect matchings

$$M_\tau={e_{1,\tau(1)},e_{2,\tau(2)},e_{3,\tau(3)}},$$

where $\tau$ is one of the three cyclic permutations of ${1,2,3}$.

Thus we obtain exactly nine lines, each containing three points, and every point lies on three lines.

Any automorphism of $K_{3,3}$ permutes the nine edges and preserves incidence. Hence it induces an automorphism of the configuration.

The automorphism group of $K_{3,3}$ consists of arbitrary permutations of the three $A$-vertices, arbitrary permutations of the three $B$-vertices, and the optional interchange of the two parts. Therefore

$$|{\rm Aut}(K_{3,3})| = (3!)(3!)\cdot2 = 72.$$

So there are at least $72$ configuration automorphisms.

We now prove that there are no others.

Among the nine lines, six have the property that each meets four other lines and is disjoint from four. These are precisely the six star-lines coming from the vertices of $K_{3,3}$. The remaining three lines, namely the perfect matchings, are pairwise disjoint.

Hence the set of six star-lines is determined solely from the incidence structure. Their intersection pattern is exactly the graph $K_{3,3}$: two star-lines meet if and only if the corresponding vertices of $K_{3,3}$ are adjacent.

Therefore every automorphism of the configuration induces an automorphism of $K_{3,3}$. Since each point is the intersection of a unique adjacent pair of star-lines, the induced automorphism of $K_{3,3}$ completely determines the permutation of points.

Consequently every configuration automorphism comes from an automorphism of $K_{3,3}$.

The number of admissible permutations is therefore

$$2(3!)^2=72.$$

c)

Let

$$X={1,2,3,4,5}.$$

Represent the ten points of the Desargues configuration by the ten $2$-element subsets of $X$.

For each $3$-element subset ${i,j,k}\subset X$, define a line consisting of the three points

$${i,j},\quad {i,k},\quad {j,k}.$$

There are

$$\binom53=10$$

such lines, and each point ${i,j}$ lies on exactly the three lines corresponding to the triples containing $i$ and $j$. This is the Desargues configuration.

Every permutation $\pi\in S_5$ acts on the points by

$${i,j}\mapsto{\pi(i),\pi(j)}.$$

Containment of $2$-subsets in $3$-subsets is preserved, so every permutation of $X$ gives an automorphism of the configuration. Hence there are at least

$$5!=120$$

automorphisms.

Now let $\sigma$ be any automorphism of the configuration.

For each $i\in X$, consider the set

$$F_i={{i,j}:j\ne i}.$$

This consists of four points.

Any two points of $F_i$ are collinear, because

$${i,j},{i,k}$$

lie on the line corresponding to ${i,j,k}$.

Conversely, if four points are pairwise connected by configuration lines, they must be of the form $F_i$. Indeed, two points ${a,b}$ and ${c,d}$ are collinear exactly when the corresponding $2$-subsets intersect. Thus a family of four pairwise collinear points is a family of four $2$-subsets with pairwise nonempty intersection. Among the $2$-subsets of a $5$-element set, the only such maximal family is the collection of all pairs containing a fixed element $i$.

Hence the five sets $F_1,\dots,F_5$ are characterized intrinsically by the incidence structure.

Therefore $\sigma$ permutes the five sets $F_i$. Let the induced permutation of ${1,2,3,4,5}$ be $\pi$.

The point ${i,j}$ is the unique element of

$$F_i\cap F_j.$$

Thus

$$\sigma({i,j}) = F_{\pi(i)}\cap F_{\pi(j)} = {\pi(i),\pi(j)}.$$

Hence $\sigma$ is exactly the automorphism induced by $\pi$.

Every automorphism therefore arises from a unique permutation of the five symbols, and the number of admissible permutations is

$$5!=120.$$

We obtain

$$\boxed{24,\ 72,\ 120}.$$

Verification of Key Steps

For part (a), the essential point is that the four original lines are recoverable from the incidence structure alone. A careless argument might assume that every collinear triple is one of the given four triples. This must be checked. In the configuration formed by four lines in general position, the only triples lying on a common line are exactly the triples belonging to those four lines. Hence every automorphism necessarily permutes those four triples.

For part (b), the crucial issue is identifying the six star-lines intrinsically. If one merely counts incidences without distinguishing the three matching lines, one could incorrectly obtain a larger symmetry group. The six star-lines form a copy of $K_{3,3}$ under the relation “meet in a point”. Once this graph is recovered, every point becomes the intersection of a unique adjacent pair of star-lines, so the action on points is forced.

For part (c), the delicate step is proving that the families $F_i$ are uniquely determined. The argument uses the intersection model of $2$-subsets. Four pairwise intersecting $2$-subsets of a $5$-element set must share a common element. Without this verification one could not conclude that an automorphism induces a permutation of the five underlying symbols.

Alternative Approaches

For part (a), one may regard the six points as the six edges of a complete graph $K_4$. The four lines then correspond to the four stars at the vertices of $K_4$. An automorphism of the configuration becomes an automorphism of $K_4$, giving immediately $4!=24$.

For part (c), a more geometric approach uses the realization of the Desargues configuration by five planes in general position in three-dimensional space. Each point is the intersection of three planes, and each line is the intersection of two planes. Any permutation of the five planes induces a symmetry of the configuration. One then proves that the five planes can be reconstructed from the incidence structure, yielding the group $S_5$ of order $120$. This approach reflects the geometric origin of the configuration, but the subset model is shorter and makes the counting completely transparent.