Cajas con diferencias II

Piste rouge Le 11 octobre 2013  - Ecrit par  Romain Bondil
Le 10 février 2019  - Traduit par  Jimena Royo-Letelier, Julio E. De Villegas
Article original : Boîtes à différences II Voir les commentaires
Lire l'article en  

Continuamos aquí el juego de las cajas con diferencias. Ahora consideramos n números al inicio en lugar de 4. La lectura de esta segunda parte es un poco más exigente que la de ’’Cajas con diferencias I’’, pero debería estar al alcance de un alumno de liceo. La paridad de números es el punto esencial del razonamiento y el triángulo de Sierpinski muestra la punta de su nariz.

1. Introducción

En ’’Cajas con diferencias I’’ estudiamos las cajas con diferencias construidas a partir de cuatro números enteros. Por comodidad, llamaremos cuatro números $(a,b,c,d)$ escritos entre paréntesis una 4-tupla.

Mostramos que en el juego —consistente en reemplazar $(a,b,c,d)$ por $(dist(a,b),dist(b,c),dist(c,d),dist(d,a))$ y comenzar de nuevo— se llegaba siempre a la 4-tupla $(0,0,0,0)$, a partir de la cual no ocurre nada nuevo.

Recordemos que aquí designamos como $dist(a,b)$ a la distancia de $a$ a $b$, es decir $dist(a,b)=b-a$ si $b\geq a$ y $dist(a,b)=a-b$ si $a \geq b$.

Convención de lenguaje : en matemáticas, dado un entero positivo $n$ cualquiera, se hablará de una $n$-tupla para referirse al conjunto ordenado $(a_1,... ,a_n)$.

Si en vez de partir de cuatro números partimos, por ejemplo, de tres, es decir, de una 3-tupla, y en cada etapa se reemplaza $(a,b,c)$ por $(dist(a,b),dist(b,c),dist(c,a))$, no es difícil encontrar un ejemplo de comportamiento muy diferente :

1 0 1
1 1 0
0 1 1
1 0 1

Vemos que al cabo de tres etapas se llega de nuevo al punto de partida. Por lo tanto, la serie de 3-tuplas será periódica de período 3.

En términos de representación gráfica, tendremos el siguiente encajonamiento :

donde el gran triángulo rojo se reencuentra más pequeño (dado vuelta, es cierto, pero el lector del artículo anterior sabrá que una rotación no cambia nada en nuestro problema).

El mismo juego de las cajas con diferencias : en general, para cada entero $n\geq 3$ se considerará el juego de las cajas con diferencias que en cada etapa reemplaza la $n$-tupla $(a_1,...,a_n)$ por la $n$-tupla $(dist(a_1,a_2),...,dist(a_n,a_1))$. En matemáticas, un tal juego se llama un algoritmo.

  El problema que se quiere resolver : buscamos saber para qué valores de $n$ este algoritmo se detiene siempre en $(0,..,0)$, cualquiera que sea la $n$-tupla con la cual se comience.

Ya se sabe que este es el caso para $n=4$ y no para $n=3$.

Ejemplo de comienzo de juego con dos 6-tuplas

2. El juego simplificado, ¡de nuevo él !

En el artículo anterior se habló del juego simplificado, que consistía en reemplazar al inicio cada número por ’’$p$’’ si este es par y por ’’$i$’’ si es impar.

Para que el algoritmo se detenga dada cualquier n-tupla $(a_1,...,a_n)$, es necesario que en particular el juego simplificado se detenga, es decir, que llegue a $(p,p,...,p)$.

Mejor aún, aplicando los mismos argumentos que en ’’Cajas con diferencias I’’ se demuestra que el recíproco también es verdadero.

En efecto, si uno sabe que el juego simplificado se detiene siempre en $(p,..,p)$, significa que a partir de un $n$-tupla de enteros $(a_1,...,a_n)$, se llega siempre a una $n$-tupla de números pares. Luego, recomenzando del mismo modo, se llega a una $n$-tupla de números divisibles por $4$, y se sigue así, hasta que los números obtenidos sean divisibles por un número de la forma $2 \times 2 \times \cdots \times 2$ más grande que el máximo de los números $( a_1,...,a_n)$ del inicio.

  Conclusión del problema que uno quiere resolver : los enteros $n$ que buscamos son exactamente aquellos para los cuales el juego simplificado se detiene dada cualquier $n$-tupla de inicio.

