Encontrar subconjuntos que se cruzan para un coeficiente binomial dado

Mis disculpas si esta pregunta es más apropiada para mathisfun.com, pero solo puedo llegar hasta cierto punto leyendo sobre combinatría y teoría de conjuntos antes de que la lógica entrelazada se vuelva totalmente borrosa. Si este es un concepto totalmente fundamental, no dude en nombrarlo para que yo mismo pueda leer y entender las matemáticas.

Entonces, el objetivo es minimizar la repetición de preguntas en un cuestionario para evitar (o realmente ralentizar) la creación de una clave maestra. Esto es para un cliente y le expliqué que para que esto sea realmente realista, la cantidad de preguntas en el grupo maestro debería ser enorme, pero quiero mostrarles las matemáticas detrás de su idea.

Por lo tanto, sugirieron tener un grupo de 20 preguntas con un conjunto dado que sea un subconjunto de 5 miembros. Descubrí que el número total de cuestionarios únicos$\binom{20}{5}$sería$\frac{20!}{5!(20-5)!}$o 15504 cuestionarios únicos. Pero sé que la mayoría de esos cuestionarios serán casi idénticos y que los tramposos no tardarán tanto en ver las 20 preguntas para hacer la clave. Para probarme esto a mí mismo (sin saber las matemáticas), simplifiqué las combinaciones totales a$\binom{4}{3}$, al igual que:

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

Y veo que solo se necesita ver 2 cuestionarios para ver los 4 miembros del conjunto maestro. Entonces, sabiendo que la cantidad de combinaciones (¡coeficiente binomial!) no es equivalente a la cantidad de apariciones únicas del conjunto maestro, me gustaría saber las matemáticas reales involucradas para mostrarle al cliente que si bien tiene un montón de cuestionarios, es solo toma$x$para conocer a todos los miembros.

Gracias como siempre.

Apéndice

Un poco más de investigación me ha presentado el problema NP-completo conocido como Exact Cover, que sería (si lo estoy leyendo bien) un conjunto preciso de subconjuntos que tienen una unión igual al conjunto maestro original. Solo quiero aclarar que esta restricción de superposición perfecta no es necesaria para mi pregunta, solo el número mínimo de subconjuntos que daría como resultado una unión que tiene todos los miembros del conjunto maestro, independientemente de la repetición, para demostrar cuántos subconjuntos son necesitaba conocer el conjunto original (suponiendo que el buscador del conjunto maestro conoce el recuento total de miembros). Modifiqué mi micro-experimento de$\binom{4}{3}$a$\binom{4}{2}$lo que da como resultado 6 combinaciones y la capacidad de derivar el conjunto maestro ya no es posible con un número específico de subconjuntos arbitrarios. En cambio, obtengo:

{a, b, c, d} = {{ab}; {ca}; {anuncio} ; {antes de Cristo} ; {b}; {cd} }

que podría derivar el conjunto maestro usando los primeros tres ($a$) grupos, o la cobertura exacta de${ {a,b}; {c,d} }$. Esto me hace pensar que los subconjuntos mínimos necesarios para derivar el conjunto original es igual a la cantidad de subconjuntos en los que aparece cualquier miembro dado (entonces, en este caso, 3$a$s, pero esto no coincide con el$\binom{4}{3}$, donde se puede encontrar con 2 subconjuntos. La siguiente solución obvia (para mí) es que el número mínimo necesario para derivar el conjunto maestro (a ciegas) es la mitad del número total de subconjuntos, pero realmente me gustaría un enlace a una prueba o una demostración en inglés simple sobre cómo un grupo de 20 preguntas requeriría 7752 subconjuntos para saber con certeza que los 20 miembros han aparecido al menos una vez.

Gracias otra véz.

Pregunta como probabilidad:

Tengo una bolsa de fichas de Scrabble y sé lo siguiente:

1. La bolsa contiene 20 fichas,
2. Cada ficha es única (no hay dos fichas con el mismo carácter),
3. Los mosaicos provienen de un conjunto mucho más grande (y por lo demás irrelevante) de un conjunto de expansión que incluye números y caracteres del alfabeto no romano, lo que elimina cualquier ventaja de saber que este conjunto de 20 proviene de un conjunto más grande pero limitado (en otras palabras , los personajes son solo informativos entre sí y es posible que obtenga todo el klingon o una mezcla de chino y tamil. No debo asumir nada sobre el conjunto que no sea lo que está en la bolsa).

Se me permite realizar los siguientes pasos en el orden indicado tantas veces como quiera:

1. Saca 5 fichas,
2. Anota los caracteres dibujados,
3. Devuelve las fichas a la bolsa.
4. Hacer espuma, enjuagar, repetir.

Además: tengo dedos mágicos que me impiden dibujar el mismo conjunto de 5 dos veces, reduciendo así el número de sorteos de infinito a 15504 sorteos posibles.

Mi objetivo es tener los 20 caracteres escritos eventualmente y luego dejar de dibujar caracteres.

Sé que el número total de combinaciones únicas que podría dibujar es$\binom{20}{5}$que es 15504. También sé que los sorteos mínimos requeridos son iguales a$\lceil{20}/{5}\rceil$, que sería muy afortunado. Lo que me interesa es el número máximo de sorteos necesarios para revelar los 20 personajes.