Conjuntos: mínimo garantizado y fórmulas para contar

¿Cuántas personas deben tener necesariamente todas las características pedidas? Los datos no siempre determinan el número exacto: a menudo permiten hallar un mínimo garantizado. Partimos de un acertijo, deducimos una fórmula para cualquier número de conjuntos y distinguimos esta pregunta del recuento exacto.

Laboratorio: contar con conjuntos · Laboratorio visual de Venn

1. El acertijo de los 100 médicos

En un hospital trabajan 100 médicos: 75 hablan inglés, 80 español, 85 francés y 90 alemán. ¿Cuál es el mínimo garantizado de médicos que hablan los cuatro idiomas? Una misma persona puede pertenecer a varios grupos.

La respuesta no es «exactamente 30», sino «al menos 30, y 30 es posible».

Calcular y explicar

2. Contar las ausencias en lugar de las presencias

Fijamos un universo U con N elementos y k subconjuntos A₁,…,Aₖ. Escribimos aᵢ=|Aᵢ| para el tamaño del grupo i. S=a₁+⋯+aₖ cuenta pertenencias, no personas distintas, y puede superar N. Quien está en todos los grupos no tiene ninguna ausencia.

En el grupo i faltan N−aᵢ elementos. Las ausencias suman M=(N−a₁)+⋯+(N−aₖ)=kN−S. Una persona puede faltar en varios grupos: el número de personas con alguna ausencia es como máximo M, sin superar N. El complementario de la intersección es la unión de los complementarios: U∖(A₁∩⋯∩Aₖ)=(U∖A₁)∪⋯∪(U∖Aₖ).

x ≥ N−min(N,M) = max(0,N−M) = max(0,S−(k−1)N)

3. Fórmula general y demostración por recuento

Sea x=|A₁∩⋯∩Aₖ| el número común. Estas x personas aportan kx pertenencias. Cada una de las otras N−x pertenece como máximo a k−1 grupos. Por tanto:

S ≤ kx+(k−1)(N−x)
S ≤ kx+(k−1)N−(k−1)x
S ≤ x+(k−1)N
x ≥ S−(k−1)N.

Como x≥0, obtenemos la fórmula buscada cuando solo conocemos N y los tamaños de los grupos, con 0≤aᵢ≤N:

x mínimo = max(0, a₁+⋯+aₖ−(k−1)N)

Con dos grupos restamos N; con tres, 2N; con cuatro, 3N. Para los médicos: max(0,75+80+85+90−3×100)=max(0,330−300)=30. El máximo con cero evita una respuesta negativa. «Mínimo cero» significa que no se garantiza ninguna persona común, no que la intersección sea necesariamente vacía.

4. Por qué se puede alcanzar el límite

Una desigualdad no demuestra por sí sola que el mínimo sea alcanzable. Si M≤N, asignamos las N−aᵢ ausencias de cada grupo a personas todas distintas. Exactamente M personas tienen una ausencia y N−M no tienen ninguna: el mínimo de la fórmula.

Si M≥N, imaginamos a las N personas en círculo. Asignamos las ausencias del primer grupo a personas consecutivas; seguimos con el segundo desde donde terminamos y luego con los demás, dando otra vuelta cuando haga falta. Cada bloque tiene como máximo N personas, de modo que nadie falta dos veces en el mismo grupo. Al menos N asignaciones consecutivas cubren a todos: nadie pertenece a todos los grupos. La fórmula da precisamente cero.

La construcción respeta todos los tamaños iniciales. No supone otras restricciones: si se fijaran también intersecciones concretas, habría que comprobarlas aparte. El laboratorio construye y verifica una distribución incluso cuando M≥N.

Calcular y explicar

5. El máximo: seguro frente a posible

La intersección no puede tener más elementos que el grupo más pequeño. Anidar los conjuntos del menor al mayor permite alcanzar el máximo.

x máximo = min(a₁,…,aₖ)

Para los médicos, el máximo es 75. Incluimos a los 75 anglófonos en los 80 hispanohablantes, estos en los 85 francófonos y estos en los 90 germanohablantes; 10 quedan fuera de todos. Los totales son los mismos que en la distribución con mínimo 30, pero ahora 75 hablan todos los idiomas. Por tanto, esos cuatro totales no determinan un número exacto entre 30 y 75.

Si mínimo y máximo coinciden, el número queda determinado. Un grupo vacío obliga a cero miembros comunes; si todos los grupos son U, el número es N. Un tamaño negativo o aᵢ>N no es un caso difícil: es un dato imposible.

Calcular y explicar

6. Otra clase: recuentos exactos con dos conjuntos

Para N elementos conocemos a=|A|, b=|B| e i=|A∩B|. La suma a+b cuenta dos veces a los miembros comunes: restamos una copia. A diferencia del problema del mínimo garantizado, conocemos la intersección.

|A∪B| = a+b−i
solo A = a−i; solo B = b−i
exactamente uno = a+b−2i
ninguno = N−a−b+i

