Suppose that the latter is true. We are seeking an n value that is 1 mod pk and 2 mod pk-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, pk(pk-1). Not surprisingly, the answer is that n=m (mod pk(pk-1)), because we know that n=m satisfies both conditions. Therefore, the next number to satisfy these conditions is m+pk(pk-1), or p2k+1. We will later on in this solution show constructively that S(3,pk+1,p2k+1) exists for all values of p and k, where pk 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 pk. This means that n-2 is a multiple of pk(pk-1). The lowest possible value here is n=pk(pk-1)+2. The second-lowest value is n=2pk(pk-1)+2. As stated previously, we will show that in every case there is a solution with n=p2k+1. The difference between this value and the "second-lowest" value quoted above is -p2k+2pk-1 = -(pk-1)2≤0. Therefore, the "second-lowest" value cannot be the desired minimum. We are left only with the possibility that n=pk(pk-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,pk+1,p2k+1), where pk 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(pk). 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 ax+by=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,
(x1,y1),
(x2,y2) and
(x3,y3), we are looking for a circle
(x-a)2+(y-b)2=c
that passes through all three. This means
(x1-a)2+(y1-b)2=c,
(x2-a)2+(y2-b)2=c and
(x3-a)2+(y3-b)2=c.
By subtracting the first equation from the latter two equations we get
2(x2-x1)a +
2(y2-y1)b =
(x22+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 pk+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 pk. It is one element too small. Interestingly,
the total size of the plane is p2k 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,pk+1,p2k+1) and have
solved the riddle in full.