Cajas con diferencias I

Piste bleue Le 4 septembre 2013  - Ecrit par  Romain Bondil
Le 30 janvier 2019  - Traduit par  Jimena Royo-Letelier, Julio E. De Villegas
Article original : Boites à différences I Voir les commentaires

Este es un artículo que me gustaría que un estudiante de liceo pudiese disfrutar. Encontramos (está de moda en los nuevos programas) un algoritmo. Para probar que este algoritmo se detiene, hay que hacer matemáticas de verdad : comprender las simetrías del problema, lo que se conserva, lo que disminuye y cómo el hecho de mirar sólo la paridad permite finalmente resolver el problema.

1. Presentación del juego

Uno puede jugar al juego de las cajas con diferencias [1] para hacer practicar las sustracciones, digamos a partir del segundo año de la escuela. ¡Lo esencial a esta edad es que no dure tanto rato !

¿De qué se trata ? Se toman cuatro números enteros no negativos, por ejemplo 7, 5, 3, 11, y se colocan sobre la primera línea de un tablero, en ese orden. Esta es la etapa 0.

Luego, para pasar de una línea a la siguiente, a partir de cuatro números $a,b,c,d$ de la línea en curso, se escriben las distancias $dist(a,b), dist(b,c), dist(c,d), dist(d,a)$ sobre la línea siguiente. Por definición, la distancia $dist(a,b)$ es $b-a$ si $b \geq a$ y $dist(a,b)= a-b$ si $a \geq b$. Dicho de otra forma, es el resultado de la sustracción entre $a$ y $b$ olvidándose del signo negativo si este aparece.

Con los números elegidos arriba uno obtiene :

7 5 3 11
2 2 8 4

En ese momento, la última diferencia $dist(d,a)$ (aquí 11-7) parece menos cómoda de hacer que las otras. Esta dificultad, que viene de nuestra forma de escribir en un tablero, va a desaparecer un poco más adelante.

¿Qué pasa si continuamos haciendo estas diferencias línea tras línea ?

En el ejemplo anterior, las líneas siguientes son :

0 6 4 2
6 2 2 2
4 0 0 4
4 0 4 0
4 4 4 4
0 0 0 0

Con una línea así de cuatro ceros, uno dirá que el juego de las diferencias se termina.

Una forma más bonita de presentar el juego anterior consiste en colocar los cuatro números sobre los vértices de un cuadrado y cada diferencia al centro entre los vértices. Así, para la primera etapa :

Después de cuatro etapas :

Ahora uno comprende mejor el porqué de la expresión ’’caja con diferencias’’. ¡Pero esto solo se puede hacer si el juego termina rápido ! Además, no hay que confundir las distancias en el dibujo, con la distancia entre los dos números que colocamos.

La pregunta que surge : ¿el juego siempre termina ?

A estas alturas, usted debe tratar con cuatro números a su elección. Si no tiene ganas de hacerlo a mano, es fácil programarlo.

Normalmente, todos sus intentos terminarán (salvo errores repetidos de cálculo). El objetivo de lo que viene a continuación es comprender por qué.

Notación importante para la continuación : denotemos $N(a,b,c,d)$ el número de etapas necesarias para llegar a $(0,0,0,0)$ partiendo de cuatro números $(a,b,c,d)$. En la fase en que estamos, no sabemos todavía si este número es siempre finito, pero en el ejemplo que vimos juntos se cumple que $N(7,5,3,11)=7$.

Una versión más interesante del juego es, entonces, jugar a fabricar familias de 4 números, digamos todos de dos cifras, de modo que la cantidad de etapas antes de que el juego termine sea la más grande posible.

2. Un primer control : usando el máximo

Una primera forma de llegar a mostrar que el juego se termina sería interesándose en el máximo entre $a,b,c,d$.

Otra notación importante para la continuación : se notará $Max(a,b,c,d)$ el máximo entre $a,b,c,d$, es decir, el más grande de los números $a,b,c,d$. Por ejemplo, $Max(2,4,15,7)=15$.

