Un problema llamado en inglés ’’Oddtown problem’’ es frecuentemente discutido durante los cursos introductorios de combinatoria. Aquí está la historia.

Una gran ciudad está enfrentada a la explosión del número de clubes que su servicio de deportes debe administrar (o del número de asociaciones que su servicio cultural regula, etc). Ninguna ley rige la formación de esos clubes, y a los ciudadanos les gusta crear nuevos. De hecho, para crear un ’’club’’, basta con entregar la lista de sus miembros a la alcaldía : esta lista define al club por sus adherentes, y dos clubes son distintos si y solamente si la lista de sus miembros es diferente. El entusiasmo asociativo de esta ciudad es tal que rápidamente todas las listas, todos los emparejamientos, en resumen todos los clubes posibles quedan progresivamente registrados : están todos los clubes egocéntricos (con un sólo miembro), lo que hace que haya un club de este tipo por habitante ; luego todos los clubes con dos miembros (todas las parejas), los clubes con tres habitantes, etc. Para un pueblo de treinta habitantes eso hace ya $1073741824$ listas que va a ser necesario integrar al nuevo programa informático de la comuna...

Entonces esta extraña ciudad decide legislar sobre los clubes que agrupan a sus habitantes. Éstas son las reglas que impone :

1. Cada club debe tener un número impar de miembros.
2. Dos clubes deben tener siempre un número par de miembros en común.

La pregunta ahora es saber cuántos clubes pueden formarse, y la respuesta está suministrada por el teorema conocido bajo el nombre de ’’Oddtown Theorem’’ [1] :

El número de clubes es automáticamente inferior al número de habitantes.

Así, en una ciudad de treinta habitantes habrá a lo más treinta clubes. Bastante lejos de las $1073741824$ posibilidades iniciales.

Es bastante difícil dar el nombre del autor de ese resultado que parece pertenecer al folklore matemático. El Oddtown esconde su identidad. Sin embargo, se puede decir en qué parte de las matemáticas se sitúa él. Esta parte es la teoría extrema de conjuntos y pertenece al campo más amplio denominado ’’combinatoria extrema’’ Los problemas estudiados consisten en estimar el número máximo de objetos (conjuntos, números, grafos, etc.) que pueden existir cuando uno les impone algunas restricciones.

El teorema mencionado anteriormente es un resultado sorprendente. Si $n$ designa el número de habitantes, el número total de clubes es $2^n$ (por ejemplo $2^n=1073741824$ si $n=30$). Parecería que las restricciones ’’pares’’ o ’’impares’’ deberían dividir el conjunto de clubes por dos, o sea $2^n/2$ clubes, aún con un crecimiento exponencial. El límite superior $n$ parece entonces sorprendente ¿verdad ?

« A Club of Gentlemen », Joseph Highmore (1730).

Este primer opus (vea también Oddtown y Eventown, Parte II) de nuestro viaje a través de estas extrañas ciudades y aldeas no necesita ningún conocimiento matemático previo, con excepción de la pequeña última parte que contiene las demostraciones. Nuestro objetivo es convencer al lector que el eterno juego ’’par - impar’’ se mantiene cautivante después de algunos milenios y generaciones de jugadores disfrazados de matemáticos.

Clubes en una ciudad Oddtown

Es fácil encontrar ejemplos de clubes para ilustrar el teorema Oddtown. Aquí hay algunos.

• Cada habitante forma su propio club.

Todas las intersecciones entre los clubes son ahora vacías : contienen $0$ miembros, que es un número par. Obtenemos entonces tantos clubes como habitantes, que es el máximo anunciado por el teorema.

Aquí hay otros ejemplos, menos individualistas.

Si el número $n$ de habitantes es par, se puede proponer una construcción dual a nuestra primera construcción.

• Cada club contiene a todos los habitantes, menos a uno.

La intersección entre dos clubes contiene siempre un número par de habitantes (todos los habitantes salvo dos) y aún hay tantos clubes como habitantes.

Para mostrar una multitud de soluciones diversas, aquí hay una construcción inductiva. Se comienza por dividir la ciudad en dos grupos de $p$ y $q$ habitantes, con $n=p+q$ ; después se eligen $p$ clubes y $q$ clubes en esos dos grupos que satisfacen las restricciones oddtown : por ejemplo los $p$ clubes individualistas para la primera parte, y los $q$ clubes con $q-1$ miembros en la segunda si $q$ es par.

