Un sujet qui s’appelle en anglais le « Oddtown problem » est fréquemment discuté pendant les cours introductifs de combinatoire. Voici l’histoire.

Une grande ville est confrontée à l’explosion du nombre de clubs que son service des sports doit gérer (ou du nombre d’associations que son service culturel soutient, etc). Aucune loi ne régit la formation de ces clubs et les citoyens adorent en créer de nouveaux. En fait, pour créer un « club », il suffit de déposer la liste des membres du club à la mairie ; cette liste définit le club par ses adhérents, et deux clubs sont distincts si et seulement si la liste des membres est différente. L’engouement associatif de cette ville est tel que rapidement, toutes les listes, tous les appariements, brefs tous les clubs possibles sont progressivement enregistrés : il y a tous les clubs égocentriques (avec un seul membre), ce qui fait un club de cette sorte par habitant ; puis tous les clubs à deux membres (toutes les paires), les clubs à trois habitants, etc. Pour une ville de trente habitants, cela fait déjà $1073741824$ listes qu’il va falloir intégrer au nouveau logiciel informatique de la commune ...

Alors cette ville étrange décide de légiférer sur les clubs qui regroupent ses habitants ; voici les règles qu’elle impose :

1. Chaque club doit avoir un nombre impair de membres.
2. Deux clubs doivent toujours avoir un nombre pair de membres en commun.

La question est alors de savoir combien de clubs peuvent être formés, et la réponse est fournie par le théorème connu sous le nom de « Oddtown Theorem » [1] :

Le nombre de clubs est automatiquement inférieur au nombre d’habitants.

Ainsi, dans une ville de trente habitants, il y aura au plus trente clubs.
Bien loin des $1073741824$ possibilités initiales.

Il est assez difficile de donner le nom de l’auteur de ce résultat qui semble appartenir au folklore mathématique. Le Oddtown cache son identité ; en revanche, on peut dire dans quelle partie des mathématiques il se situe. Cette partie est la théorie extrémale des ensembles et appartient au domaine plus large dénommé « combinatoire extrémale ».
Les problèmes étudiés consistent à estimer le nombre maximal d’objets (ensembles, nombres, graphes, etc.) qui peuvent exister lorsqu’on leur impose certaines restrictions.

Le théorème ci-dessus est un résultat étonnant.
Si $n$ désigne le nombre d’habitants, le nombre total de clubs est $2^n$ (par exemple $2^n=1073741824$ si $n=30$). Il semblerait que les restrictions « paires » ou « impaires » devraient diviser l’ensemble des clubs par deux soit $2^n/2$ clubs avec encore une croissance exponentielle. La borne supérieure $n$ parait alors surprenante, n’est-ce pas ?

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

Ce premier opus (voir aussi Oddtown et Eventown Partie II) de notre voyage à travers ces étranges villes et bourgades ne nécessite aucun bagage mathématique, à l’exception de la dernière petite partie qui contient les démonstrations. Notre but est de convaincre le lecteur que l’éternel jeu « pair - impair » reste captivant après quelques millénaires et des générations de joueurs déguisés en mathématiciens.

Clubs dans une ville Oddtown

Il est facile de trouver des exemples de clubs pour illustrer le théorème Oddtown, voici quelques-uns.

• Chaque habitant forme son propre club.

Toutes les intersections entre les clubs sont alors vides : elles contiennent $0$ membre, ce qui est un nombre pair. Nous obtenons donc autant de clubs que d’habitants, ce qui est le maximum annoncé par le théorème.

Voici d’autres exemples, moins individualistes.

Si le nombre $n$ d’habitants est pair, on peut proposer une construction duale à notre première construction.

• Chaque club contient tous les habitants sauf un.

L’intersection entre deux clubs contient toujours un nombre pair d’habitants (tous les habitants sauf deux), et il y a encore autant de clubs que d’habitants.

Pour exhiber une multitude de solutions diverses, voici une construction inductive :
on commence par partager la ville en deux groupes de $p$ et $q$ habitants, avec donc $n=p+q$ ; puis, on choisit $p$ clubs et $q$ clubs dans ces deux parties qui satisfont les contraintes oddtown, par exemple les $p$ clubs individualistes pour la première partie, et les $q$ clubs à $q-1$ membres dans la seconde si $q$ est pair.

