¿Cuántos grupos distintos pueden convivir bajo unas reglas que parecen casi inofensivas? La paridad esconde un límite sorprendentemente rígido.
Los clubes incompatibles
Enunciado
En una ciudad viven 100 personas y se han formado varios clubes.
Cada club tiene un número impar de miembros, mientras que dos clubes distintos siempre tienen un número par de miembros en común.
¿Cuál es el mayor número de clubes que puede haber?
Ver solución
Solución
Respuesta: puede haber como máximo 100 clubes.
Representa cada club mediante un vector de 100 ceros y unos: un 1 indica que la persona pertenece al club y un 0 que no pertenece. Trabajamos módulo 2, de modo que solo importa la paridad.
El producto escalar de cada vector consigo mismo es 1, porque el club tiene un número impar de miembros. En cambio, el producto escalar de dos vectores distintos es 0, porque ambos clubes tienen un número par de miembros en común.
Supongamos que una suma no vacía de estos vectores fuera igual al vector cero. Elegimos uno de los vectores incluidos y tomamos el producto escalar con él. Su producto consigo mismo aporta 1 y todos los demás aportan 0, de modo que el resultado es 1.
Pero el producto escalar del vector cero con cualquier vector es 0. Esta contradicción demuestra que los vectores de los clubes son linealmente independientes.
Como se encuentran en un espacio de dimensión 100, no puede haber más de 100.
El límite se alcanza formando 100 clubes de una sola persona: cada club tiene un miembro y dos clubes distintos no comparten ninguno.
Por tanto, el máximo es 100 clubes.