¿Cuántas formas diferentes hay de formar (familias máximas de) clubes en la ciudad Oddtown ? Esta pregunta ha sido el objeto de muchos trabajos. Se probó que el número de soluciones crece como $2^{n^2}$. Hay a lo más $n$ clubes, pero el número de estrategias para constituir esos $n$ clubes (si uno desea $n$) es gigantesca.

El gemelo de la ciudad Oddtown

El teorema en el cual las palabras ’’par’’ e ’’impar’’ se intercambian se parece al teorema Oddtown. Más exactamente, consideremos una ciudad ’’gemela con una ciudad Oddtown’’. Esta ciudad, que tiene $n$ habitantes, forma clubes pares siempre con un número impar de miembros en común entre dos clubes.

El número de clubes en una ciudad gemela de Oddtown no sobrepasa nunca $n$ ; además, si $n$ es par, ese número no sobrepasa $n-1$.

Se puede deducir ese resultado del teorema Oddtown. Supongamos que tenemos una familia $F$ de clubes. Agreguemos en nuestra ciudad y en cada uno de los clubes una alma muerta [2] : se hace como si la ciudad tuviera un habitante más, miembro de todos los clubes. Los clubes completados satisfacen entonces las condiciones (1) y (2) impuestas por las leyes de tipo Oddtown ; el teorema Oddtown implica entonces que el número de clubes $|F|$, no sobrepasa el número de habitantes, es decir $n+1$ (ya que hay que contar el alma muerta agregada artificialmente).

¡Se puede mejorar ese límite ! Supongamos primero que $n$ es impar. Consideremos la población total de la ciudad : todos los habitantes vivos, sin el habitante fantasma que habíamos agregado. Consideremos este conjunto de habitantes como un nuevo club ; ya que no contiene al fantasma, no forma parte de la familia de clubes completados. Sin embargo, al agregar este club a la familia de clubes completados, las condiciones (1) y (2) son aún satisfechas. En consecuencia, $|F|$ no sobrepasa $n$.

Supongamos ahora que $n$ es par. Sea $X$ un club y $\overline{X}$ el club complementario (que consiste en el conjunto de habitantes que no pertenecen a $X$). Está claro que $\overline{X}$ no pertenece a nuestra familia $F$ ya que $X$ y $\overline{X}$ tienen un número par de habitantes en común (a saber $0$). Si $X$ contiene un número par de habitantes, entonces $\overline{X}$ también, y dado cualquier otro club $X'$, el número de miembros en común entre $\overline{X}$ y $X'$ es impar. Se puede entonces reemplazar $X$ en $F$ por $\overline{X}$ sin tocar a los otros clubes. Haciendo este reemplazo si es necesario, se puede excluir a un habitante de todos los clubes y reducir la situación al caso de $n-1$ habitantes.

Las ciudades de tipo Eventown : ’’par’’ $+$ ’’par’’ $=$ ¡exponencial !

En una ciudad de tipo Eventown, con $n$ habitantes, los clubes se rigen por las siguientes reglas :

• (i) Cada club debe tener un número par de miembros.
• (ii) Dos clubes deben tener siempre un número par de miembros en común.

La situación vuelve entonces a la ’’normalidad’’ : el número de clubes posibles crece exponencialmente con $n$. Más exactamente, el terorema Eventown da el número máximo de diferentes clubes en Eventown :

El número de clubes en una ciudad Eventown con $n$ habitantes es a lo más $2^{\frac{n}{2}}$ si $n$ es par y a lo más $2^{\frac{n-1}{2}}$ si $n$ es impar.

Aquí hay un ejemplo. No se admite en los clubes sino a parejas casadas y se forma con esas parejas todos los clubes posibles. Eso nos da $2^c$ clubes donde $c$ es el número de parejas. Tenemos la esperanza de tener $c=\frac{n}{2}$ parejas si $n$ es par, y $c=\frac{n-1}{2}$ parejas si $n$ es impar (en una ciudad donde todo el mundo vive en pareja, sin hijos..).

Muestre que el número de clubes con un número impar de miembros y con un número impar de miembros en común puede también aumentar exponencialmente.

La solución simple de arriba no es la única manera de formar los clubes en el mundo Eventown. Vamos ahora a ver otras soluciones.

Doblemente-Even-Town y los códigos correctores

