Skip to main content
4 of 4
adjusted rewrite statement
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

How many elements with a hamming distance of 3 or less?

[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. $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)$.

chous
  • 33
  • 5