3. El juego simplificado es aditivo

Para ver si el juego simplificado aplicado a todas las $n$-tuplas $(a_1,...,a_n)$ se detiene, sabiendo que $a_1$ no puede valer sino $p$ o $i$ y del mismo modo para los otros, hay que probar $2^n$ posibilidades. Si $n$ es grande, éste número puede ser muy grande.

Pero el juego simplificado tiene propiedades muy notables que van a facilitarnos las cosas.

3.1. Una nueva descripción del juego simplificado

Para comenzar, es necesario hacer un poco más de álgebra : escribiremos $\underline{0}$ para denotar el símbolo $p$ y $\underline{1}$ para $i$.

Con esta elección de notaciones, el cálculo anterior con $p$ e $i$ da un cálculo natural con éstos $\underline{0}$ y $\underline{1}$ (agregar $\underline{0}$ no cambia nada), a excepción de $\underline{1} + \underline{1} =\underline{0}$.

Comentario : en el juego simplificado, la ’’distancia’’ entre dos pares (respectivamente dos impares) es $\underline{0}$ y entre un par y un impar es $\underline{1}$.

Ahora bien, hay una manera muy simple de mirar esta distancia, haciendo la adición de dos números (siempre con la regla $\underline{1} + \underline{1} =\underline{0}$) : la suma de dos números de igual paridad será siempre par, por ejemplo.

  En consecuencia, se puede ver una etapa del juego simplificado como la siguiente operación :
Reemplazamos : $(a_1,...,a_n)$ por $(a_1 +a_2, a_2 + a_3,...,a_n + a_1)$.

Esta operación se anotará $J$, es decir :

$J(a_1,...,a_n) = (a_1 +a_2, a_2 + a_3,...,a_n + a_1)$,

donde los $a_1,...,a_n$ no pueden valer sino $\underline{0}$ o $\underline{1}$.

Por ejemplo $J(\underline{0}, \underline{1}, \underline{0})= ( \underline{1}, \underline{1}, \underline{0})$.

3.2. Comportamiento bajo la adición de los $n$-tuplas

Se puede considerar una adición para las $n$-tuplas, que anotaremos en rojo, definida como sigue :

$(a_1,...,a_n)$ + $(b_1,...,b_n)= (a_1 + b_1,...,a_n + b_n)$

La propiedad esencial para nosotros es :

 

Para todas las $n$-tuplas $a=(a_1,...,a_n)$ y $b=(b_1,...,b_n)$ formadas por $\underline{0}$ y por $\underline{1}$, se tiene :

$J$($a$ + $b$)$=J(a)$ + $J(b)$

Lo que hace funcionar esta propiedad es que uno puede hacer las adiciones en el orden que quiera.

Una prueba más detallada para n=3.

Escribiendo $\: c=a$ + $b$, por definición tenemos :
$\: c=(c_1,c_2,c_3)=(a_1+b_1,a_2+b_2,a_3+b_3)$.

Por otra parte $\: J(c)=(c_1+c_2,c_2+c_3,c_3+c_1)$.

Entonces $\: J(c)=(a_1+b_1+a_2+b_2,a_2+b_2+a_3+b_3,a_3+b_3+a_1+b_1)$.

Reagrupando los términos en una forma diferente :

$\: J(c)=(a_1+a_2+b_1+b_2,a_2+a_3+b_2+b_3,a_3+a_1+b_3+b_1)$.

Y finalmente $\: J(c)=J(a)$ + $J(b)$.

Incluso vamos a generalizar un poco, aplicando muchas veces la propiedad anterior :

  Si uno hace 2 etapas del juego simplificado, se anota $J^2(a)$ la $n$-tupla obtenida partiendo de $a= (a_1,...,a_n)$.

Del mismo modo se anota $J^p(a)$ la $n$-tupla obtenida después de $p$ etapas partiendo de $(a_1,...,a_n)$.

Se tiene todavía la propiedad :

$J^p$($a$ + $b$) $=J^p(a)$ + $J^p(b)$

3.3. Reducción de los problemas con las $n$-tuplas más simples

Se llamarán $n$-tupas elementales a las $n$-tuplas donde hay solo un $\underline{1}$ que aparece, y todas las otras entradas de la $n$-tupla son $\underline{0}$.

Así, para $n=3$, los tres $3$-tuplas elementales son $(\underline{1},\underline{0},\underline{0})$, $(\underline{0},\underline{1},\underline{0})$ y $(\underline{0},\underline{0},\underline{1})$.

