Using your Head is Permitted

July 2009 solution

The first step is to establish the n value we are looking for, for each m value. For this, we will use the same logic as in the non-existence proofs of the September 2007 solution. Namely, for an n value to be a potential for any given m, it must at least satisfy the following three criteria:
  1. 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).
  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).
  3. 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.
In our case, m=pk+1 for some prime p and some natural k. The third condition implies that n-2 is a multiple of pk-1. Note that n-2 and n-1 are consecutive integers and are therefore co-prime. Therefore, only one of them can divide by p. The second condition therefore implies that either n-2 is a multiple of pk or n-1 is a multiple of pk.

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.

Back to riddle

Back to main page