Using your Head is Permitted

July 2009 riddle

UPDATE (1 August): So far, there have been no complete solutions for the July riddle. The riddle will therefore run one extra month, but with the following hint:

The riddle asks to find subsets of a set of size n such that any three elements uniquely identify a subset. How would you solve this riddle if the original set was not a finite set of some size, n, but rather the infinite set R2?

A new August riddle will be posted, as usual, in parallel to this one.

This question came to me while working with Yaniv Erlich on a related problem.

A Steiner system, often denoted S(k,m,n), is a set of subsets, each of size m, of a set of size n, such that any k out of the n original elements appear together in exactly one subset. (For a more formal definition, see Wikipedia.)

"Using your Head is Permitted" has looked at Steiner systems before. The riddle for September 2007 had to do with constructing several Steiner systems of desired sizes with k=2.

This month's riddle deals with the construction of Steiner systems with k=3. In particular, for any m that is a multiple of 4 that satisfies that m-1 is a prime power (or a prime) you are asked to construct S(3,m,n) with the minimal possible n. (Assuming n>m, to exclude the trivial Steiner system, containing only one subset.) You are asked to prove in each case the minimality of n.

One mitigation: In 1981, Sloane and Thompson proved that S(3,12,112) does not exist. You are allowed to use their result without re-proving it.

List of solvers:

Oded Margalit (3 August 10:20)

Elegant solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page