Combien existe-t-il de façons différentes pour former les (familles maximales de) clubs dans le village Oddtown ?
Cette question a fait l’objet de plusieurs travaux. Il a été prouvé que le nombre de solutions grandit comme $2^{n^2}$. Il y a donc au plus $n$ clubs, mais le nombre de stratégies pour constituer ces $n$ clubs (si on en veut $n$) est gigantesque.

Le jumeau du village Oddtown

Le théorème dans lequel les mots « pair » et « impair » sont échangés ressemble au théorème Oddtown. Plus précisément, considérons une ville (jumelée avec une ville Oddtown) : cette ville, qui comporte $n$ habitants, forme des clubs pairs avec toujours un nombre impair de membres en commun entre deux clubs.

Le nombre de clubs dans une ville jumelle de Oddtown ne dépasse jamais $n$ ; de plus, si $n$ est pair, ce nombre ne dépasse pas $n-1$.

On peut déduire ce résultat du théorème Oddtown.
Supposons que nous avons une famille $F$ de clubs. Ajoutons dans notre ville et dans chacun des clubs une âme morte [2] : on fait comme si la ville avait un habitant de plus, membre de tous les clubs. Les clubs complétés satisfont alors les conditions (1) et (2) imposées par les lois de type Oddtown ; le théorème Oddtown implique alors que le nombre des clubs, $|F|$, ne dépasse pas le nombre d’habitants, c’est-à-dire $n+1$ (puisqu’il faut compter l’âme morte ajoutée artificiellement).

On peut améliorer cette borne !
Supposons d’abord que $n$ est impair. Considérons la population totale de la ville : tous les habitants vivants, sans l’habitant fantôme que nous avions ajouté. Considérons cet ensemble d’habitants comme un nouveau club ; puisqu’il ne contient pas le fantôme, il ne fait pas partie de la famille des clubs complétés. Pourtant, en ajoutant ce club à la famille des clubs complétés, les conditions (1) et (2) sont encore satisfaites. Par conséquent, $|F|$ ne dépasse pas $n$.

Supposons maintenant que $n$ est pair. Soit $X$ un club et $\overline{X}$ le club complémentaire (qui consiste en l’ensemble des habitants qui n’appartiennent pas à $X$). Il est clair que $\overline{X}$ n’appartient pas à notre famille $F$ car $X$ et $\overline{X}$ ont un nombre pair d’habitants en commun (à savoir $0$). Si $X$ contient un nombre pair d’habitants, alors $\overline{X}$ aussi, et pour tout autre club $X'$, le nombre de membres en commun entres $\overline{X}$ et $X'$ est impaire. On peut alors remplacer $X$ dans $F$ par $\overline{X}$ sans toucher aux autres clubs. En faisant ce remplacement si nécessaire, on peut exclure un habitant de tous les clubs et réduire la situation au cas de $n-1$ habitants.

Les villes de type Eventown : « pair » $+$ « pair » $=$ exponentiel !

Dans une ville de type Eventown, avec $n$ habitants, les clubs sont régis par les règles suivantes :

• (i) Chaque club doit avoir un nombre pair de membres.
• (ii) Deux clubs doivent toujours avoir un nombre pair de membres en commun.

La situation revient alors à la « normale » : le nombre de clubs possibles grandit exponentiellement avec $n$. Plus précisément, le théorème Eventown donne le nombre maximal de différents clubs dans Eventown :

Le nombre de clubs dans une ville Eventown à $n$ habitants est au plus $2^{\frac{n}{2}}$ si $n$ est pair et au plus $2^{\frac{n-1}{2}}$ si $n$ est impair.

Voici un exemple.
On n’admet aux clubs que des couples mariés et l’on forme avec ces couples tous les clubs possibles. Cela nous donne $2^c$ clubs où $c$ est le nombre de couples. Nous avons un espoir d’avoir $c=\frac{n}{2}$ couples si $n$ est pair, et $c=\frac{n-1}{2}$ couples si $n$ est impair (dans une ville où tout le monde vit en couple, sans enfant ...).

Montrez que le nombre de clubs avec un nombre impair de membres et avec un nombre impair de membres en commun peut aussi grandir exponentiellement.