En general hay exactamente $n$ de tales $n$-tuplas elementales : la primera es $(\underline{1} , \underline{0},..., \underline{0})$ y la última $(\underline{0},..., \underline{0}, \underline{1})$.

Con la adición de las $n$-tuplas que se definió en la sección 3.2, toda $n$-tupla puede escribirse como una suma de $n$-tuplas elementales.

A modo de ejemplo, $(\underline{0}, \underline{1}, \underline{1}, \underline{0}, \underline{1})$ se escribe como la suma de tres $5$-tuplas elementales :

$(\underline{0} , \underline{1}, \underline{1}, \underline{0}, \underline{1})= (\underline{0} ,\underline{1}, \underline{0}, \underline{0}, \underline{0})+(\underline{0}, \underline{0}, \underline{1}, \underline{0}, \underline{0})+(\underline{0} , \underline{0}, \underline{0} , \underline{0}, \underline{1})$.

Con la propiedad de la sección 3.2, se deduce :

  Propiedad : para que el juego (simplificado) se termine para todas las $n$-tuplas, basta que se termine para las $n$-tuplas elementales.

Además, como todas esas $n$-tuplas elementales se deducen por rotación a partir de una de ellas, por ejemplo
$(\underline{0},...,\underline{0},\underline{1})$, basta con estudiar (ver ’’Cajas con diferencias I’’) si el juego se termina ¡para ésa única $n$-tupla !

¡Hemos simplificado bastante el problema ! A título de comparación, en ’’Cajas con diferencias I’’ tuvimos que estudiar todas las posibilidades ’’a mano’’.

4. El estudio a partir de (0,...,0,1) :

Para aliviar la escritura de lo que sigue, se usará la notación $0$ para $\underline{0}$ y $1$ para $\underline{1}$ (pero hay que pensar que $1+1=0$ en este contexto).

Estudiamos entonces el tablero de evolución de $(0,...,0,1)$ en el juego.

4.1 Caso donde $n$ es una potencia de 2 : 4, 8, 16, 32...

Para $n=8$, se termina en exactamente ocho etapas :

0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0

Pero sobre todo, vemos que la línea 4 del tablero (haciendo que el tablero comience en la línea 0), se descompone en dos partes idénticas, marcadas en rojo y en verde, que van a evolucionar de la misma forma, siguiendo la evolución ya conocida para la $4$-tupla $(0,0,0,1)$.

¿Por qué éstas dos evoluciones independientes ?

Simplemente gracias al $0$ que queda en el extremo izquierdo de cada una de las dos partes.

Generalizando este comentario, obtenemos lo siguiente.

  Conclusión 1 : para todos los $n$ de la forma $2^m$, es decir $2,4,8,16,32$,..., el juego simplificado se termina siempre en a lo más $n$ etapas y exactamente en $n$ etapas partiendo de la $n$-tupla elemental $(\underline{0},...,\underline{0}, \underline{1})$.

Conclusión 2 (solución del problema de este artículo para los $n$ de la forma 2m ) : gracias a lo explicado en la sección 2, sabemos que para esos mismos valores de $n$ de la forma $2^m$, el verdadero juego de las diferencias se termina siempre.

4.2 ¿Y que pasa con los otros valores de $n$ ?

En el nivel donde estamos, no tengo una prueba verdaderamente elemental del siguiente resultado :

  Propiedad : para un entero $n$ cualquiera, si el juego simplificado a partir de una $n$-tupla se termina, entonces se termina en a lo más $n$ etapas.

Prueba para aquellos que hicieron un primer año de matemáticas en la enseñanza superior.

Usamos álgebra lineal, pues el párrafo 3.2. sugiere abiertamente esto. La aplicación $J$ es un endomorfismo del espacio vectorial $(Z/2Z)^n$. Se busca la condición necesaria y suficiente para que $J$ sea nilpotente. Ahora bien, un endomorfismo $J$ de un espacio vectorial de dimensión finita $n$ es nilpotente si y solamente si $J^n=0$.

Ahora bien, partiendo de $(0,0,...,0,1)$, si uno se limita a las $n-1$ primeras etapas, el juego simplificado reproduce un fenómeno bien estudiado en otra parte, llamado el triángulo de Sierpinski. El hecho de que tengamos $(0,0,..,0)$ en la $n$-ésima etapa se ve por supuesto en la $(n-1)$-ésima, donde se tendrá una línea de $1$ (o una línea de $0$ si se terminara antes, pero esto no sucede).

