Boites à différences I

Pista azul El 4 septiembre 2013  - Escrito por  Romain Bondil Ver los comentarios (6)
Leer el artículo en  

Voici un café dont j’aimerais qu’il soit digeste pour un élève de collège. On y rencontre, et c’est à la mode dans les nouveaux programmes, un algorithme.
Pour prouver que cet algorithme s’arrête, on doit vraiment faire des mathématiques : comprendre les symétries du problème, ce qui se conserve, ce qui diminue, et comment le fait de ne regarder que la parité permet finalement de résoudre le problème.

1. Présentation du jeu :

On peut jouer au jeu des boites à différences [1] pour faire pratiquer les soustractions, donc disons à partir du CE1. L’essentiel à cet âge-là est que cela ne dure pas trop longtemps !

De quoi s’agit-il ? On prend quatre nombres, pour l’instant quatre nombres entiers, par exemple 7,5,3,11, qu’on met sur la première ligne d’un tableau, dans cet ordre : c’est l’étape 0.

Ensuite pour passer d’une ligne à la suivante, à partir des quatre nombres $a,b,c,d$ de la ligne en cours, on écrit les distances $dist(a,b), dist(b,c), dist(c,d), dist(d,a)$ sur la ligne suivante : par définition la distance $dist(a,b)$ est $b-a$ si $b ≥ a$ et $dist(a,b)= a-b$ si $a ≥ b$. Autrement dit, c’est le résultat de la soustraction qu’il est possible de faire entre $a$ et $b$ tout en restant dans le monde des nombres positifs.

Avec les nombres choisis ci-dessus on obtient :

7 5 3 11
2 2 8 4

À ce stade, la dernière différence $dist(d,a)$ (ici 11-7) paraît moins commode à faire que les autres.
Cette difficulté, qui vient de notre façon d’écrire dans un tableau, disparaîtra un peu plus loin.

Que se passe-t-il si on continue à faire ces différences ligne après ligne ?

Dans l’exemple précédent, les lignes suivantes sont :

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

Avec une telle ligne de quatre zéros, on dira que le jeu des différences s’arrête.

Une autre façon, plus jolie, de présenter le jeu précédent est de placer les quatre nombres comme sommets d’un carré et chaque différence au milieu entre les sommets. Ainsi pour la première étape :

Puis après 4 étapes :

On comprend alors mieux l’expression «boite à différences», mais ceci n’est faisable que si le jeu se termine rapidement ! En outre, il ne faut pas confondre les distances sur le dessin, avec la distance entre les deux nombres que nous avons introduite.

La question qui se pose : le jeu s’arrête-t-il toujours ?

À ce stade, vous devez déjà essayer avec quatre nombres de votre choix. Si vous n’avez pas envie de le faire à la main, c’est très facile à programmer.

Normalement, tous vos essais s’arrêteront (sauf erreurs de calcul répétées). Le but de ce qui suit est de comprendre pourquoi.

Notation importante pour la suite :  Notons $N(a,b,c,d)$ le nombre d’étapes qu’il faut pour arriver à $(0,0,0,0)$ en partant des quatre nombres $(a,b,c,d)$. Au stade où nous en sommes, nous ne savons pas encore si ce nombre est toujours fini. Mais dans l’exemple que nous avons vu ensemble : $N(7,5,3,11)=7$.

Une version plus intéressante du jeu est donc de jouer à fabriquer des familles de 4 nombres, disons tous à deux chiffres, tels que le nombre d’étapes avant que le jeu finisse soit le plus grand possible.

2. Un premier contrôle : avec le maximum

Une première façon d’arriver à montrer que le jeu s’arrête serait de s’intéresser au maximum de $a,b,c,d$.

Une autre notation importante pour la suite : On notera $Max(a,b,c,d)$, le maximum, c’est-à-dire le plus grand des nombres $a,b,c,d$. Par exemple $Max(2,4,15,7)=15$.

