Turismo corporal

Le 15 décembre 2012  - Ecrit par  Pierre Colmez
Le 1er juillet 2020  - Traduit par  Jimena Royo-Letelier, Julio E. De Villegas
Article original : Tourisme corporel Voir les commentaires
Lire l'article en  

¿Se puede hacer visitar París a 15 turistas en 7 días, en grupos de a 3, de manera que al final de la estadía cada turista haya pasado un día con alguno de los demás ? De manera más general, uno puede preguntarse para qué valores de $a$, $b$, $n$, se puede hacer visitar París en $b$ días a $n$ turistas, en grupos de $a$, de manera que al final de la estadía cada turista haya pasado exactamente un día con cada uno de los demás.

Una condición necesaria es que $a$ divida $n$ y que $n-1=b(a-1)$, ya que cada turista viaja con $a-1$ turistas cada día, y se desea que él/ella haya visto a todos los demás exactamente una vez al cabo de $b$ días. Por ejemplo, si $q$ es un entero, se puede tomar $n=q^2$, $a=q$ y $b=q+1$, o bien
$n=q^3+q^2+q+1$, $a=q+1$ y $b=q^2+q+1$ (el problema inicial es de este tipo con $q=2$).

Alentamos al lector para que trate de hacer visitar París a $4$ turistas en $3$ días, en grupos de $2$, y luego a $9$ turistas en $4$ días, en grupos de $3$, antes de leer lo que sigue.

$4$ turistas en $3$ días en grupos de $2$

Enumeremos $1,2,3,4$ a los turistas. No hay ninguna opción : $1$ debe pasar un día con $2$, uno con $3$ y uno con $4$, y los otros dos deben viajar juntos, lo que nos da la siguiente solución.

— Día1 : $(1,2)$ y $(3,4)$,

— Día 2 : $(1,3)$ y $(2,4)$,

— Día 3 : $(1,4)$ y $(2,3)$.

$9$ turistas en $4$ días en grupos de $3$

El problema es claramente más difícil, y una solución por tanteo es demasiado problemática. La solución es preguntarse cómo codificar a esos $9$ turistas, y si uno se da cuenta que $9=3\times 3$, es natural verlos como elementos del plano sobre el cuerpo ${\bf F}_3={\bf Z}/3{\bf Z}$ con $3$ elementos, es decir, como parejas $(x,y)$ de elementos de ${\bf F}_3\times {\bf F}_3$. Este plano contiene $4$ rectas vectoriales, las que tienen una ecuación de la forma $y=\lambda x$, con $\lambda\in{\bf F}_3$, o bien coinciden con la recta
$x=0$. Si se denota $0,1,2$ a los elementos de ${\bf F}_3$ (con $1+2=0$ y $2\times 2=1$), esas rectas son las generadas por $(1,0)$, $(1,1)$, $(1,2)$ y $(0,1)$.

A cada recta vectorial le corresponde una partición del plano en rectas paralelas afines, cada una con $3$ elementos. Como por dos puntos pasa una y solo una recta afín, y que una recta afín es paralela a una única recta vectorial, se obtiene una solución a nuestro problema eligiendo una recta vectorial cada día y repartiendo a los turistas siguiendo las rectas afines de dirección de esta recta vectorial. De manera explícita, esto nos da la siguiente solución :

— Día 1 : $((0,0),(1,0),(2,0))$, $((0,1),(1,1),(2,1))$ y $((0,2),(1,2),(2,2))$,

— Día 2 : $((0,0),(1,1),(2,2))$, $((0,1),(1,2),(2,0))$ y $((0,2),(1,0),(2,1))$,

— Día 3 : $((0,0),(1,2),(2,1))$, $((0,1),(1,0),(2,2))$ y $((0,2),(1,1),(2,0))$,

— Día 4 : $((0,0),(0,1),(0,2))$, $((1,0),(1,1),(1,2))$ y $((2,0),(2,1),(2,2))$,

Como es un poco pesado codificar a los turistas por parejas, se los puede enumerar de $1$ a $9$ enviando a la pareja $(a,b)$ sobre $1+a+3b$, lo que nos da :

— Día 1 : $(1,2,3)$, $(4,5,6)$ y $(7,8,9)$,

— Día 2 : $(1,5,9)$, $(3,4,8)$ y $(2,6,7)$,

— Día 3 : $(1,6,8)$, $(2,4,9)$ y $(3,5,7)$,

— Día 4 : $(1,4,7)$, $(2,5,8)$ y $(3,6,9)$.

Sin embargo, es más difícil adivinar la estructura que se esconde detrás de la solución si uno la da bajo esta forma.

$16$ turistas en $5$ días en grupos de $4$

Se puede ver, a posteriori, que la solución para $4$ turistas en $3$ días en grupos de $2$ equivale a tomar cada día una recta vectorial del plano ${\bf F}_2\times {\bf F}_2$ sobre el cuerpo ${\bf F}_2={\bf Z}/2{\bf Z}$ de $2$ elementos, y repartir a los turistas siguiendo las rectas afines de dirección de esta recta vectorial. Por lo tanto, parece natural pensar que una solución sería hacer lo mismo partiendo del plano sobre un cuerpo de $4$ elementos. El problema es : ¿existe un cuerpo así ? No es inmediato, dado que ${\bf Z}/4{\bf Z}$ no es un cuerpo, ya que $2\times 2=0$ y $2\neq 0$ en ${\bf Z}/4{\bf Z}$.