Tomemos de nuevo el tablero de juego de más arriba partiendo de $(0,0,...,0,1)$. Vamos a quitar la última línea y colorear de gris los 0 sobre la diagonal que va de abajo a la izquierda hacia arriba a la derecha. Por ejemplo :

0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1
0 0</font 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1

Si se eliminan los 0 grises y en lugar de alinear a la derecha, se centra, uno obtiene entonces la figura siguiente.

1
1 1
1 0 1
1 1 1 1
1 0 0 0 1
1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1 1

Comentario : la ventaja de esta manera de presentar los cálculos es que, aparte del número de etapas, la representación es independiente del tamaño de las $n$-tuplas.

Reemplazando los 1 por un • y los 0 por un , se obtiene :

• •
• • • •
• • •
• • • • • •
• • • • • • • •

La regla de construcción de este nuevo cuadro, equivalente al anterior para nosotros, es muy simple :

Regla 1 : al principio y al final de cada línea, hay siempre un punto negro : •

Regla 2 : para construir una nueva línea a partir de la anterior, entre dos puntos del mismo color se coloca un punto rojo y entre dos puntos de colores diferentes se coloca un punto negro •

Vemos aquí el resultado de ésta construcción con 256 líneas es decir 255 etapas (los círculos • y están pegados unos a otros).

Este tipo de triángulo es el que se llama triángulo de Sierpinski. Se puede también elaborar una versión 3D (la pirámide de Sierpinski), como lo muestra esta foto publicada en ’’Paisajes Matemáticos’’. También se encontrará en IdM una breve biografía de W. Sierpinski.

¿Qué aprendemos del esquema de construcción de este triángulo ? Se puede construir un tal triángulo al revés en relación a lo que acabamos de hacer, es decir, partiendo del más grande de los triángulos negros dibujados, luego dibujando tres triángulos negros de igual tamaño como éste, que delimitan un triángulo rojo intenso que no contendrá nunca puntos negros.

Luego, recomenzando en cada uno de los triángulos rosados :

¡Y así sucesivamente !

Consecuencia para nosotros : reviniendo a la descripción con puntos • y , las únicas líneas completamente negras serán las líneas cuyo número es de la forma $2^k-1$. Dicho de otra manera $3,7,15,31...$. Serán entonces las únicas líneas del juego simplificado que sólo contengan $1$. Por lo tanto, las únicas que serán seguidas por una línea que sólo contengan $0$ : la condición de término del juego simplificado.

Gracias al vínculo ya hecho entre el verdadero juego y el juego simplificado, terminamos nuestra deducción.

  Conclusión final : los enteros $n$ para los cuales el juego se termina para todas las $n$-tuplas, son exactamente los $n$ de la forma $2^k$, es decir, $2,4,8,16,32,...$ No hay otros.

Referencias : el problema estudiado aquí es conocido bajo el doble nombre de diffy boxes y de problema de Ducci.

Las referencias acerca del triángulo de Sierpinski son muy numerosas, especialmente sobre su construcción a partir del triángulo de Pascal. Me gustaría sólo citar el bonito libro El diablo de las matemáticas de Hans Magnus Enzensberger. La excelente ilustradora R. S. Berner ha hecho también muchos libros para niños, entre los cuales se encuentra la serie El libro de la primavera, El libro del verano,.. ¡me ha hecho pasar hermosos momentos de observaciones con mis niños !

Escribiendo este artículo, recibí la Gazette des Mathématiciens, dedicada a B. Mandelbrot, el padre de la geometría fractal. Ahí hay una foto de un molusco llamado ’’Cymbiola innexa Reeve’’ cuya concha retoma la figura de Sierpinski. Vea aquí una foto, en este foro de amantes de las conchas marinas.

Post-scriptum :

El autor y el comité de redacción agradecen a los relectores Reynald Thelliez y Simon Iosti por sus comentarios.

Article original édité par Patrick Popescu-Pampu

Partager cet article

Pour citer cet article :

Julio E. De Villegas, Jimena Royo-Letelier — «Cajas con diferencias II » — Images des Mathématiques, CNRS, 2019

Crédits image :

Image à la une - El logo y los dibujos fueron realizados con Geogebra. El triángulo de Sierpinski en lenguaje Python.

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