Si on appelle $a',b',c',d'$ les nombres $a'=dist(a,b), b'=dist(b,c), c'=dist(c,d), d'=dist(d,a)$, et si aucun des nombres $a,b,c,d$ n’est nul, on est sûr que $a'< Max(a,b), b'< Max(b,c), c'< Max(c,d), d'< Max(d,a)$ et donc que le maximum des quatre nombres diminue strictement à chaque étape. De la sorte on serait sûr que le jeu finisse en au plus $Max(a,b,c,d)$ étapes.

Mais ce n’est pas si simple car il faudrait alors examiner soigneusement ce qui se passe si l’un des nombres est nul, et cela peut se produire à une étape quelconque.
Ainsi, dans l’exemple de la première section, pendant les étapes suivantes le maximum reste constamment égal à 4 :

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

On pourrait en fait résoudre le problème de cette manière, en examinant tous les cas où il y a des zéros, mais j’ai choisi un autre chemin qui va permettre d’éviter une telle minutie.

Retenons néanmoins la :

Propriété : Si $(a',b',c',d')$ est obtenu à partir de (a,b,c,d) par le jeu des différences,
alors on sait que $Max(a',b',c',d') ≤ Max(a,b,c,d)$.

3. Quelques invariants ou symétries du problème

Avant de s’attaquer à la preuve du fait que le jeu finit, voici quelques remarques que feront facilement ceux et celles qui ont l’habitude de résoudre des problèmes : elles sont liées aux symétries du problème. [2]

Nous allons considérer ici quelques opérations sur les quatre nombres ordonnés $(a,b,c,d)$ qui ne changent pas le nombre d’étapes $N(a,b,c,d)$.

Opérations géométriques

Les deux opérations suivantes sont vues plus clairement à l’aide des dessins avec des carrés donnés à la fin du 1.

  • Rotation : On dira ici que les nombres ordonnés $(b,c,d,a), (c,d,a,b), (d,a,b,c)$ se déduisent de $(a,b,c,d)$ par rotation.
  • Réflexion : On dira aussi que les nombres ordonnés $(d,c,b,a)$ se déduisent de $(a,b,c,d)$ par réflexion, avec comme axe de symétrie la droite des milieux des segments $[a,d]$ et $[b,c]$. Ceci est illustré sur la figure ci-dessous.
    De même on dira que $(b,a,d,c)$ se déduisent de $(a,b,c,d)$ par réflexion (avec comme axe de symétrie la droite des milieux des segments $[a,b]$ et $[c,d]$).

$ $

Propriété : une rotation ou une réflexion comme ci-dessus ne changent pas le nombre $N$ d’étapes qu’il faut pour finir le jeu.

Pour comprendre cette propriété, il suffit de se rendre compte que le résultat du jeu à partir de $(b,c,d,a)$ par exemple se déduit, à chaque étape, de celui du jeu à partir de $(a,b,c,d)$ avec la même rotation. En fait, quand j’ai dessiné les quatre nombres dans un carré, je n’ai pas spécifié où l’on mettait $a$, j’avais choisi de le mettre au coin en bas à gauche, mais on sentait bien que ce choix n’avait pas d’importance.

Opérations algébriques

  • Addition Si à chacun des nombres $a,b,c,d$ on ajoute un nombre fixe $k$, et qu’on considère le jeu à partir de $(a+k,b+k,c+k,d+k)$, on ne change pas la suite du jeu, puisqu’on ne change pas les différences. En particulier $N(a+k,b+k,c+k,d+k)=N(a,b,c,d)$.
  • Multiplication Si on multiplie chacun des nombres $a,b,c,d$ par un nombre $k$ positif non nul, alors ce nombre $k$ restera toujours en facteur de toutes le différences : $(ka-kb)=k(a-b)$, etc.... D’où la :

$ $

Propriété : Toute la suite du jeu à partir de $(ka,kb,kc,kd)$ est la même qu’ à partir de $(a,b,c,d)$ en multipliant tout par $k$ à chaque étape.

En particulier $N(ka,kb,kc,kd)=N(a,b,c,d)$, pour $k$ non nul bien sûr.

4. Le jeu simplifié avec « pair » et « impair »