La solution simple ci-dessus n’est pas la seule façon de former les clubs dans le monde Eventown. Nous allons maintenant voir d’autres solutions.

Doubly-Even-Town et les codes correcteurs

La différence principale entre « pair » et « impair » est que le pair peut être « doublement pair » (multiple de $4$), « triplement pair » (multiple de $8$), etc. Il est impossible de définir les notions analogues dans le cas impair [3].

Les villes de type Doubly-Even-Town deviennent encore plus étranges, mais de plus en plus even en même temps. Voici les règles de Doubly-Even-Town.

• (i-2) Chaque club doit avoir un nombre doublement pair de membres
  (c’est-à-dire, un nombre divisible par 4).
• (ii) Deux clubs doivent avoir un nombre pair de membres en commun.

Là, on est sûr que le nombre de clubs va diminuer par rapport à celui de Eventown, car ce « doublement » semble être une condition forte ? Pas toujours !

Dans une commune Doubly-Even Town, on peut avoir $2^{\frac{n}{2}}$ clubs
si (et seulement si) le nombre d’habitants $n$ est un multiple de $8$.

Le problème de trouver des familles de clubs qui satisfassent la condition (i-2) est lié à la théorie des codes correcteurs, fascinante science à l’interface entre les mathématiques, informatique et la théorie de télécommunications. Pour expliquer ce lien, et pour trouver des solutions à notre problème, nous allons introduire une nouvelle notation.

Les habitants sont rangés de $1$ à $n$ (par exemple, on les classe par ordre alphabétique). Chaque club est alors représenté par une suite de $0$ et de $1$ à $n$ termes \[ X=(x_1\,\ldots\,x_n) \] où $x_i=1$ si le $i$-ème habitant est un membre du club, et $x_i= 0$ sinon.
Si $X$ et $X'$ sont deux suites, on définit leur somme : \[ X+X'=(x_1+x_1'\,\ldots\,x_n+x_n'), \] en utilisant la convention $1+1=0$, car nous ne nous intéressons qu’à la parité.

Voici une construction pour $n=8$ habitants. Considérons les clubs suivants : \[ \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} \] Il est facile de voir que non seulement tous les clubs déterminés par les listes $X_i$ mais aussi toutes leurs sommes sont doublement paires. Par exemple, $X_1+X_2=(1\,1\,0\,0\,1\,1\,0\,0)$, ou encore $X_1+X_2+X_3+X_4=(1\,1\,1\,1\,1\,1\,1\,1)$, etc..
Nous obtenons une famille de $2^4=16$ clubs.

Cet exemple porte le nom de code de Hamming, le premier exemple de code correcteur utilisé dans la théorie de l’information.

Richard Hamming (1915 — 1998)

Imaginez que vous voulez transmettre un message en utilisant des symboles $0$ et $1$ à la place des lettres de l’alphabet latin (ou russe). Il suffit d’une petite erreur et votre information est perdue ! Pour éviter cet écueil, on peut utiliser dans le message les $16$ mots du code de Hamming (les $X_i$ ci-dessus et toutes leurs sommes). Si une erreur s’est glissée dans le message, elle peut encore être corrigée ; en effet, la « distance » entre tous les mots du code est au moins $4$, donc il faudrait au moins deux erreurs dans un même mot pour ne plus pouvoir le reconnaitre. Si chaque
mot $X_i$ du code de Hamming est utilisé pour coder les lettres d’un alphabet (à 16 lettres), on peut alors transmettre des informations sans risque important d’erreur.

Construire une famille de $2^{4m}$ clubs qui satisfassent (i-2) et (ii) dans une ville avec $8m$ habitants.

L’idée la plus simple est d’utiliser la construction de Hamming $m$ fois.
Mais, cette solution n’est pas unique. Pour $n=24$, il existe un code remarquable qui s’appelle le code de Golay qui n’est pas équivalent au code de Hamming répété. Le code de Golay peut corriger $3$ erreurs dans un mot !

Les démonstrations

Notre parcours sur une piste rouge se termine par une partie un peu plus abrupte que nous cachons dans le dépliant suivant [4].

L’article Oddtown et Eventown Partie II
« Une variation doublement paire sur le thème « Oddtown » est la suite du présent article.

Pour une lecture plus approfondie nous recommandons les livres suivants. [5]