Peut-on faire visiter Paris en 7 jours à 15 touristes, par groupes de 3, de telle sorte qu’à la fin du séjour chaque touriste ait passé un jour avec chacun des autres?
Plus généralement, on peut se demander pour quelles valeurs de \(a\), \(b\), \(n\), on peut faire visiter Paris en \(b\) jours à \(n\) touristes, par groupes de \(a\), de telle sorte qu’à la fin du séjour chaque touriste ait passé exactement un jour avec chacun des autres.
Une condition nécessaire est que \(a\) divise \(n\) et que \(n-1=b(a-1)\) puisque chaque touriste voyage avec \(a-1\) touristes chaque jour et qu’on veut qu’il ait vu tout le monde exactement une fois au bout de \(b\) jours. Par exemple, si \(q\) est un entier, on peut prendre \(n=q^2\), \(a=q\) et \(b=q+1\), ou bien \(n=q^3+q^2+q+1\), \(a=q+1\) et \(b=q^2+q+1\) (le problème initial est de ce type avec \(q=2\)).
Nous encourageons le lecteur à essayer de faire visiter Paris à \(4\) touristes en \(3\) jours par groupes de \(2\), puis à \(9\) touristes en \(4\) jours par groupes de \(3\), avant de lire ce qui suit.
4 touristes en 3 jours par groupes de 2
Numérotons \(1,2,3,4\) les touristes. Il n’y a aucun choix: \(1\) doit passer un jour avec \(2\), un avec \(3\) et un avec \(4\) et lesdeux autres doivent voyager ensemble, ce qui nous donne la solution suivante.
— Jour 1: \((1,2)\) et \((3,4)\),
— Jour 2: \((1,3)\) et \((2,4)\),
— Jour 3: \((1,4)\) et \((2,3)\).
9 touristes en 4 jours par groupes de 3
Le problème est nettement plus dur et une solution par tâtonnements assez problématique. La solution est de se demander comment encoder ces \(9\) touristes, et si on remarque que \(9=3\times 3\), il est naturel de les voir comme des éléments du plan sur le corps \({\bf F}_3={\bf Z}/3{\bf Z}\) à \(3\) éléments, et donc de les voir comme des couples \((x,y)\) d’éléments de \({\bf F}_3\times {\bf F}_3\). Ce plan contient \(4\) droites vectorielles: une telle droite a une équation de la forme \(y=\lambda x\), avec \(\lambda\in{\bf F}_3\), ou est la droite \(x=0\). Si on note \(0,1,2\) les éléments de \({\bf F}_3\) (avec \(1+2=0\) et \(2\times 2=1\)), ces droites sont les droites engendrées par \((1,0)\), \((1,1)\), \((1,2)\) et \((0,1)\). À chaque droite vectorielle correspond une partition du plan en droites parallèles affines ayant chacune \(3\) éléments. Comme par deux points il passe une et une seule droite affine, et qu’une droite affine est parallèle à une unique droite vectorielle,on obtient une solution à notre problème en choisissant une droite vectorielle chaque jour, et en répartissant les touristes suivant les droites affines de direction cette droite vectorielle. De manière explicite, cela nous donne la solution suivante :
— Jour 1: \(((0,0),(1,0),(2,0))\), \(((0,1),(1,1),(2,1))\) et \(((0,2),(1,2),(2,2))\),
— Jour 2: \(((0,0),(1,1),(2,2))\), \(((0,1),(1,2),(2,0))\) et \(((0,2),(1,0),(2,1))\),
— Jour 3: \(((0,0),(1,2),(2,1))\), \(((0,1),(1,0),(2,2))\) et \(((0,2),(1,1),(2,0))\),
— Jour 4: \(((0,0),(0,1),(0,2))\), \(((1,0),(1,1),(1,2))\) et \(((2,0),(2,1),(2,2))\),
Comme il est un peu lourd d’encoder les touristes par des couples, on peut les numéroter de \(1\) à \(9\) en envoyant le couple \((a,b)\) sur \(1+a+3b\), ce qui nous donne:
— Jour 1: \((1,2,3)\), \((4,5,6)\) et \((7,8,9)\),
— Jour 2: \((1,5,9)\), \((3,4,8)\) et \((2,6,7)\),
— Jour 3: \((1,6,8)\), \((2,4,9)\) et \((3,5,7)\),
— Jour 4: \((1,4,7)\), \((2,5,8)\) et \((3,6,9)\).
Il est plus difficile de deviner la structure qui se cache derrière la solution si on la donne sous cette forme.
16 touristes en 5 jours par groupes de 4
On peut voir, a posteriori, que la solution pour \(4\) touristes en \(3\) jours par groupes de \(2\) revient à prendre chaque jour une droite vectorielle du plan \({\bf F}_2\times {\bf F}_2\) sur le corps \({\bf F}_2={\bf Z}/2{\bf Z}\) à \(2\) éléments, et à répartir les touristes suivant les droites affines de direction cette droite vectorielle. Il semble donc naturel de penser qu’une solution serait de faire la même chose en partant du plan sur un corps à \(4\) éléments. Le problème est: existe-t-il un tel corps? Ce n’est pas immédiat étant donné que \({\bf Z}/4{\bf Z}\) n’est pas un corps puisque \(2\times 2=0\) et \(2\neq 0\) dans \({\bf Z}/4{\bf Z}\).
Pour construire un tel corps, on s’inspire de la construction du corps des nombres complexes \({\bf C}\) à partir du corps \({\bf R}\) des nombres réels. Le polynôme \(X^2+1\) n’a pas de racine dans \({\bf R}\) et on obtient \({\bf C}\) en rajoutant de force une racine \(i\) de ce polynôme 4De manière équivalente, on obtient \({\bf C}\) en quotientant l’anneau \({\bf R}[X]\) des polynômes à coefficients dans \({\bf R}\) par l’idéal \((X^2+1)\) constitué des multiples de \(X^2+1\): faire ceci revient à rajouter à \({\bf R}\) un élément \(X\) vérifiant \(X^2+1=0\).. On aurait pu aussi obtenir \({\bf C}\) en rajoutant à \({\bf R}\) une solution \(\omega=(-1+i\sqrt{3})/2\) de l’équation \(X^2+X+1=0\) puisque \(i=(2\omega+1)/\sqrt 3\) 5Autrement dit, on aurait aussi pu définir \({\bf C}\) comme le quotient \({\bf R}[X]/(X^2+X+1)\) de \({\bf R}[X]\) par l’idéal \((X^2+X+1)\)..
Pour obtenir un corps à \(4\) éléments, on fait exactement pareil en partant de \({\bf F}_2\). Le polynôme \(X^2+1\) admet \(1\) comme racine dans \({\bf F}_2\), mais le polynôme \(X^2+X+1\) ne s’annule pas (c’est nettement plus facile à voir que sur \({\bf R}\)…). On rajoute donc de force une racine \(\omega\) de ce polynôme 6En faisant le quotient de \({\bf F}_2[X]\) par l’idéal \((X^2+X+1)\)., et on obtient un corps \({\bf F}_4\) dont les éléments s’écrivent, de manière unique, sous la forme \(a+\omega b\), avec \(a,b\in{\bf F}_2\). Comme \(\omega^2=-\omega-1=\omega+1\), on a \[(a+b\omega)(a’+b’\omega)= aa’+(ab’+ba’)\omega+bb’\omega^2= aa’+bb’+(ab’+ba’+bb’)\omega.\]
Maintenant, il y a \(5\) droites vectorielles dans le plan \({\bf F}_4\times{\bf F}_4\), les droites d’équation \(y=\lambda x\) avec \(\lambda\in{\bf F}_4\) et la droite \(x=0\). En codant les touristes par des éléments \((a+b\omega,c+d\omega)\) de \({\bf F}_4\times{\bf F}_4\), avec \(a,b,c,d\in{\bf F}_2\), on obtient la solution:
— Jour 1: \(((0,0),(1,0),(\omega,0),(1+\omega,0))\), \(((0,1),(1,1),(\omega,1),(1+\omega,1))\),
\(((0,\omega),(1,\omega),(\omega,\omega),(1+\omega,\omega))\) et \(((0,1+\omega),(1,1+\omega),(\omega,1+\omega),(1+\omega,1+\omega))\),
— Jour 2: \(((0,0),(1,1),(\omega,\omega),(1+\omega,1+\omega))\), \(((0,1),(1,0),(\omega,1+\omega),(1+\omega,\omega))\), \(((0,\omega),(1,1+\omega),(\omega,0),(1+\omega,1))\) et \(((0,1+\omega),(1,\omega),(\omega,1),(1+\omega,0))\),
— Jour 3: \(((0,0),(1,\omega),(\omega,1+\omega),(1+\omega,1))\),\(((0,1),(1,1+\omega),(\omega,\omega),(1+\omega,0))\),\(((0,\omega),(1,0),(\omega,1),(1+\omega,1+\omega))\) et \(((0,1+\omega),(1,1),(\omega,0),(1+\omega,\omega))\),
— Jour 4: \(((0,0),(1,1+\omega),(\omega,1),(1+\omega,\omega))\), \(((0,1),(1,\omega),(\omega,0),(1+\omega,1+\omega))\), \(((0,\omega),(1,1),(\omega,1+\omega),(1+\omega,0))\) et \(((0,1+\omega),(1,0),(\omega,\omega),(1+\omega,1))\),
— Jour 5: \(((0,0),(0,1),(0,\omega),(0,1+\omega))\),\(((1,0),(1,1),(1,\omega),(1,1+\omega))\),
\(((\omega,0),(\omega,1),(\omega,\omega),(\omega,1+\omega))\) et \(((1+\omega,0),(1+\omega,1),(1+\omega,\omega),(1+\omega,1+\omega))\).
En associant à \((a+b\omega,c+d\omega)\) l’élément \(1+a+2b+4c+8d\) de \(1,2,\dots,16\), cela donne une solution plus compacte mais moins structurée.
— Jour 1: \((1,2,3,4)\), \((5,6,7,8)\), \((9,10,11,12)\) et \((13,14,15,16)\),
— Jour 2: \((1,6,11,16)\), \((2,5,12,15)\), \((3,8,9,14)\) et \((4,7,10,13)\),
— Jour 3: \((1,8,10,15)\), \((4,5,11,14)\), \((2,7,9,16)\) et \((3,6,12,13)\),
— Jour 4: \((1,7,12,14)\), \((3,5,10,16)\), \((4,6,9,15)\) et \((2,8,11,13)\).
Généralisons...
\(q^2\) touristes en \(q+1\) jours par groupes de \(q\), pour \(q\leq 10\)
Si \(q=5,7,8,9\) il y a un corps à \(q\) éléments et nous laissons au lecteur le soin d’arranger nos touristes (pour construire un corps à \(p^f\) éléments, où \(p\) est un nombre premier, il faut rajouter au corps \({\bf F}_p\) la racine d’un polynôme irréductible dans \({\bf F}_p[X]\) de degré \(f\): par exemple, pour \(8=2^3\), on peut prendre \(X^3+X+1\) car ce polynôme ne s’annule pas dans \({\bf F}_2\) et \(2+2>\deg (X^3+X+1)\)).
Si \(q=6\) ou \(10\), il n’y a pas de corps ayant \(q\) éléments et j’ignore si le problème a une solution. Il est probable que la réponse soit connue.
15 touristes en 7 jours par groupes de 3
La réponse dans un prochain billet, celui-ci étant déjà bien long.
ÉCRIT PAR
Pierre Colmez
Directeur de recherche - CNRS - Sorbonne Université, Paris