La diferencia principal entre ’’par’’ e ’’impar’’ es que el par puede ser ’’doblemente par’’ (múltiplo de $4$), ’’triplemente par’’ (múltiplo de $8$), etc. Es imposible definir las nociones análogas en el caso impar [3].

Las ciudades de tipo Doblemente-Even-Town pasan a ser entonces más extrañas, pero cada vez más even al mismo tiempo. Estas son las reglas del Doblemente-Even-Town.

• (i-2) Cada club debe tener un número doblemente par de miembros (es decir, un número divisible por 4).
• (ii) Dos clubes deben tener un número par de miembros en común.

Ahí, uno está seguro que el número de clubes va a disminuir en relación con el de Eventown, ya que ese ’’doblemente’’... ¿parece ser una condición fuerte ? ¡No siempre !

En una comuna Doblemente-Even Town, se puede tener $2^{\frac{n}{2}}$ clubes si (y solamente si) el numero de habitantes $n$ es un múltiplo de $8$.

El problema de encontrar familias de clubes que satisfagan la condición (i-2) está vinculado a la teoría de los códigos correctores, fascinante ciencia en la frontera entre las matemáticas, la informática y la teoría de telecomunicaciones. Para explicar este vínculo y para encontrar soluciones a nuestro problema, vamos a introducir una nueva notación.

Los habitantes son ordenados de $1$ a $n$ (por ejemplo, se les clasifica por orden alfabético). Cada club está entonces representado por una serie de $0$ y de $1$ con $n$ términos

\[ X=(x_1\,\ldots\,x_n) \]

donde $x_i=1$ si el $i$-ésimo habitante es un miembro del club, y $x_i= 0$ si no. Si $X$ y $X'$ son dos series, se define su suma :

\[ X+X'=(x_1+x_1'\,\ldots\,x_n+x_n'), \]

utilizando la convención $1+1=0$, ya que sólo nos interesamos en la paridad.

Aquí hay una construcción para $n=8$ habitantes. Consideremos los clubes siguientes :

\[ \begin{array}{rcl} X_1 &=& (1 \,0 \,0 \,0 \,0 \,1 \,1 \,1)\\ X_2 &=& (0\,1\,0\,0\,1\,0\,1\,1)\\  X_3 &=& (0\,0\,1\,0\,1\,1\,0\,1)\\ X_4 &=& (0\,0\,0\,1\,1\,1\,1\,0). \end{array} \]

Es fácil ver que no solamente todos los clubes determinados por las listas $X_i$ sino también todas sus sumas son doblemente pares. Por ejemplo, $X_1+X_2=(1\,1\,0\,0\,1\,1\,0\,0)$, o incluso
$X_1+X_2+X_3+X_4=(1\,1\,1\,1\,1\,1\,1\,1)$, etc..
Obtenemos una familia de $2^4=16$ clubes.

Este ejemplo lleva el nombre de código de Hamming, el primer ejemplo de código corrector utilizado en la teoría de la información.

Richard Hamming (1915 — 1998)

Imagine que usted quiere transmitir una mensaje utilizando símbolos $0$ y $1$ en lugar de las letras del alfabeto latino (o ruso). ¡Basta un pequeño error y su información se pierde ! Para evitar este escollo, se puede utilizar en el mensaje las $16$ palabras del código de Hamming (las $X_i$ de arriba y todas sus sumas). Si un error se desliza en el mensaje, puede aún ser corregido ; en efecto, la ’’distancia’’ entre todas las palabras del código es al menos $4$, por lo tanto haría falta al menos dos errores en una misma palabra para ya no poder reconocerla. Si cada palabra $X_i$ del código de Hamming es utilizada para codificar las letras de un alfabeto (de 16 letras), se puede entonces transmitir informaciones sin riesgo importante de error.

Construir una familia de $2^{4m}$ clubes que satisfagan (i-2) y (ii) en una ciudad con $8m$ habitantes.

La idea más simple es utilizar la construcción de Hamming $m$ veces. Pero esta solución no es única. Para $n=24$, existe un código notable que se llama el código de Golay que no es equivalente al código de Hamming repetido. ¡El código de Golay puede corregir $3$ errores en una palabra !

Las demostraciones

Nuestro recorrido termina en una parte un poco más abrupta que nosotros escondemos en el folleto siguiente [4].

Para una lectura más profunda, recomendamos los siguientes libros [5]