Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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!) –  user53153 Jan 1 '13 at 7:53
    
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. –  user1924939 Jan 1 '13 at 8:08
    
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. –  user1924939 Jan 1 '13 at 8:44
    
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. –  Hagen von Eitzen Jan 1 '13 at 11:53

1 Answer 1

up vote 7 down vote accepted

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

share|improve this answer
    
+1 Nice idea. I wonder if 210 is minimal. –  miracle173 Jan 1 '13 at 8:59
    
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. –  user1924939 Jan 1 '13 at 9:14
    
+1 Brilliant idea. –  user1551 Jan 1 '13 at 10:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.