Si uno llama $a',b',c',d'$ a los números $a'=dist(a,b), b'=dist(b,c), c'=dist(c,d), d'=dist(d,a)$ y si ninguno de los números $a,b,c,d$ es nulo, uno está seguro de que $a'< Max(a,b), b'< Max(b,c), c'< Max(c,d), d'< Max(d,a)$ y, por lo tanto, de que el máximo de los cuatro números disminuye estrictamente en cada etapa. De este modo uno estará seguro de que el juego finaliza a lo más en $Max(a,b,c,d)$ etapas.

Pero no todo es tan simple, pues aún se necesita examinar cuidadosamente lo que ocurre si uno de los números es nulo, y eso puede ocurrir en una etapa cualquiera. Así, en el ejemplo de la primera sección, durante las etapas siguientes el máximo permaneció constantemente igual a 4 :

4 0 0 4
4 0 4 0
4 4 4 4

De hecho, se podría resolver el problema de este modo, examinando todos los casos donde hay ceros, pero yo elegí otro camino que va a permitir evitar hacer tantos cálculos.

Retengamos, sin embargo, la propiedad siguiente.

Propiedad : Si $(a',b',c',d')$ se obtiene a partir de $(a,b,c,d)$ por el juego de las diferencias,
entonces $Max(a',b',c',d') \leq Max(a,b,c,d)$.

3. Algunos invariantes o simetrías del problema

Antes de ir a la prueba de que el juego se termina, notemos algunos comentarios que harán aquellas y aquellos que tienen la costumbre de resolver problemas. <estos están relacionados con las simetrías del problema. [2]

Vamos a considerar aquí algunas operaciones con los cuatro números ordenados $(a,b,c,d)$ que no cambian el número de etapas $N(a,b,c,d)$.

Operaciones geométricas

Las dos operaciones siguientes se ven más claramente con la ayuda de los dibujos con cuadrados dados al final de la sección 1.

  • Rotación : Decimos que los números ordenados $(b,c,d,a), (c,d,a,b), (d,a,b,c)$ se deducen de $(a,b,c,d)$ por rotación.
  • De derecha a izquierda : se gira en el sentido de las agujas del reloj.

  • Reflexión : Decimos también que los números ordenados $(d,c,b,a)$ se deducen de $(a,b,c,d)$ por reflexión, teniendo como eje de simetría la recta que pasa por los centros de los segmentos $[a,d]$ y $[b,c]$. Esto está ilustrado en la figura de abajo. También se dirá que $(b,a,d,c)$ se deduce de $(a,b,c,d)$ por reflexión (teniendo como eje de simetría la recta que pasa por los centros de los segmentos $[a,b]$ et $[c,d]$).

$ $

Propiedad : una rotación o una reflexión como las de arriba no cambian el número $N$ de etapas necesarias para terminar el juego.

Para comprender esta propiedad, basta con darse cuenta de que el resultado del juego a partir por ejemplo de $(b,c,d,a)$ se deduce en cada etapa de aquel del juego a partir de $(a,b,c,d)$ mediante la misma rotación. De hecho, cuando dibujé los cuatro números en un cuadrado, no especifiqué dónde se colocaba $a$. Escogí ponerlo en la esquina de abajo a la izquierda, pero podíamos presentir que esta elección no tenía importancia.

Operaciones algebraicas

  • Adición : si a cada uno de los números $a,b,c,d$ se le suma un número fijo $k$ y se considera el juego a partir de $(a+k,b+k,c+k,d+k)$, entonces no se altera la continuación del juego, ya las diferencias siguen siendo las mismas. En particular, $N(a+k,b+k,c+k,d+k)=N(a,b,c,d)$.
  • Multiplicación : si se multiplica cada uno de los números $a,b,c,d$ por un número $k$ positivo no nulo, entonces ese número $k$ quedará siempre como factor de todas las diferencias : $(ka-kb)=k(a-b)$, etc.... De ahí la propiedad siguiente.

