A l'Université Paire de Regina, on considère qu'il est très important de faire
partie de plusieurs comités. L'association de la faculté a établi les règles suivantes:

1.  chaque comité doit avoir un nombre PAIR de membres,
2. chaque paire de comités a un nombre PAIR de membres en commun,
3. aucune paire de comités n'a exactement les mêmes membres.
   

De l'autre côté de la ville se trouve l'Université Impaire de Regina, rivale de la première, qui accorde aussi beaucoup d'importance aux comités. Ses règles sont un peu différentes:

1. chaque comité doit avoir un nombre IMPAIR de membres,
2. chaque paire de comités a un nombre PAIR de membres en commun.
   

Notre problème du mois:

La faculté de l'Université Paire compte seulement 20 membres, alors que celle l'Université Impaire en compte 1000. Cette dernière essaie de former autant de comités que possible en respectant ses règles énoncées ci-haut. Pourtant, elle se retrouve avec moins de comités que l'Université Paire. Comment est-ce possible?

Solution au problème MP31

Ce mois-ci, Pierre Bornsztein (de France), et Juan Mir Pieras (d'Espagne) nous ont répondu. Voici la solution de Bornsztein, à laquelle on a ajouté quelques commentaires de Mir.

Nombre de comités à l'Université Paire.

La faculté de l'Université Paire consiste en dix couples mari-femme. Une personne fait partie d'un comité si et seulement si son conjoint en fait partie. De cette façon, tout comité a bien un nombre pair de membres, et toute paire de comités a un nombre pair de membres en commun. Avec dix couples, on peut former 2¹⁰ = 1024 comités (ou 1023, si on exclue le comité vide).

Nombre de comités à l'Université Impaire.

Avec 1000 personnes à l'Université Impaire, on peut former 1000 comités de une personne, ce qui est moins que le nombre de comités que l'on peut former à l'Université Paire. En utilisant l'algèbre linéaire, on arrive à démontrer que c'est là le nombre maximum de comités que l'on peut former: Supposons que l'on puisse former k comités C₁, C₂, ..., C_k. Notons M la matrice
1000 par k dont la j-ième colonne est le vecteur caractéristique du comité j, c'est à dire M(i,j) = 1 si la personne i fait partie du comité j, et M(i,j) = 0 sinon. Notons M^T la matrice transposée de M, et T =  M^T · M. Alors T est une matrice k par k, où la valeur T(i,j) est le nombre de personnes faisant conjointement partie des comités C_i et C_j. Ainsi, T(i,j) est impair si i = j,
et pair sinon. En réduisant toutes les valeurs modulo 2, on obtient une matrice identité, dont
le déterminant est 1. Ceci implique que le déterminant de T est impair; en particulier, le déterminant de T n'est pas 0, donc T est inversible, et son rang est k. Par conséquent, le rang de M est au moins k, puisque le rang d'une matrice est au plus le minimum entre son nombre de lignes et son nombre de colones, on a k <= 1000.

Mir note qu'en formant 1000 comités distincts de 999 personnes, on obtient aussi un ensemble de 1000 comités satisfaisant aux conditions requises. Ainsi, il y a plus d'une façon de former 1000 comités satisfaisant aux conditions requises. Certaines de ces solutions sont beaucoup plus complexes; par exemple, dans le groupe des 14 personnes 0, 1, 2, ..., 11, 12, et *, on peut former les 13 comités de 5 personnes donnés dans le tableau suivant

Ainsi que le comité {0, 1, ..., 12}. Chacun de ces comités a un nombre impair de personnes, et le lecteur peut vérifier que l'intersection de deux comités est toujours paire.

Le problème provient du manuscrit Linear Algebra Methods in Combinatorics de László Babai et Péter Frankl, qui l'ont tiré d'une note de 1969 de E.R. Berlekamp. Nous espérions que quelqu'un puisse trouver une démonstration élémentaire du fait que l'Université Impaire puisse former au plus 1000 comités, mais les constructions dérivées des géométries projectives, telles que la précédente, suggèrent qu'il est peut-être impossible d'éviter l'algèbre linéaire.