5
$\begingroup$

I'm trying so solve following problem:

Let's say, we have a set $A=\{1,2,3,...,49\}$.

Now, I am defining sets $A_1, A_2, A_3,...,A_n$ as follow: $A_1=\{a_1,a_2,a_3,...,a_{30}\}$, $A_2= \{b_1,b_2,b_3,...b_{30}\}$, and so on, where all elements of sets $A_i$ are also elements of set $A$, which means they are subsets of set $A$. (All sets $A_i$ have $30$ elements).

Now, I am looking for a set $C=\{ A_1,A_2,A_3,...,A_n \}$ so, that if I pick randomly $6$ elements of set $A$, they will be (at least) in one of sets $A_i$.

What is $n$? Let's see: first of all, how much possibilities are to pick $6$ elements of set $A$? There are $\binom{49}{6}=\large\frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{6!}=13,983,816$

Secondly, how much of these possibilities covers one of sets $A_i$? Because set $A_i$ has $30$ elements, it covers $\binom{30}{6}=\large\frac{30 \cdot 29 \cdot 28 \cdot 27 \cdot 26 \cdot 25}{6!}=593,775$

Now dividing both results, it gives $23.55$ and this means, that we need at least $n=24$ (probably more, I am not sure).

So the question is, how do you find the set $C$?

Let's say, we can start so: $A_1=\{1,2,3,...,30\}$, this will be first set. But what next? With some algorithm I can implement it in C or Java, but I don't know how to start. Thanks.

$\endgroup$
4
  • $\begingroup$ To avoid any confusion: the goal is to make sure than any 6-element subset of $A$ is contained in some of the chosen sets $A_i$, is this correct? (Also, welcome to Math.SE!) $\endgroup$
    – user53153
    Jan 1, 2013 at 7:53
  • $\begingroup$ Thanks! Yes, or in other words: to make sure that any 6-element subset of A is contained at least in one of sets Ai. $\endgroup$ Jan 1, 2013 at 8:08
  • $\begingroup$ One more remark: I am trying also make "n" small as possible. I see one way to solve the problem, but not much elegant: I can generate 24 sets Ai with random numbers, then check all possible 13,983,816 6-element subsets of A (using Java), and then for those 6-element subsets, that are not contained in any Ai, generate additional Ai sets. In this way I can not get n small as possible.I thought, maybe there is more elegant mathematical way to solve my problem. $\endgroup$ Jan 1, 2013 at 8:44
  • $\begingroup$ Note that any two sets of 30 numbers share at least 11 numbers, thus share ${11\choose 6}=462$ outcomes. Taking this into account, the 23.55 must be replaced with 23.98, which would still fit 24, but makes it seem less likely. $\endgroup$ Jan 1, 2013 at 11:53

1 Answer 1

7
$\begingroup$

One possible approach is to partition $A$ into 10 sets (say $B_i$), each of size 5 (one will be of size 4). Define your $A_j$ as union of any 6 of the above $B_i$. So you get $\binom{10}{6}$ such $A_j$ (some of them will have size 29, but you can throw in some random element if you want to make it 30). Any 6 element set touches at most 6 blocks $B_i$ and hence is present in one of the above $A_j$. This gives an upper bound for size of $C$ as $\binom{10}{6} = 210$.

$\endgroup$
1
  • $\begingroup$ Thanks, interesting and simple solution! So we know how to get 210 sets, and now I must think harder and try to find a way to make less sets. $\endgroup$ Jan 1, 2013 at 9:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .