Pierre Legrand a écrit un grand nombre d’articles pour le Bulletin de l’APMEP, dont certains sous le pseudonyme Julien Moreau. Il a fait partie de son équipe de rédaction de 1994 au printemps 2017, date à laquelle celle-ci a démissionné en bloc.
L’article qui suit est le fruit du travail successif de Pierre Legrand, à l’initiative du projet, et du comité de rédaction de MathémaTICE. L’article initial a suscité de nombreux débats en comité de rédaction au sujet de la résolution informatique des problèmes proposés. Patrick Raffinat a accepté de rédiger une seconde partie algorithmique avec des programmes Scratch, Blockly et Python.
L’article final comporte donc deux parties : un premier onglet contient l’article initial, un deuxième propose la résolution du problème au moyen des outils informatiques.
Ces deux parties sont évidemment complémentaires : l’approche de Pierre Legrand rappelle qu’on peut faire des mathématiques sans aucune machine (on a tendance à l’oublier), le complément de Patrick Raffinat met en évidence des solutions du problème qui supposent d’autres compétences.
Les récréations arithmétiques ont un passé vieux d’au moins deux millénaires, mais elles ont évolué avec le temps. Celles qu’a connues l’Antiquité grecque portaient le plus souvent sur des problèmes du premier degré tels qu’en utilisa jadis notre certificat d’études. Puis sont venus au fil du temps des casse-têtes plus variés et souvent plus complexes.
Bizarrement [1], un des types les plus élémentaires d’énigme arithmétique, les additions et multiplications lacunaires ou masquées, n’a fait une timide entrée qu’à la fin du XIXe siècle.
Les exemples se sont multipliés dans la première moitié du XXe siècle et ce type de jeu a connu alors une vogue certaine, avant de retomber dans un relatif oubli.
Les cryptarithmes [2] , puisque tel est leur nom, ne font appel qu’à un strict minimum de notions mathématiques : les quatre opérations, le maniement des inégalités, la divisibilité, des rudiments sur les congruences (qu’on peut toujours remplacer par l’étude des restes de division par 2, 5, 10, 100 ou 1000) et à l’occasion le raisonnement par l’absurde. Ils sont donc marginaux par rapport aux programmes des classes.
En revanche, ils demandent de la méthode, une certaine ingéniosité et la capacité d’utiliser plusieurs idées différentes pour parvenir à un résultat. S’ils ne contribuent guère à consolider les connaissances, ils constituent, outre un agréable passe-temps, un bon entraînement à l’autonomie de raisonnement.
Il s’agit d’une addition correcte dans laquelle on a masqué un certain nombre de chiffres. Le jeu consiste à reconstituer l’écriture complète.
Selon le nombre de chiffres occultés, le travail peut être immédiat ou demander un peu de réflexion. Si on se limite à des exercices où manquent au plus deux chiffres, ce type de jeu peut être utilisé pour consolider au cours moyen ou en sixième la maîtrise de l’addition et de la soustraction et approfondir la compréhension de leurs mécanismes.
En voici quatre, qui, vu leur simplicité, sont donnés sans justification de leur solution :
174 + 2∎8 = 40∎ | 71 + 9∎ = ∎65 | 1∎6∎ + ∎3∎7 = 5073 | 7 + ∎∎ = ∎∎3 |
174 + 228 = 402 | 71 + 94 = 165 | 1766 + 3307 = 5073 | 7 + 96 = 103 |
Chacun de ces exemples peut être présenté de trois façons : une addition et deux
soustractions ( $x+ y= z$, $z −x =y $, $z −y = x$).
Soit à compléter 1 ∎8∎ + ∎ 4∎5 = ∎∎ 721.
Le premier membre est inférieur à 2 000 + 9 500 = 11 500. Le second membre est donc au plus égal à 10 721, mais comme il a 5 chiffres et se termine par 721, c’est 10 721.
On est donc ramené à 1 ∎8∎ + ∎ 4∎5 = 10 721. La considération du chiffre des unités mène à 1 ∎86 + ∎ 4∎5 = 10 721, dont on déduit 1 ∎80 + ∎ 4∎0 = 10 710. On est ainsi ramené à 1∎8 + ∎4∎ = 1 071. Le chiffre des unités de ∎4∎ est donc 3.
De 1∎8 + ∎43 = 1 071 on déduit 1∎0 + ∎40 = 1 060, donc 1∎ + ∎4 = 106. On en tire aisément que les deux chiffres manquants sont respectivement 2 et 9.
Finalement, l’addition reconstituée est 1 286+9 435=10 721.
Dans la résolution du problème précédent, nous avons été gênés par le fait que les six chiffres manquants dans l’égalité de départ étaient représentés par le même symbole ∎. Il aurait été plus commode de leur donner à chacun un nom, par exemple $x, y, z, t, u, v $.
Cela nous mène à l’idée d’addition cryptée, où chaque chiffre est représenté par une lettre, toujours la même, deux chiffres différents étant représentés par deux lettres différentes, la lettre la plus à gauche de l’écriture d’un nombre ne représentant jamais zéro.
Nous donnons ci-après, dans l’ordre de difficulté croissante, des problèmes dont tous les chiffres sont cryptés. Nous utiliserons les conventions d’écriture suivantes :
$\overline{AC}$ et $\overline{BC}$ sont strictement inférieur à 100, donc leur somme l’est donc à 200, donc $C=1$. En regardant le chiffre des unités des deux côtés on obtient $A = 2$.
$\overline{AC}+\overline{BC}=\overline{CDA}$ s’écrit alors $22 + 10\times B = 102 + 10\times D$, soit $10\times (B - D) = 80$ , donc $B=D+8$, donc $D = 0$ et $B = 8$ $(D = 1$ est à exclure puisque $D\neq C)$. Finalement, 21+81=102.
La mode des additions cryptées et plus généralement des cryptarithmes fut lancée en juillet 1924 par un casse-tête d’Henry Dudeney sorti dans le Strand Magazine, la revue mensuelle qui publiait les aventures de Sherlock Holmes.
L’auteur (ci-contre) raconte l’histoire d’un jeune homme qui, à court d’argent, télégraphie à son père « SEND MORE MONEY ». Il s’agit en fait d’une addition, où chaque lettre représente un chiffre différent :
$$\overline{SEND}+\overline{MORE}=\overline{MONEY}$$
Les problèmes de multiplication cryptée ou lacunaire sont, étant donné la taille du produit, plus difficiles que les problèmes d’additions. Ils font en général utiliser abondamment la divisibilité et les congruences modulo une puissance de 10.
$\overline{ABC}=\overline{C}^{4}$
$\overline{ABCD}=\overline{D}^{4}$
La revue belge Sphinx , entièrement consacrée aux récréations mathématiques et logiques, fut fondée en 1931 par Maurice Kraitchik, spécialiste notoire de théorie des nombres. Elle connut un certain succès international jusqu’en 1939 mais périt victime de la guerre.
C’est dans Sphinx que fut publié en mai 1931 le premier exemple de multiplication cryptée qui est donné ci-dessous.
L’exemple ci-après (de janvier 1934) est assez curieux, car à la multiplication présentée est adjointe une mention qui à première vue semble anodine : « Tous les 3 sont indiqués », mais qui en fait doit être utilisée à deux reprises.
Cette énigme, plus difficile que les précédentes, date des alentours de 1960. Signalons qu’elle repose en partie sur la preuve par 9. Chacune des lettres représente un chiffre différent autre que zéro.
La résolution est laissée à la bonne volonté de chacun. Le lecteur fatigué pourra trouver une solution entièrement tricotée main dans ce document.
Ces exemples [5] l’ont, je pense, montré : les méthodes utilisées pour résoudre ces problèmes demandent de la patience et une certaine ingéniosité, mais elles sont finalement assez peu variées.
En outre, un informaticien objectera que, dans chacune de ces énigmes, le nombre d’éventualités à examiner est fini. On en connaît même une borne : si l’opération à reconstituer contient n chiffres inconnus, il y a au plus $10^{n}$ possibilités. Un petit programme doit donc pouvoir régler aisément la question.
C’est irréfutable. Mais on peut aussi se poser une question du même genre : pourquoi se fatiguer à faire des randonnées à pied alors qu’il existe des véhicules automobiles ?
Pour résoudre informatiquement un cryptarithme comportant n lettres distinctes, il suffit de balayer toutes les possibilités avec n boucles imbriquées. Par exemple, NON + NON = OUI peut être résolu ainsi en Python :
Comme ce principe de résolution peut facilement être transposé aux autres exemples de l’article, il est légitime de se demander s’il est utile de rédiger une partie consacrée au codage.
Si au final il y a un ajout informatique, c’est notamment parce que le comité de rédaction de MathémaTICE s’est demandé s’il peut être pédagogiquement fructueux de faire écrire des programmes par blocs aux collégiens sur les cryptarithmes.
Par ailleurs, il m’a incité à me pencher sur des aspects techniques a priori non destinés à des élèves : par exemple, comment utiliser en Python des permutations et des structures de données avancées (dictionnaires) pour résoudre SEND + MORE = MONEY. Un autre intérêt de ce cryptarithme est qu’il comporte 8 lettres à découvrir, soit potentiellement $10^{8}$ solutions à examiner : pour obtenir un temps d’exécution acceptable, il faut donc chercher à optimiser [6] un algorithme a priori 10000 fois plus long que celui de NON + NON = OUI.
Pour tester les divers programmes Python, il vaut mieux cliquer sur les liens « Télécharger » : en effet, si on se contente d’un copier coller, les caractères de tabulation ne sont pas toujours bien transférés, ce qui perturbe alors l’exécution en Python.
Proposée par Pierre Legrand :
Proposée par le comité de rédaction :
[1] Une partie de ce retard s’explique tout simplement par le temps qu’ont mis la numération décimale et les règles de calcul allant avec elle pour entrer vraiment dans les mœurs.
[2] Du grec : κρυπτος (caché) et αριθμος (nombre). Le terme daterait de 1931.
[3] Une généralisation de ce problème a été publiée dans le Bulletin Vert n° 484, pages 584-588, sous le titre « nombres rimant avec leur carré » .
[4] $625=39\times 16+1$
[5] Je remercie vivement Catherine Combelles, qui a vérifié les solutions de ces exercices et a rectifié plusieurs erreurs.
[6] Il est d’autant plus indispensable de réduire le temps d’exécution de SEND + MORE = MONEY que « TIME is MONEY » selon un proverbe bien connu !
[7] Voir De la programmation par blocs à Python, avec SofusPy et PluriAlgo dans le N°57.
[8] Voir À la pêche aux groupes avec Python dans le N°57.
[9] C’est fastidieux, sauf si on fait du « Python avancé » : l’instruction L = [int(c) for c in str(BARDOT)] permet en effet de récupérer les 6 chiffres dans la liste L.