Skip to main content
8 of 9
added 650 characters in body
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

Final(?) answer: See the rest of the answer for terminology. As noted in a comment by @chous below. There is a solution with 36 blocks at this lottery systems site. This can be reduced to $35$ blocks. To do this with the solution in the link, replace the block $\ 3\ 11\ 37\ 42\ 47 $ with $3\ 9\ 11\ 37\ 47 $ and delete the block $ 9\ 12\ 22\ 27\ 47 .$ I will post an analysis of this solution in a new question I posted.


You are not using the positions at all. You have 50 points. $S$ is the set of all $\binom{50}{5}=2118760$ selections of 5 points. You want a subset $B \subset S$ such that any $s \in S$ intersects at least one $b \in B$ in at least 2 points. That is an interesting problem and does not immediately strike me as familiar. Call a member of $B$ a block. A given block intersects $152026$ members of $S$ in 2 or more points. This gives a lower bound of $14$ for the possible size of $B$. Of course this a weak bound since two disjoint blocks determine $200$ members of $S$ intersecting one in 2 points and the other in 3 and another $4000$ intersecting each in 2 points. If my calculations are correct, that raises the lower bound to at least $19$ blocks. I doubt that $20$ would suffice.

So far my record is 44 blocks.

Let me digress for some terminology (which I'll try to keep fairly standard). a design is a pair $D=(V,B)$ where $V$ is a set of $v$ vertices and a $B$ is a collection of subsets called blocks There are various names for designs which satisfy additional conditions. Two are

Every pair of points is in exactly one common block. (Then $D$ is called a linear space)

Every pair of points is in at least one common block and every block has the same number $k$ of points. (Then $D$ is called a $(v,k,2)$-covering design and the La Jolla Repository has information about these.)

When both conditions hold, $D$ is called a Steiner System $S(2,k,v).$ Many that one encounters arise from algebraic constructions. This is perhaps due to the Streetlight effect.

I'll coin the term super-linear space for a design such that every pair of points from $V$ occur in at least one common block but the blocks may have various sizes (since I don't know a standard name. It turns out that this might be called a lottery wheel although that term is not very specific)

You have $50$ points and do not require that every pair of points is in a block but do wish that from every 5 points (element of $S$), at least one pair is in at least one block. You also want all blocks to have $5$ points. I'll find it convenient to only require that each block have at most 5 points, then one can arbitrarily enlarge blocks to size 5.

All my constructions have this form: Split the points into 4 groups (or 2 or 3) and for each group take a super-linear space with no block having more than 6 points. Then any element of $S$ has two points in the same group and those two points are in a common block. Perhaps one can do better without this restriction. I include a few other possibilities in case it inspires anyone to get a better result.

44* blocks. Split into 4 groups of size 21,21,4 and 4. For each of the large groups take the 21 lines of a projective plane of order 4 and let the two small groups be 4 point blocks. Now any set in $S$ has at least two points in a common group and those two pints determine a unique block.


60 blocks: split the points into two sets of 25 and use the 30 lines of an affine plane of order 5 on each. This is overkill because any 3 element set has two points in some block. Perhaps there is a way to cull out some of the lines.

Under 52 blocks If the points are partitioned into 3 groups of 13 and one of 11 (with two fake points added in) then (for each group) the lines of a projective plane of order 3 were taken as blocks this would give a solution with 52 blocks of size 4. Delete $X,Y$ to improve this to 45 of size 4 and 6 of size 3 and one of size two. Now tack the block of size 2 onto a block of size 3 to get $51$ blocks (one of size 5). (If $X,Y$ are in different groups it might be better, I haven't checked.) One can also get rid of at least 3 more blocks as follows: take a block abcd, delete it and add b as a fifth point to a block containing c and another containing c, add c as a fifth point to two blocks containing d and a and add d as a fifth point to two blocks containing a and b.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104