Boites à différences I

Piste bleue 4 septembre 2013  - Ecrit par  Romain Bondil Voir les commentaires (6)

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

Notes

[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 !

Partager cet article

Pour citer cet article :

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

Crédits image :

Image à la une - Le logo comme les autres dessins ont été réalisés avec Geogebra.

Commentaire sur l'article

  • Boites à différences I

    le 9 septembre 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
  • Boites à différences I

    le 22 septembre 2013 à 19:05, par Yannick Danard

    Bonjour,
    Pour l’avoir testé auprès d’élèves de 3ème, c’est effectivement digeste pour un élève de collège. En tout cas pour ce qui est de formuler la conjecture : le jeu des différences s’arrête. Ce fut l’occasion d’un travail très intéressant.
    La démonstration complète semble en revanche peu accessible en 3ème mais je ne doute pas qu’elle puisse passionner dès cet âge des esprits curieux...
    Merci beaucoup pour ce café, j’attends le II et le III avec impatience !

    Cordialement

    Répondre à ce message
  • Boites à différences I

    le 23 septembre 2013 à 22:37, par Romain Bondil

    Merci beaucoup de vos commentaires et du test grandeur nature sur une classe.
    Pour ce qui est de la curiosité en maths, j’écoutais la très bonne émission Science publique de vendredi dernier sur les expériences de recherche scientifique à l’école,
    (à écouter sur http://www.franceculture.fr/emission-science-publique-0) avec grand plaisir, jusqu’à ce que j’entende un intervenant qui y déplorait quand même que « les matières demandées pour la formation des maîtres : le français, le maths, le sport, ne développaient pas la curiosité scientifique... »

    Sale coup pour les maths quand même, même après avoir précisé « les maths à ce niveau... » (c’est-à-dire celui de la formation des maîtres !)

    Répondre à ce message
  • Boites à différences I

    le 17 novembre 2013 à 10:43, par Dasson

    Merci pour ce texte que j’ai utilisé dans ce programme en test :
    http://rdassonval.free.fr/flash/differences.swf

    Répondre à ce message
  • Boites à différences I

    le 22 novembre 2013 à 21:42, par Prof Gra

    Bonjour,

    Merci pour cet article, que je pense pouvoir exploiter de la seconde à la terminale (ISN surtout).

    Je n’ai pas compris la phrase « On vérifiera aussi que parmi les 15 possibilités différentes de (p,p,p,p) » du premier coup. Ne serait-il pas plus lisible :

    1) de mettre cette phrase avant l’exemple (qui passe au féminin),

    2) de ne pas utiliser « 15 possibilités différentes de (p,p,p,p) », mais plutôt « configurations restantes », sans en donner le nombre (que de toutes façons vous proposez de réduire juste avant).

    Merci encore.

    Répondre à ce message
  • Boites à différences I

    le 22 novembre 2013 à 22:23, par Romain Bondil

    Bravo à « Dasson » pour son joli programme flash !
    C’est exactement ce que j’aurais voulu faire moi-même pour illustrer les boîtes, mais la technique n’avait pas suivi. Donc grand merci.

    Pour ProfGra : merci de la remarque. Hélas, je ne peux plus modifier le texte maintenant sur la site. Pour l’ISN en Terminale, je pense qu’on peut aller jusqu’à boîte à différences II non ?

    Répondre à ce message

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

Suivre IDM