Imaginons que l’on remplace chacun des quatre nombres entiers $a,b,c,d$ par le symbole $p$ s’il est pair et par le symbole $i$ s’il est impair.

Ainsi $(2,5,7,4)$ sera remplacé par $(p,i,i,p)$.

Lorsqu’on effectue une étape du jeu, la distance entre deux impairs (ou entre deux pairs) donnera toujours un nombre pair, et la distance entre deux nombres dont l’un est impair et l’autre pair donnera toujours un nombre impair.

On considère donc le :

Jeu simplifié : Les règles sont les mêmes qu’au jeu des différences décrit plus haut, mais cette fois $a_1, ..., a_4$ ne sont plus des nombres entiers mais des symboles $p$ ou $i$, et les distances sont définies par $d(p,i)=d(i,p)=i, d(p,p)=d(i,i)=p$.

Par exemple, en une étape de ce jeu $(p,i,p,p)$ donne $(i,i,p,p)$.

 

Remarque importante : Dans le jeu simplifié fabriqué à partir de vrais nombres $a_1, ..., a_4$ on garde à chaque étape l’information «pair» ou «impair» sur les nombres qui apparaissent dans le vrai jeu à la même étape.

Par exemple, $(2,4,5,6)$ devient $(p,p,i,i)$, qui par le jeu simplifié donne $(p,i,i,p)$, ce qui traduit bien la parité des nombres obtenus au vrai jeu à partir de $(2,4,5,6)$ à savoir $(2,1,1,4)$.

L’avantage du jeu simplifié est qu’il n’y a qu’un nombre fini de possibilités au départ : en fait seize exactement.

Le jeu simplifié s’arrête si on arrive à $(p,p,p,p)$ (puisqu’ensuite on obtiendrait toujours $(p,p,p,p)$). Il est facile, mais un peu long, de tester sur les quinze autres possibilités de départ que l’on arrive toujours à $(p,p,p,p)$, donc que le jeu simplifié s’arrête toujours.

En fait les résultats de symétries donnés par le paragraphe 3, (rotations et réflexions) permettent de réduire le nombre de cas (exercice : combien de cas a-t-on vraiment besoin de tester ?)

En voici un pour l’exemple :

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

On vérifiera aussi que parmi les 15 possibilités différentes de $(p,p,p,p)$, toutes donnent un jeu simplifié qui s’arrête au bout de 4 étapes au plus.

5. Comment on déduit la solution du jeu réel de celle du jeu simplifié

La section 4 nous a montré que le jeu simplifié s’arrête toujours, en au plus quatre étapes, et en même temps, (voir la remarque importante ci-dessus), on y garde à chaque étape l’information «pair» ou «impair» sur les nombres qui apparaissent dans le vrai jeu à la même étape.

On conclut donc qu’à partir de n’importe quels nombres $(a,b,c,d)$, au bout de quatre étapes au maximum, on obtient des nombres tous pairs, donc de la forme
$(2 a_1, 2 b_1, 2 c_1, 2d_1)$.

Comme on l’a dit au paragraphe sur les invariances et symétries, on sait alors que tous les nombres qui apparaîtront ensuite dans le jeu seront pairs. Ils s’obtiendront en prenant le jeu à partir de $(a_1, b_1, c_1, d_1)$, en multipliant par 2.

Mais, de même, pour le jeu à partir de $(a_1, b_1, c_1, d_1)$, en au plus quatre étapes, on obtiendra encore des nombres pairs, de la forme $(2a_2, 2b_2, 2c_2, 2d_2)$.

Ainsi à partir de cette nouvelle étape, dans le jeu à partir de $(a,b,c,d)$, tous les nombres seront des multiples de $4= 2 \times 2$.

En continuant ainsi, on aura ensuite des nombres tous multiples de
$8= 2 \times 2 \times 2$, puis de $16, 32, 64$, et ceci, indéfiniment ! On va montrer que ceci force ces nombres à être nuls à partir d’un certain moment.

En effet, comme on a vu à la fin de la section 2, à chaque étape du jeu, le maximum des quatre nombres ne dépasse pas $M=Max(a,b,c,d)$, le maximum des nombres choisis au départ.