$ $

Propiedad : la continuación del juego a partir de $(ka,kb,kc,kd)$ es la misma que a partir de $(a,b,c,d)$ multiplicando todo por $k$ en cada etapa.

En especial $N(ka,kb,kc,kd)=N(a,b,c,d)$ (para $k$ no nulo, por supuesto).

4. El juego simplificado : ’’par’’ e ’’impar’’

Imaginemos que se reemplaza cada uno de los cuatro números enteros $a,b,c,d$ por el símbolo $p$ si es par y por el símbolo $i$ si es impar.

Así $(2,5,7,4)$ será reemplazado por $(p,i,i,p)$.

Cuando uno efectúe una etapa del juego, la distancia entre dos impares (o entre dos pares) dará siempre un número par y la distancia entre dos números donde uno es impar y el otro par dará siempre un número impar.

Se considera entonces el juego simplificado.

Juego simplificado : las reglas son las mismas que en el juego de las diferencias descrito más arriba, pero esta vez $a_1, ..., a_4$ ya no son números enteros, sino símbolos $p$ o $i$ cuyas ’’distancias’’ están definidas por $d(p,i)=d(i,p)=i, d(p,p)=d(i,i)=p$.

Por ejemplo, en una etapa de ese juego, $(p,i,p,p)$ da $(i,i,p,p)$.

 

Comentario importante : en el juego simplificado construido a partir de los números originales $a_1, ..., a_4$, en cada etapa se conserva la información de ser ’’par’’ o ’’impar’’ sobre los números que aparecen en el verdadero juego en la misma etapa.

Por ejemplo, $(2,4,5,6)$ pasa a ser $(p,p,i,i)$, que por el juego simplificado da $(p,i,i,p)$. Esto traduce bien la paridad de los números obtenidos en el verdadero juego a partir de $(2,4,5,6)$, a saber, $(2,1,1,4)$.

La ventaja del juego simplificado es que al comienzo solo hay un número finito de posibilidades : exactamente dieciséis.

El juego simplificado termina si uno llega a $(p,p,p,p)$ (ya que después se obtendría siempre $(p,p,p,p)$). Es fácil, pero un tanto largo, probar que en las otras quince posibilidades de inicio siempre se llega a $(p,p,p,p)$. En otras palabras, el juego simplificado siempre se termina.

De hecho, los resultados de simetrías dadas en el párrafo 3 (rotaciones y reflexiones) permiten reducir el número de casos (ejercicio : ¿cuántos casos se necesita realmente verificar ?).

Aquí hay uno a modo de ejemplo :

p i p p
i i p p
p i p i
i i i i
p p p p

Se verificará también que entre las otras 15 posibilidades diferentes de $(p/i,p/i,p/i,p/i)$, todas dan un juego simplificado que se termina al cabo de 4 etapas a lo más.

5. Cómo se deduce la solución del juego real a partir de la del juego simplificado

La sección 4 nos mostró que el juego simplificado se termina siempre, a lo más en cuatro etapas, y que al mismo tiempo (vea el comentario importante acá abajo) se conserva en cada etapa la información ’’par’’ o ’’impar’’ sobre los números que aparecen en el juego verdadero en la misma etapa.

Se concluye entonces que a partir de cualquier $(a,b,c,d)$, al cabo de cuatro etapas como máximo, se obtienen sólo números pares, es decir, de la forma $(2 a_1, 2 b_1, 2 c_1, 2d_1)$.

Como se dijo en el párrafo sobre los invariantes y simetrías, sabemos entonces que todos los números que aparecerán después en el juego serán pares. Se obtendrán tomando el juego a partir de $(a_1, b_1, c_1, d_1)$ y multiplicando por 2.

Pero igualmente, para el juego a partir de $(a_1, b_1, c_1, d_1)$, en a lo más cuatro etapas, se obtendrá aún números pares de la forma $(2a_2, 2b_2, 2c_2, 2d_2)$.