Para construir un cuerpo así uno se inspira en la construcción del cuerpo de números complejos ${\bf C}$ a partir del cuerpo ${\bf R}$ de números reales. El polinomio $X^2+1$ no tiene raíz en ${\bf R}$, y uno obtiene ${\bf C}$ agregando a la fuerza una raíz $i$ de ese polinomio [1]. Uno también habría podido obtener ${\bf C}$ agregando a ${\bf R}$ una solución $\omega=(-1+i\sqrt{3})/2$ de la ecuación $X^2+X+1=0$ ya que $i=(2\omega+1)/\sqrt 3$ [2].

Para obtener un cuerpo de $4$ elementos, se hace exactamente lo mismo partiendo de ${\bf F}_2$. El polinomio $X^2+1$ admite a $1$ como raíz en ${\bf F}_2$, pero el polinomio $X^2+X+1$ no se anula (esto es claramente más fácil de ver que sobre ${\bf R}$...). Por lo tanto, se agrega a la fuerza una raíz $\omega$ a este polinomio [3] y se obtiene un cuerpo ${\bf F}_4$ cuyos elementos se escriben, de manera única, de la forma $a+\omega b$, con $a,b\in{\bf F}_2$.
Como $\omega^2=-\omega-1=\omega+1$, se tiene \[(a+b\omega)(a'+b'\omega) = aa'+(ab'+ba')\omega+bb'\omega^2 = aa'+bb'+(ab'+ba'+bb')\omega.\]

Ahora hay $5$ rectas vectoriales en el plano ${\bf F}_4\times{\bf F}_4$ : las rectas de ecuación $y=\lambda x$ con $\lambda\in{\bf F}_4$ y la recta $x=0$. Codificando a los turistas con elementos $(a+b\omega,c+d\omega)$ de ${\bf F}_4\times{\bf F}_4$, con $a,b,c,d\in{\bf F}_2$, se obtiene la solución :

— Día 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))$ y
$((0,1+\omega),(1,1+\omega),(\omega,1+\omega),(1+\omega,1+\omega))$,

— Día 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))$ y
$((0,1+\omega),(1,\omega),(\omega,1),(1+\omega,0))$,

— Día 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))$ y
$((0,1+\omega),(1,1),(\omega,0),(1+\omega,\omega))$,

— Día 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))$ y
$((0,1+\omega),(1,0),(\omega,\omega),(1+\omega,1))$,

— Día 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))$ y
$((1+\omega,0),(1+\omega,1),(1+\omega,\omega),(1+\omega,1+\omega))$.

Asociando a $(a+b\omega,c+d\omega)$ el elemento $1+a+2b+4c+8d$ de $1,2,\dots,16$, da una solución más compacta pero menos estructurada.

— Día 1 : $(1,2,3,4)$, $(5,6,7,8)$, $(9,10,11,12)$ y $(13,14,15,16)$,

— Día 2 : $(1,6,11,16)$, $(2,5,12,15)$, $(3,8,9,14)$ y $(4,7,10,13)$,

— Día 3 : $(1,8,10,15)$, $(4,5,11,14)$, $(2,7,9,16)$ y $(3,6,12,13)$,

— Día 4 : $(1,7,12,14)$, $(3,5,10,16)$, $(4,6,9,15)$ y $(2,8,11,13)$.

— Día 5 : $(1,5,9,13)$, $(2,6,10,14)$, $(3,7,11,15)$ y $(4,8,12,16)$.

$q^2$ turistas en $q+1$ días en grupos de $q$, para $q\leq 10$

Si $q=5,7,8,9$, hay un cuerpo de $q$ elementos, y dejamos al lector el cuidado de ordenar a nuestros turistas (para construir un cuerpo de $p^f$ elementos, donde $p$ es un número primo, hay que añadir al cuerpo ${\bf F}_p$ la raíz de un polinomio irreductible en ${\bf F}_p[X]$ de grado $f$ : por ejemplo, para $8=2^3$, se puede tomar $X^3+X+1$ ya que ese polinomio no se anula en ${\bf F}_2$ y $2+2>\deg (X^3+X+1)$).

Si $q=6$ o $10$, no hay cuerpo que tenga $q$ elementos, e ignoro si el problema tiene una solución. Es probable que la respuesta sea conocida.

$15$ turistas en $7$ días en grupos de $3$

La respuesta en un próximo artículo, porque este ya está largo.

Notes

[1De manera equivalente, uno obtiene ${\bf C}$ poniendo como cuociente el anillo ${\bf R}[X]$ de los polinomios con coeficientes en ${\bf R}$ por el ideal $(X^2+1)$ constituido por múltiplos de $X^2+1$ : hacer esto equivale a agregar a ${\bf R}$ un elemento $X$ que verifica $X^2+1=0$.

[2En otras palabras, uno habría podido definir también ${\bf C}$ como el cuociente ${\bf R}[X]/(X^2+X+1)$ de ${\bf R}[X]$ por el ideal $(X^2+X+1)$.

[3Haciendo el cuociente de ${\bf F}_2[X]$ por el ideal $(X^2+X+1)$.

Partager cet article

Pour citer cet article :

Julio E. De Villegas, Jimena Royo-Letelier — «Turismo corporal» — Images des Mathématiques, CNRS, 2020

Crédits image :

Image à la une - Jacques Demarthon (AFP) para L’Express

Commentaire sur l'article

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é ?