Or des nombres non nuls inférieurs à un nombre $M$ fixé ne peuvent pas être divisibles par un nombre de la forme $2 \times 2 \times \cdots \times 2$
qui est plus grand que $M$ !

Ceci force les nombres du jeu à être nuls à partir d’un certain moment.

  Nous avons enfin démontré que le jeu s’arrête

Pour mieux digérer cette démonstration abstraite : reprenons-en le fil sur l’exemple du début

On reprend donc $(a,b,c,d)=(7,5,3,11)$ (ce qui signifie $a=7,b=5$, etc). Par commodité, je reproduis le tableau des distances successives du début de l’article :

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

Après une étape on a $(a',b',c',d')=(2,2,8,4)$, donc tous les nombres sont pairs. On sait alors que tous les nombres suivants seront aussi pairs et que le jeu serait le même si on repartait de $(1,1,4,2)$ à condition de multiplier par $2$ à chaque étape.

À son tour, le jeu à partir de $(1,1,4,2)$ doit donner en moins de quatre étapes un quadruplet de nombres pairs, et c’est bien ce que l’on constate puisqu’ à l’étape quatre de notre exemple du début, on a $(4,0,0,4)$ c’est-à-dire $2$ fois $(2,0,0,2)$.
 
À partir de ce moment-là, on est sûr que tous les nombres seront multiples de 4, mais le maximum ne peut pas augmenter et donc il doit rester inférieur à $Max(4,0,0,4)=4$. Or le raisonnement précédent nous dit qu’en au plus quatre étapes les nombres vont tous devenir multiples de 8. C’est impossible sauf s’ils sont tous nuls. Cette annulation doit arriver avant l’étape 8, elle arrive à l’étape 7 ici.

6. Variantes possibles :

On peut se demander si on a les mêmes propriétés si au lieu de quatre nombres au départ, on en prend $3$, ou $5$, ou davantage. Nous examinerons cela dans « Boîtes à différence II ».

D’autre part, pour les mathématiciens, il est naturel de se demander ce qui se passe si au lieu de quatre nombres entiers, on considère quatre nombres réels. Cela fera l’objet de « Boîtes à différence III ».

Post-scriptum :

La rédaction d’Images des maths, ainsi que l’auteur, remercient pour leur relecture attentive, les relecteurs dont le pseudonyme est le suivant : Omar Khettab,
Newbie,
reynald.thelliez,
GoutteDeScience et
Simon IOSTI.

Article édité par Patrick Popescu-Pampu

Notas

[1ce jeu est connu dans la littérature sous le nom de problème de Ducci ou, en anglais, diffy boxes

[2Bien comprendre un objet, c’est notamment connaître ses symétries. Ce fait est bien connu des mathématiciens. Récemment, en visitant l’exposition « Bêtes de sexes» au Palais de la Découverte, j’ai entendu la guide nous dire que les animaux (dont nous sommes) préféraient toujours choisir le partenaire dont le visage, le corps, est le plus symétrique !

Comparte este artículo

Para citar este artículo:

Romain Bondil — «Boites à différences I» — Images des Mathématiques, CNRS, 2013

Créditos de las imágenes:

Imagen de portada - Le logo comme les autres dessins ont été réalisés avec Geogebra.

Comentario sobre el artículo

Voir tous les messages - Retourner à l'article

  • Boites à différences I

    le 9 de septiembre de 2013 à 11:59, par jean marc esch

    bonjour

    voila une chose plaisante que de jouer avec les nombres . je trouve cela très relaxant . la je ne vais pas plaire a tout le monde mais je vais résonner avec mon intuition : la science est le domaine des faits , la numérologie le domaine de l’imagination ! je sais science et ésotérisme ne font pas bon ménage ^^ .
    mais les carrés magiques aussi sont une source de joie . l’univers n’est lui même qu’une grande suite mathématique qui n’as pas de fin! alors j’adore ces petits problèmes a résoudre ! merci pour ce post intéressant j’ai deja initiés mes enfants aux joie des carrés magiques et je vais leur proposer celui la .

    cordialement

    Répondre à ce message

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.