Turismo corporal

El 15 diciembre 2012  - Escrito por  Pierre Colmez
El 1ro julio 2020  - Traducido por  Jimena Royo-Letelier, Julio E. De Villegas
Artículo original : Tourisme corporel Ver los comentarios
Leer el artículo 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.

Notas

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

Comparte este artículo

Para citar este artículo:

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

Comentario sobre el artículo

Dejar un comentario

Foro sólo para inscritos

Para participar en este foro, debe registrarte previamente. Gracias por indicar a continuación el identificador personal que se le ha suministrado. Si no está inscrito/a, debe inscribirse.

Conexióninscribirse¿contraseña olvidada?

La traducción del sitio del francés al castellano se realiza gracias al apoyo de diversas instituciones de matemáticas de América Latina.