Finden von sich überschneidenden Teilmengen für einen gegebenen Binomialkoeffizienten

Ich entschuldige mich, wenn diese Frage für mathisfun.com besser geeignet ist, aber ich kann nur so weit über Kombinatrie und Mengenlehre lesen, bevor die ineinandergreifende Logik völlig verschwommen wird. Wenn dies ein völlig grundlegendes Konzept ist, können Sie es einfach benennen, damit ich die Mathematik selbst lesen und verstehen kann.

Das Ziel ist also, die Wiederholung von Fragen in einem Quiz zu minimieren, um die Erstellung eines Hauptschlüssels zu vermeiden (oder wirklich zu verlangsamen). Dies ist für einen Kunden und ich habe erklärt, dass die Anzahl der Fragen im Master-Pool riesig sein müsste, um dies wirklich realistisch zu machen, aber ich möchte ihnen die Mathematik hinter ihrer Idee zeigen.

Also schlugen sie vor, einen Pool mit 20 Fragen zu haben, wobei eine gegebene Menge eine 5-köpfige Teilmenge ist. Ich fand heraus, dass die Gesamtzahl der einzigartigen Quizes$\binom{20}{5}$wäre$\frac{20!}{5!(20-5)!}$oder 15504 einzigartige Quizes. Aber ich weiß, dass die meisten dieser Quizes nahezu identisch sein werden und dass es nicht so lange dauern wird, bis Betrüger alle 20 Fragen sehen, um den Schlüssel zu machen. Um mir das selbst zu beweisen (ohne die Mathematik zu kennen), habe ich die Gesamtkombinationen zu vereinfacht$\binom{4}{3}$, so:

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

Und ich sehe, dass man nur 2 Quizes sehen muss, um alle 4 Mitglieder des Master-Sets zu sehen. Da ich also weiß, dass die Anzahl der Kombinationen (Binominalkoeffizient!) Nicht der Anzahl der einzigartigen Erscheinungen des Master-Sets entspricht, würde ich gerne die tatsächliche Mathematik kennen, die damit verbunden ist, um dem Kunden zu zeigen, dass er zwar eine Menge Quizes hat, es aber nimmt nur$x$alle Mitglieder kennen.

Danke wie immer.

Nachtrag

Ein bisschen mehr Forschung hat mich zu dem NP-vollständigen Problem geführt, das als Exact Cover bekannt ist, das (wenn ich es richtig lese) eine präzise Menge von Teilmengen wäre, die eine Vereinigung haben, die der ursprünglichen Master-Menge entspricht. Ich möchte nur klarstellen, dass diese Einschränkung der perfekten Überlappung für meine Frage nicht erforderlich ist, sondern nur die minimale Anzahl von Teilmengen, die zu einer Vereinigung führen würde, die unabhängig von der Wiederholung alle Master-Set-Mitglieder enthält, um zu zeigen, wie viele Teilmengen es gibt benötigt, um die ursprüngliche Menge zu kennen (unter der Annahme, dass der Suchende der Master-Menge die Gesamtzahl der Mitglieder kennt). Ich zwickte mein Mikroexperiment aus$\binom{4}{3}$Zu$\binom{4}{2}$was dazu führt, dass 6 Kombinationen und die Ableitung der Master-Menge mit einer bestimmten Anzahl beliebiger Teilmengen nicht mehr möglich sind. Stattdessen bekomme ich:

{a, b, c, d} = { {ab} ; {ac} ; {Anzeige} ; {bc} ; {bd} ; {CD} }

die den Master-Satz mit den ersten drei ($a$) Gruppen oder die genaue Abdeckung von${ {a,b}; {c,d} }$. Dies lässt mich denken, dass die minimalen Teilmengen, die zum Ableiten der ursprünglichen Menge benötigt werden, gleich der Anzahl der Teilmengen sind, in denen ein bestimmtes Mitglied vorkommt (also in diesem Fall 3$a$s, aber das stimmt nicht mit dem überein$\binom{4}{3}$, wo es mit 2 Teilmengen zu finden ist. Die nächste offensichtliche Lösung (für mich) ist, dass die Mindestanzahl, die zum Ableiten des Master-Sets (blind) benötigt wird, die Hälfte der Gesamtzahl der Teilmengen ist, aber ich möchte wirklich einen Link zu einem Beweis oder einer einfachen englischen Demonstration, wie Ein Pool von 20 Fragen würde 7752 Teilmengen erfordern, um mit Sicherheit zu wissen, dass alle 20 Mitglieder mindestens einmal aufgetreten sind.

Noch einmal Danke.

Frage als Wahrscheinlichkeit:

Ich habe eine Tüte mit Scrabble-Steinen und ich weiß Folgendes:

1. Die Tüte enthält 20 Fliesen,
2. Jede Kachel ist einzigartig (keine zwei Kacheln haben den gleichen Charakter),
3. Die Kacheln stammen aus einem viel größeren (und ansonsten irrelevanten) Satz eines Erweiterungssatzes, der Zahlen und nicht-lateinische Buchstaben enthält, wodurch jeder Vorteil zunichte gemacht wird, zu wissen, dass dieser Satz von 20 aus einem größeren, aber begrenzten Satz stammt (mit anderen Worten , die Zeichen sind nur informativ füreinander und ich kann alles Klingonisch oder eine Mischung aus Chinesisch und Tamil bekommen. Ich sollte nichts über das Set vermuten, außer was in der Tasche ist).

Folgende Schritte darf ich in der angegebenen Reihenfolge beliebig oft durchführen:

1. Ziehe 5 Kacheln heraus,
2. Schreiben Sie die gezeichneten Zeichen auf,
3. Legen Sie die Kacheln zurück in den Beutel.
4. Aufschäumen, ausspülen, wiederholen.

Außerdem: Ich habe magische Finger, die mich daran hindern, den gleichen 5er-Satz zweimal zu ziehen, wodurch die Anzahl der Ziehungen von unendlich auf 15504 mögliche Ziehungen reduziert wird.

Mein Ziel ist es, irgendwann alle 20 Zeichen aufgeschrieben zu haben und dann mit dem Zeichnen aufzuhören.

Ich weiß, dass die Gesamtzahl der einzigartigen Kombinationen, die ich ziehen könnte, ist$\binom{20}{5}$das ist 15504. Ich weiß auch, dass die erforderlichen Mindestziehungen gleich sind$\lceil{20}/{5}\rceil$, was sehr viel Glück wäre. Was mich interessiert, ist die maximale Anzahl von Ziehungen, die erforderlich sind, um alle 20 Zeichen aufzudecken.