Skip to main content
MathOverflow

Return to Question

adjusted rewrite statement
Source Link
Douglas Zare
Douglas Zare
  • 28k
  • 6
  • 90
  • 130

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

Consider all tuplesTake a set of 5 (ordered, not repeated) natural numbers, each between 1 and 50$50$ elements.

$S=\{(c_1,c_2,c_3,c_4,c_5) \in N^5 / \forall i \in [1,5], c_i \in [1, 50] \wedge \forall i,j \in [1,5], i < j => c_i < c_j\}$ 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?

I'd like to know the cardinality of the subsetThis collection of all those elements, withsubsets is known as a "Hamming" distance equallottery wheel or less than 3 toa any other tuplelotto design. That$L(v,k,p,t)$ is, I'm looking for the minimum number of subsets of a $v$ element set so that each subset ensuringhas size $k$ with the property that every $p$ element subset intersects at least 2 numbers of any other tuple are presentone $k$-subset in an element of said subsetat least $t$ points.

$S_3 = \{t \in S / \forall s \in S, \exists t / d_h(t,s) \leq 3\}$

where If you select $d_h$ refers to a non-rigorous definition of Hamming distance: differences between tuples, regardless$5$ out of the position.

So, besides my likely errors in the definitions (I don't really know how to describe$50$ numbers in a lottery which pays a prize for getting at least $S_3$ properly, apologies)$2$ numbers right, what I'm looking forthen you can ensure getting a prize if you buy a particular collection of $L(50,5,5,2)$ tickets. The question is to find $|S_3|$$L(50,5,5,2)$.

Hi,

Consider all tuples of 5 (ordered, not repeated) natural numbers, each between 1 and 50.

$S=\{(c_1,c_2,c_3,c_4,c_5) \in N^5 / \forall i \in [1,5], c_i \in [1, 50] \wedge \forall i,j \in [1,5], i < j => c_i < c_j\}$

I'd like to know the cardinality of the subset of all those elements, with a "Hamming" distance equal or less than 3 to any other tuple. That is, I'm looking for the minimum subset ensuring at least 2 numbers of any other tuple are present in an element of said subset.

$S_3 = \{t \in S / \forall s \in S, \exists t / d_h(t,s) \leq 3\}$

where $d_h$ refers to a non-rigorous definition of Hamming distance: differences between tuples, regardless of the position.

So, besides my likely errors in the definitions (I don't really know how to describe $S_3$ properly, apologies), what I'm looking for is $|S_3|$.

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

removed finite-groups tag
Link
Gerry Myerson
Gerry Myerson
  • 39.9k
  • 10
  • 186
  • 247
Redefining $S_3$
Source Link
chous
chous
  • 33
  • 5

Hi,

Consider all tuples of 5 (ordered, not repeated) natural numbers, each between 1 and 50.

$S=\{(c_1,c_2,c_3,c_4,c_5) \in N^5 / \forall i \in [1,5], c_i \in [1, 50] \wedge \forall i,j \in [1,5], i < j => c_i < c_j\}$

I'd like to know the cardinality of the subset of all those elements, with a "Hamming" distance equal or less than 3 to any other tuple. That is, I'm looking for the minimum subset ensuring at least 2 numbers of any other tuple are present in an element of said subset.

$S_3 = \{t \in S / \forall s \in S, d_h(t,s) \leq 3\}$$S_3 = \{t \in S / \forall s \in S, \exists t / d_h(t,s) \leq 3\}$

where $d_h$ refers to a non-rigorous definition of Hamming distance: differences between tuples, regardless of the position.

So, besides my likely errors in the definitions (I don't really know how to describe $S_3$ properly, apologies), what I'm looking for is $|S_3|$.

Hi,

Consider all tuples of 5 (ordered, not repeated) natural numbers, each between 1 and 50.

$S=\{(c_1,c_2,c_3,c_4,c_5) \in N^5 / \forall i \in [1,5], c_i \in [1, 50] \wedge \forall i,j \in [1,5], i < j => c_i < c_j\}$

I'd like to know the cardinality of the subset of all those elements, with a "Hamming" distance equal or less than 3 to any other tuple. That is, I'm looking for the minimum subset ensuring at least 2 numbers of any other tuple are present in an element of said subset.

$S_3 = \{t \in S / \forall s \in S, d_h(t,s) \leq 3\}$

where $d_h$ refers to a non-rigorous definition of Hamming distance: differences between tuples, regardless of the position.

So, besides my likely errors in the definitions, what I'm looking for is $|S_3|$.

Hi,

Consider all tuples of 5 (ordered, not repeated) natural numbers, each between 1 and 50.

$S=\{(c_1,c_2,c_3,c_4,c_5) \in N^5 / \forall i \in [1,5], c_i \in [1, 50] \wedge \forall i,j \in [1,5], i < j => c_i < c_j\}$

I'd like to know the cardinality of the subset of all those elements, with a "Hamming" distance equal or less than 3 to any other tuple. That is, I'm looking for the minimum subset ensuring at least 2 numbers of any other tuple are present in an element of said subset.

$S_3 = \{t \in S / \forall s \in S, \exists t / d_h(t,s) \leq 3\}$

where $d_h$ refers to a non-rigorous definition of Hamming distance: differences between tuples, regardless of the position.

So, besides my likely errors in the definitions (I don't really know how to describe $S_3$ properly, apologies), what I'm looking for is $|S_3|$.

Source Link
chous
chous
  • 33
  • 5