Así, desde esta nueva etapa, en el juego a partir de $(a,b,c,d)$, todos los números serán múltiplos por $4= 2 \times 2$.

Continuando, luego se tendrán solo números múltiplos de $8= 2 \times 2 \times 2$, luego de $16, 32, 64$, ¡y así indefinidamente ! Vamos a mostrar que esto fuerza a esos números a ser nulos a partir de cierto momento.
En efecto, como se vio al final de la sección 2, en cada etapa del juego el máximo de cuatro números no sobrepasa $M=Max(a,b,c,d)$, el máximo de números elegidos al inicio.

Ahora bien, números no nulos inferiores a un número $M$ fijo no pueden ser divisibles por un número de la forma $2 \times 2 \times \cdots \times 2$ ¡que es más grande que $M$.

Esto obliga a los números del juego a ser nulos a partir de cierto momento.

  Hemos demostrado finalmente que el juego se termina.

Para digerir mejor esta demostración abstracta : retomemos el ejemplo del comienzo.

Tomamos de nuevo $(a,b,c,d)=(7,5,3,11)$ (que significa $a=7,b=5$, etc). Por comodidad, reproduzco el cuadro de distancias sucesivas del principio del artículo :

7 5 3 11
2 2 8 4
0 6 4 2
6 2 2 2
4 0 0 4
4 0 4 0
4 4 4 4
0 0 0 0

Después de una etapa se tiene $(a',b',c',d')=(2,2,8,4)$, por lo tanto todos los números son pares. Se sabe entonces que todos los números siguientes serán también pares, y que el juego sería el mismo si se partiera de $(1,1,4,2)$ con la condición de multiplicar por $2$ en cada etapa.

A su vez, el juego a partir de $(1,1,4,2)$ debe dar en menos de cuatro etapas solo números pares. Esto es justamente lo que uno comprueba, ya que en la etapa cuatro de nuestro ejemplo del comienzo, se tiene $(4,0,0,4)$, es decir, $2$ veces $(2,0,0,2)$.
 
A partir de ese momento, uno está seguro de que todos los números serán múltiplos de 4. Sin embargo, el máximo no puede aumentar, y por lo tanto debe ser inferior a $Max(4,0,0,4)=4$. Ahora bien, el razonamiento anterior nos dice que, en a lo más cuatro etapas, los números van a ser todos múltiplos de 8. Esto es imposible salvo que sean todos nulos. Esta anulación debe suceder antes de la etapa 8. En este caso sucede en la etapa 7.

6. Variantes posibles

Uno puede preguntarse si se tienen las mismas propiedades cuando, en lugar de cuatro números al inicio, se toman $3$, $5$, o más. Examinaremos esto en ’’Cajas con diferencias II’’.

Por otra parte, para los matemáticos es natural preguntarse lo que sucede si, en lugar de cuatro números enteros, se considera cuatro números reales. Eso será el tema de ’’Cajas con diferencias III’’.

Post-scriptum :

La redacción de Paisajes Matemáticos, así como el autor, agradecen por su atenta relectura a los relectores cuyos seudónimos son Omar Khettab, Newbie, reynald.thelliez, GoutteDeScience y Simon IOSTI.

Article original édité par Patrick Popescu-Pampu

Notes

[1Este juego se conoce en la literatura bajo el nombre de problema de Ducci o, en inglés, diffy boxes

[2Conocer bien un objeto es conocer en particular sus simetrías. Hace poco, visitando la exposición ’’’Animales Sexuales’’ en el Palacio del Descubrimiento, escuché a la guía decirnos que los animales (entre los cuales estamos nosotros) ¡siempre preferían elegir a la pareja cuyo rostro o cuerpo fuera más simétrico !

Partager cet article

Pour citer cet article :

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

Crédits image :

Image à la une - El logo, así como los otros dibujos, ha sido realizados con Geogebra.

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