De 30 estudiantes, 18 hacen deporte, 16 música y 7 ambas actividades. ¿Cuántos hacen al menos una actividad, exactamente una o ninguna?

Los datos son compatibles si y solo si max(0,a+b−N)≤i≤min(a,b). Equivale a exigir que las cuatro regiones tengan recuentos no negativos.

Calcular y explicar

7. Problemas inversos: hallar la intersección

Si z elementos no pertenecen a ninguno de los dos conjuntos, la unión tiene N−z miembros. Partimos de N−z=a+b−i y despejamos i sin inventar otra regla:

i = a+b−N+z

De 40 personas, 25 leen la revista A, 22 la revista B y 5 ninguna. ¿Cuántas leen ambas?

Comprueba siempre 0≤i≤min(a,b). Por ejemplo, N=20, a=8, b=7, z=0 daría i=−5: datos incompatibles, porque los grupos no pueden cubrir a las 20 personas. No sustituyas −5 por cero; señala la incoherencia.

Calcular y explicar

8. Tres conjuntos: unión, exactamente uno, exactamente dos

Escribimos a=|A|, b=|B|, c=|C|, p=|A∩B|, q=|A∩C|, r=|B∩C| y t=|A∩B∩C|. Las intersecciones por parejas incluyen t: p no significa «A y B pero no C». Sean S₁=a+b+c y S₂=p+q+r.

|A∪B∪C| = S₁−S₂+t
ninguno = N−S₁+S₂−t
exactamente uno = S₁−2S₂+3t
exactamente dos = S₂−3t
al menos dos = S₂−2t

En la primera fórmula, alguien presente en los tres grupos se cuenta 3−3+1=1 vez. «Solo A», «solo B» y «solo C» valen a−p−q+t, b−p−r+t y c−q−r+t. «Solo AB», «solo AC» y «solo BC» valen p−t, q−t y r−t. Estos valores, la intersección triple y la región exterior deben ser no negativos.

Ejemplo: N=100, a=60, b=50, c=40, p=30, q=25, r=20, t=15.

Calcular y explicar

9. Porcentajes y comprobaciones: la misma base

Las fórmulas también funcionan para proporciones sobre el mismo universo. Para porcentajes p₁,…,pₖ, el porcentaje mínimo común es max(0,p₁+⋯+pₖ−100(k−1))%. Los 75%, 80%, 85%, 90% de los médicos garantizan al menos 30%. Un porcentaje exacto se convierte en recuento con N×p/100, comprobando la compatibilidad con enteros. Los porcentajes redondeados no son datos exactos.

No combines el 70% de todos los alumnos de un colegio con el 60% de solo los alumnos deportistas: tienen denominadores distintos. Primero usa un mismo universo. El laboratorio admite recuentos enteros, no porcentajes: conviértelos antes de introducirlos.

10. ¿Qué fórmula elegir?

• ¿Solo tamaños y pregunta «al menos cuántos en todos»? Usa el mínimo garantizado.
• ¿Dos conjuntos con tamaños e intersección conocidos? Usa inclusión–exclusión para recuentos exactos.
• ¿Conoces el número exterior? Halla primero la unión y después la intersección.
• ¿Tres conjuntos con todas las intersecciones necesarias? Parte de la triple y reconstruye ocho regiones.

Identifica el universo; traduce «todos», «al menos uno», «exactamente uno»; comprueba los datos; aplica la fórmula; verifica con regiones disjuntas. No confundas garantía con recuento exacto ni uses max(0,…) para ocultar datos incompatibles en un cálculo exacto.

Diez ejercicios: inténtalo antes de abrir la solución

1. De 50 personas, 35 están en A y 40 en B. ¿Mínimo y máximo comunes?

2. Tres grupos tienen 20, 18, 17 miembros de 30 personas: ¿cuántos se garantizan en todos?

3. Cinco competencias: 95, 94, 93, 92, 91 personas de 100. ¿Mínimo común?

4. En los 100 médicos, ¿una distribución con 75 que hablan los cuatro contradice el mínimo 30?

5. N=25, |A|=16, |B|=14, |A∩B|=8. Halla unión, exactamente uno, ninguno.

6. N=60, |A|=35, |B|=30; 10 están fuera de ambos. Halla la intersección.

7. N=20, |A|=15, |B|=12, intersección=3. ¿Datos posibles?

8. N=100; a=60, b=50, c=40; p=30, q=25, r=20, t=15. ¿Cuántos pertenecen al menos a dos grupos?

9. El 90% y el 85% de la misma población tienen dos requisitos. ¿Porcentaje mínimo con ambos?

10. N=10 y tamaños 10, 10, 7. ¿Hace falta más información para saber cuántos están en todos?

Repasa elementos y operaciones · Diez problemas avanzados sobre conjuntos · Laboratorio: contar con conjuntos

Para profundizar

MIT · Mathematics for Computer Science, Cardinality Rules