Tourisme corporel

Le 15 décembre 2012  - Ecrit par  Pierre Colmez Voir les commentaires (2)

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 les
deux 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 [1].
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$ [2].

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 [3], 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)$.

— Jour 5 : $(1,5,9,13)$, $(2,6,10,14)$, $(3,7,11,15)$ et $(4,8,12,16)$.

$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.

Notes

[1De 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$.

[2Autrement 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)$.

[3En faisant le quotient
de ${\bf F}_2[X]$ par l’idéal $(X^2+X+1)$.

Partager cet article

Pour citer cet article :

Pierre Colmez — «Tourisme corporel» — Images des Mathématiques, CNRS, 2012

Crédits image :

Image à la une - Jacques Demarthon (AFP) pour l’Express

Commentaire sur l'article

  • Tourisme corporel

    le 14 décembre 2012 à 12:06, par antoine.levitt

    Si je ne m’abuse, ce problème est similaire à la construction du jeu Dobble, étudiée sur ce même site http://images.math.cnrs.fr/Dobble-et-la-geometrie-finie.html

    Répondre à ce message
  • Tourisme corporel

    le 15 décembre 2012 à 11:00, par Pierre Colmez

    Les deux utilisent la géométrie sur des corps finis, mais Dobble utilise un plan projectif car on a besoin que deux droites se coupent toujours en un point ; dans la solution de notre problème, il est important de disposer de droites parallèles recouvrant tout l’espace. Cela dit, j’avais l’intention de mentionner Dooble dans le billet consacré aux 15 touristes en 7 jours, car la solution utilise la géométrie projective.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM