[This is a complete rewrite which makes some of the comments redundant or irrelevant.]


Take a set of $50$ elements. How many subsets of size $5$ are needed so that every subset of size $5$ will intersect at least one of these in at least $2$ points? 


This collection of subsets is known as a lottery wheel or a [lotto design](http://www.cs.umanitoba.ca/~vanrees/revlottodesign.pdf). $L(v,k,p,t)$ is the minimum number of subsets of a $v$ element set so that each subset has size $k$ with the property that every $p$ element subset intersects at least one $k$-subset in at least $t$ points. If you select $5$ out of $50$ numbers in a lottery which pays a prize for getting at least $2$ numbers right, then you can ensure getting a prize if you buy a particular collection of $L(50,5,5,2)$ tickets. The question is to find $L(50,5,5,2)$.



How many elements with a hamming distance of 3 or less?
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](http://en.wikipedia.org/wiki/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.


