- There is a total of
*n*(*n*-1)(*n*-2)/6 triplets, and each subset contains exactly*m*(*m*-1)(*m*-2)/6 of them. Therefore,*m*(*m*-1)(*m*-2) must be a divisor of*n*(*n*-1)(*n*-2). - Pick some element of the original set of size
*n*and consider only triplets that include it. There are (*n*-1)(*n*-2)/2 such triplets. They are not represented in subsets that don't contain the original element, but in all other subsets there are exactly (*m*-1)(*m*-2)/2 of them. This means that (*m*-1)(*m*-2) must be a divisor of (*n*-1)(*n*-2). - Pick two specific elements and consider only triplets that include both.
For the same reasoning, this yields that
*m*-2 is a divisor of*n*-2.

Suppose that the latter is true. We are seeking an *n* value that is
1 mod *p*^{k} and 2 mod *p*^{k}-1.
Because these two moduli are co-prime (they are consecutive integers), we can
use the Chinese remainder theorem to find the value of *n* mod their
multiple, *p*^{k}(*p*^{k}-1). Not
surprisingly, the answer is that *n*=*m*
(mod *p*^{k}(*p*^{k}-1)), because we
know that *n*=*m* satisfies both conditions. Therefore, the next
number to satisfy these conditions is
*m*+*p*^{k}(*p*^{k}-1), or
*p*^{2k}+1. We will later on in this solution show
constructively that
S(3,*p*^{k}+1,*p*^{2k}+1) exists for
all values of *p* and *k*, where *p*^{k} is
3 mod 4. The question remains, however, whether
there is any smaller solution.

For a smaller solution to exist, it must come from the other alternative.
Namely, *n*-2 is a multiple of *p*^{k}. This means
that *n*-2 is a multiple of
*p*^{k}(*p*^{k}-1). The lowest
possible value here is
*n*=*p*^{k}(*p*^{k}-1)+2.
The second-lowest value is
*n*=2*p*^{k}(*p*^{k}-1)+2. As
stated previously, we will show that in every case there is a solution with
*n*=*p*^{2k}+1. The difference between this value
and the "second-lowest" value quoted above is
-*p*^{2k}+2*p*^{k}-1 =
-(*p*^{k}-1)^{2}≤0. Therefore, the
"second-lowest" value cannot be the desired minimum. We are left only with the
possibility that
*n*=*p*^{k}(*p*^{k}-1)+2 is a
smaller solution.

In order to check this value, we return to the first criterion:
*n*(*n*-1)(*n*-2) is a multiple of
*m*(*m*-1)(*m*-2). Because in this case
*n*-2=(*m*-1)(*m*-2), the question is whether
*n*(*n*-1) is a multiple of *m*. Equivalently, we are asking
whether ((*m*-1)(*m*-2)+1)((*m*-1)(*m*-2)+2) is a multiple
of *m*. This is a polynomial in *m* whose free variable, it is easy
to verify, is 12. All other parts of the polynomial clearly divide by *m*,
so for the last condition to hold, *m* must be a divisor of 12.

Combining this with the condition that *m* should be a multiple of 4
(given in the question), we are left with two values of *m* to consider: 4
and 12. Regarding 4, we are trying to ascertain the existence of
*S*(3,4,8).
Regarding 12, we are looking for a *S*(3,12,112). Here, the mitigation
comes into play, as we know that *S*(3,12,112) does not exist.

*S*(3,4,8), however, does exist, as does any *S*(3,4,*n*) where
*n*>4 is a power of 2. These Steiner systems can be constructed easily as
follows: consider the set of numbers from 0 to *n*-1 as the original set,
and pick from this set all subsets of size 4 such that the xor of the four
elements is zero. It is not difficult to verify that these subsets satisfy
the conditions of being a Steiner system.

Let us now return to the main problem. We wish to construct a system
S(3,*p*^{k}+1,*p*^{2k}+1), where
*p*^{k} is 3 mod 4 (a condition that appears in the
question).

In order to do this, we will use a well-known theorem in geometry: through any three distinct points in the plane, there passes either exactly one circle or exactly one straight line. We will tweak this theorem by using finite fields instead of real-number coordinates for the plane.

Specifically, consider the field *F*=GF(*p*^{k}).
Our "plane" will be the set of ordered (*x*,*y*) pairs, where
*x* and *y* are both members of *F*. Each (*x*,*y*)
pair will be a "point" in this plane. A "straight line" will
be the set of (*x*,*y*) pairs satisfying the equation
*a**x*+*b**y*=*c* for some parameters *a*,
*b* and *c*, also being members
of *F* (*a* and *b* not both zero). Lastly, a "circle" will
be the set of (*x*,*y*) pairs satisfying the equation
(*x*-*a*)^{2}+(*y*-*b*)^{2}=*c*, with
*a*, *b* and *c* being members of *F* and *c*≠0.

First, let us verify that the geometrical theorem continues to hold in the
finite field. Given any three points,
(*x*_{1},*y*_{1}),
(*x*_{2},*y*_{2}) and
(*x*_{3},*y*_{3}), we are looking for a circle
(*x*-*a*)^{2}+(*y*-*b*)^{2}=*c*
that passes through all three. This means
(*x*_{1}-*a*)^{2}+(*y*_{1}-*b*)^{2}=*c*,
(*x*_{2}-*a*)^{2}+(*y*_{2}-*b*)^{2}=*c* and
(*x*_{3}-*a*)^{2}+(*y*_{3}-*b*)^{2}=*c*.
By subtracting the first equation from the latter two equations we get
2(*x*_{2}-*x*_{1})*a* +
2(*y*_{2}-*y*_{1})*b* =
(*x*_{22+y22-x12-y12) and
2(x3-x1)a +
2(y3-y1)b =
(x32+y32-x12-y12).
}

This is a set of two linear equations with two unknowns: *a* and *b*.
If the linear equations are independent, this has a unique solution for
*a* and *b*. Substituting this solution into the original circle
equations we also get a unique solution for *c*. On the other hand,
the linear equations are not independent if and only if all three points are
on a single straight line (as can be seen by examining the equations'
coefficients). In the case where the points are on a straight line,
this line is unique, and its equation is unique up to multiplication by a
scalar. (Three points that are on a straight line cannot all be on the same
circle. To show this, merely subtract the line equation from the circle
equation. This leads to a quadratic equation, and it cannot have three distinct
solutions.)

This proves that the geometrical property that interests us continues to hold in the finite field. In this way we construct a set of subsets of the points on the plane (all possible lines and circles), satisfying that any three points appear together in exactly one subset. However, this is still not a Steiner system, because the sizes of the various subsets are not all the same.

The size of every circle is the desired *p*^{k}+1.
(For proof of this see last month's riddle, which
was a hint for this month's riddle.) The size of every straight line, however,
is only *p*^{k}. It is one element too small. Interestingly,
the total size of the plane is *p*^{2k} points, which, also,
is one point smaller than the size we are aiming for, for *n*.

We solve all these remaining problems in one fell swoop by adding to the plane
one additional element, representing "infinity". Each straight line will pass
through infinity, but no circle will. It can easily be verified that in this
way we bring all subsets to the required size, the total set is of the
desired size, and, most important of all, the criteria of a Steiner system
continue to hold. In this way, we've constructed explicitly
S(3,*p*^{k}+1,*p*^{2k}+1) and have
solved the riddle in full.