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.

My apologies if this question is more appropriate for mathisfun.com, but I can only get so far reading about combinatrics and set theory before the interlocking logic becomes totally blurred. If this is a totally fundamental concept, feel free just to name it so I can read and understand the math myself.

So the goal is to minimize repetition of questions on a quiz to avoid (or really to slow down) the creation of a master key. This is for a client and I've explained that to make this truly realistic the number of questions in the master pool would need to be huge, but I want to show them the math behind their idea.

So they suggested having a 20 question pool with a given set being a 5-member subset. I figured out that the total number of unique quizes $\binom{20}{5}$ would be $\frac{20!}{5!(20-5)!}$ or 15504 unique quizes. But I know that most of those quizes will be near identical and that it won't take as long for cheaters to see all 20 questions to make the key. To prove this to myself (without knowing the math), I simplified the total combinations to $\binom{4}{3}$, like so:

{a, b, c, d} = { {a,b,c}; {a,b,d}; {b,c,d}; {a,c,d} }

And I see that it only takes seeing any 2 quizes to see all 4 members of the master set. So knowing that the number of combinations (binomial coefficient!) is not equivalent to number of unique appearances of the master-set, I'd like to know the actual math involved to show the client that while they have a ton of quizes, it only takes $x$ to know all members.

Thanks as always.

Addendum

A bit more research has introduced me to the NP-complete problem known as Exact Cover, which would be (if I'm reading it right) a precise set of subsets which have a union equal to the original master-set. I just want to clarify that this constraint of perfect overlap is not necessary for my question, only the minimum number of subsets that would result in a union that has all master-set members, regardless of repetition, in order to demonstrate how many subsets are needed to know the original set (with the assumption that the seeker of the master-set knows the total membership count). I tweaked my micro-experiment from $\binom{4}{3}$ to $\binom{4}{2}$ resulting in 6 combinations and the ability to derive the master-set no longer being possible with a specific number of arbitrary subsets. Instead I get:

{a, b, c, d} = { {ab} ; {ac} ; {ad} ; {bc} ; {bd} ; {cd} }

which could derive the master set using the first three ($a$) groups, or the exact cover of ${ {a,b}; {c,d} }$. This has me thinking that the minimum subsets needed to derive the original set is equal to the number of subsets where any given member occurs (so in this case 3 $a$s, but this doesn't match up to the $\binom{4}{3}$, where it can be found with 2 subsets. The next obvious solution (to me) is that the minimum number needed to derive the master-set (blindly) is half of the total number of subsets, but I would really want a link to a proof or a simple-english demonstration on how a pool of 20 questions would require 7752 subsets to know with certainty that all 20 members have appeared at least once.

Again, thanks.

Question as Probability:

I have a bag of Scrabble tiles and I know the following:

  1. The bag contains 20 tiles,
  2. Each tile is unique (no two tiles have the same character),
  3. The tiles come from a much larger (and otherwise irrelevant) set of an expansion set including numbers and non-Roman alphabet characters, thus removing any advantage of knowing that this set of 20 comes from a larger-but-limited set (in other words, the characters are only informative to each other and I may get all Klingon or a mix of Chinese and Tamil. I should not assume anything about the set other than what is in the bag).

I am allowed to perform the following steps in the order given as many times as I want:

  1. Pull out 5 tiles,
  2. Write down the characters drawn,
  3. Return the tiles to the bag.
  4. Lather, Rinse, Repeat.

Also: I have magical fingers that prevent me from drawing the same set of 5 twice, thus reducing the number of draws from infinity to 15504 possible draws.

My objective is to have all 20 characters written down eventually and then stop drawing characters.

I know that the total number of unique combinations I could draw is $\binom{20}{5}$ which is 15504. I also know that the minimum draws required is equal to $\lceil{20}/{5}\rceil$, which would be very lucky. What I am interested in is the maximum number of draws required to reveal all 20 characters.

share|improve this question
    
I do not think that this is the right question for the actual real-life problem: Avoidance of repetition for a particular person will actually help people to create a complete question list quickly. –  Phira Jan 5 at 23:07
add comment

1 Answer 1

With 20 questions total; and 5 per quiz, and a sole goal to repeat as late as possible (as i unserstand your question), you shall start repeating at the fifth quiz. If you number them arbitrarily, you have $1 -5$ in quiz $1$, and $16 -20$ in quiz $4$ ( if your sole goal is to minimize/prolong the time to repetition). By the same goal, quiz $5$ will repeat $1-5$, etc. This is probably not what you'd implement as you could predict the precise questions precisely for an upcoming quiz (after a while); but - as I understand your question - what you'd do. It is not really a binomial coefficient question (I did not underrstand your separation of the pool leading to $\binom{4}{3}$). To meaningfully use something else, you need to impose further conditions.

share|improve this answer
    
I see that you're saying (I think) -- that the subject could derive the master-set with minimum 4 subsets if they draw the 4 non-intersecting subsets, which in my problem would be incredibly fortunate. That would be the true minimum needed, just as having all 15504 would be the true maximum, as having all subsets would eliminate any doubt. What I'm hoping exists is a formula to determine the minimum number of subsets the culprit needs to blindly obtain to ensure all master-set members will be present, knowing only the pool size and sample size. –  Anthony Feb 3 '13 at 6:56
    
I see. So you draw 5 tests at random, each time? Then you can only calculate probabilities (assuming say 5 per draw, equal likelihood of drawing any in each draw); and you could never guarantee all have been drawn (it just becomes increasingly unlikely). Is the setup? –  gnometorule Feb 3 '13 at 12:47
    
Is this the setup, I meant to say. –  gnometorule Feb 3 '13 at 12:48
    
...but I also increasingly get the feeling you are asking an interesting question I simply don't get. :) –  gnometorule Feb 3 '13 at 12:55
1  
I think you are looking at something not a million miles removed from "the coupon collector's problem" and you will find much literature if you search for that keyphrase. –  Gerry Myerson Feb 7 '13 at 11:09
show 8 more comments

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.