Les cryptarithmes (point de vue historique, exemples)

Introduction

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.

Quel intérêt pour les élèves ?

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.

Un modèle simple : les additions lacunaires

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.

Quelques exemples élémentaires

En voici quatre, qui, vu leur simplicité, sont donnés sans justification de leur solution :

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$).

Un exemple un peu plus complexe

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.

Les additions cryptées

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 :

• Une écriture décimale comportant au moins deux symboles dont au moins une lettre est surlignée : ainsi $\overline{A2B}$ désigne le nombre dont $A$ est le chiffre des centaines, 2 celui des dizaines, $B$ celui des unités.
• Afin d’éviter toute confusion, les produits sont toujours désignés par le symbole $\times$ : on peut ainsi distinguer nettement $2\times N$ de $\overline{2N}$.

Un exemple simple : $\overline{AC}+\overline{BC}=\overline{CDA}$

$\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.

Hésitation : $\overline{NON}+\overline{NON}=\overline{OUI}$

Solution

On a évidemment $\overline{NON}\lt 500$, donc $N\leqslant 4$. En regardant le chiffre des unités, il vient $I=2\times N$ ou $I+10=2\times N$. Le second cas est à exclure car on aurait $I+10\leqslant 2\times 4$.
On a donc $I=2\times N$, ce qui permet de supprimer dans l’égalité le chiffre des unités : $\overline{NO}+\overline{NO}=\overline{OU}$.
Cela donne :

• Premier cas : $U=2\times O$ et $O=2\times N$, impossible car il conduit à $O=I$
• Deuxième cas : $U+10=2\times O$ et $O=2\times N+1$ et donc $U=4\times N+2-10=4\times N-8$. $I\leqslant 9$ impose $N\leqslant 4$, $U\leqslant 0$ impose $N\geqslant 2$. $N \in \{2,3,4\}$, ce qui fait trois sous-cas à étudier :
  • $N=2$. On a $I=4$, $O=5$ et $U=0$. Ce cas conduit à $\mathbf{252+252=504}$, qui convient manifestement.
  • $N=3$. On a $I=6$, $O=7$ et $U=4$. Ce cas conduit à $\mathbf{373+373=746}$, qui convient aussi.
  • $N=4$. On a $I=8$, $O=9$ et $U=8$, valeur identique à $I$, ce qui ne convient pas.

On a donc deux solutions :

$$\mathbf{252+252=504}$$

$$\mathbf{373+373=746}$$

Revirement : $\overline{OUI}+\overline{OUI}=\overline{NON}$

Solution

Ce frère jumeau du précédent est un peu plus délicat. On démarre de la même façon :
$\overline{OUI}<500$ et donc $O\leqslant 4$. $\overline{NON}$ est pair, donc $N$ aussi. En regardant le chiffre des unités, il vient $N=2\times I$ (premier cas) ou $N+10=2\times I$ (deuxième cas).

• Premier cas : $N=2\times I$. En supprimant le chiffre des unités ont est ramené à $\overline{OU}+\overline{OU}=\overline{NO}$
• * sous-cas n°1 : $U+U=O$ et $O+O=N$. $N=2\times O$ et donc $O=I$, ce qui est exclu.
• * sous-cas n°2 : $U+U=O+10$ et $O+O+1=N$ ce qui conduit à $N=2\times O+1$, impair ce qui est exclu.
• Deuxième cas (seul éventuellement possible) : $N+10=2\times I$. En supprimant le chiffre des unités ont est ramené à $\overline{OU}+\overline{OU}+1=\overline{NO}$. Donc $\overline{NO}$ est impair et par suite $O$ aussi. Comme $O\leqslant 4$, les deux cas à étudier sont $O=1$ et $O=3$.
  • $O=1$. De $\overline{OU}+\overline{OU}+1=\overline{NO}$, on tire $\overline{NO}\leqslant 39$. Comme $N$ est pair $N=2$. Alors $\overline{1U}+\overline{1U}+1=21$ donne $U=0$. On trouve $\mathbf{106+106=212}$ qui convient.
  • $O=3$. De $\overline{OU}+\overline{OU}+1=\overline{NO}$, on déduit $61+2\times U=10\times N+3$. Soit encore $29+U=5\times N$. Comme $N$ est pair, $29+U$ est multiple de 10. Ainsi $U=1$. $\overline{OU}+\overline{OU}+1=\overline{NO}$ s’écrit alors $63=\overline{N3}$ ce qui donne $N=6$. De $N+10=2\times I$ on déduit $I=8$. On est conduit à $\mathbf{318+318=636}$ qui fournit une seconde solution.

On a donc deux solutions :

$$\mathbf{106+106=212}$$

$$\mathbf{318+318=636}$$

Un problème espagnol : $\overline{DOS}+\overline{DOS}+\overline{TRES}=\overline{SIETE}$

Solution

La recherche est laissée aux soins du lecteur. La réponse est $581+581+9 231=10 393$. Les premiers résultats accessibles sont $S=1$, $I=0$, $E=3$.

Imbuvable : $\overline{COCA}+\overline{COLA}=\overline{OASIS}$

Solution

$\overline{COCA}<10 000$ et $\overline{COLA}<10 000$, donc $\overline{OASIS}<20 000$. $O=1$. $A\neq1$ et si $A=0$ alors $S=A=0$ (à exclure). On a donc $A\geqslant 2$.
On a : $\overline{COCA}+\overline{COLA}>12 000$. Cette inégalité impose $C\geqslant 6$.
$S$ est pair car $S=A+A$ ou $S+10=A+A$ (analyse du chiffre des unités).
$S$ apparaît comme chiffre des centaines du résultat. On obtient ce chiffre en ajoutant éventuellement une retenue provenant de la somme des dizaines à $1+1$ ($O=1$). On obtient donc soit $S=2$ (sans retenue) ou bien $S=3$ (avec retenue). Le dernier cas est à exclure car $S$ est pair. Ainsi $S=2$ et il n’y a pas eu de retenue en ajoutant les dizaines.
Le cas $S=A+A$ ne peut se produire car il conduit à $A=1=O$.
Ainsi $S+10=A+A$ donne $12=A+A$ et $A=6$.
Comme l’addition des dizaines n’a pas donné lieu à une retenue, le problème se sépare en deux : d’une part $\overline{CO}+\overline{CO}=\overline{OAS}$ et d’autre part $\overline{LA}+\overline{CA}=\overline{IS}$. En injectant les chiffres déjà déterminés dans la première égalité, on obtient $\overline{C1}+\overline{C1}=162$ ce qui conduit à $C=8.$ La seconde devient donc $\overline{L6}+\overline{86}=\overline{I2}$ ce qui se ramène à $L+9=I$. Le seul choix possible est $L=0$ et $I=9$.

La réponse est donc $\mathbf{8 186+8106=16 192}$.

Une somme de trois termes : $\overline{UN}+\overline{UN}+\overline{NEUF}=\overline{ONZE}$

Solution

• $\overline{ONZE}\gt\overline{NEUF}$ conduit à $O\geqslant N$. Le cas d’égalité est à exclure. Alors $O\geqslant N+1$. De plus si $O\geqslant N+2$ on aurait $\overline{ONZE}-\overline{NEUF}\gt 1 000$. Ce cas est à exclure car $\overline{UN}+\overline{UN}\lt200$. Ainsi $O = N+1$.
• Le problème se ramène à $\overline{UN}+\overline{UN}+\overline{EUF}=1 000+\overline{NZE}$. Le second membre est supérieur à 1 100, ce qui donne $\overline{EUF}\gt 900$ et donc $E=9$. En enlevant 900 aux deux membres on obtient $\overline{UN}+\overline{UN}+\overline{UF}=100+\overline{NZE}$. Comme $\overline{UN}+\overline{UN}+\overline{UF}\lt 300$, on a $\overline{NZE}\lt 200$ ce qui donne $N=1$ ($N$ ne peut être nul). $O=N+1=2$.
• On regarde les chiffres des unités dans $\overline{UN}+\overline{UN}+\overline{UF}=100+\overline{NZE}$. On a $2+F=9$ ou $2+F=10+9$. Le deuxième cas est impossible donc $F=7$.
• On reporte dans $\overline{UN}+\overline{UN}+\overline{UF}=100+\overline{NZE}$ les chiffres déjà déterminés : $\overline{U1}+\overline{U1}+\overline{U7}=100+\overline{1Z9}$. Ainsi $3\times U = \overline{2Z}$. Nous avons pour U les choix suivants :
  • $U=7$ qui doit être exclu car $F=7$
  • $U=8$ qui conduit à $Z=4$
  • $U=9$ qui doit être exclu car $E=9$.
• La seule possibilité est donc $U=8$, $Z=4$. On vérifie qu’elle convient : $\mathbf{81+81+1987=2149}$.
  

Le problème fondateur

Portrait d’Henry Ernest Dudeney

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}$$

Solution

• Première étape : $\overline{SEND}+\overline{MORE}<10 000+10 000$ donc $\overline{MONEY}<20 000$, et $M=1$.
  Alors $\overline{MORE}<2000$ et par suite $\overline{SEND}+\overline{MORE}<12 000$, donc $O$ vaut 0 ou 1, Comme $M=1$, il reste $O=0$.
  De $\overline{MONEY}\geqslant 10 234$ et $\overline{MORE}\leqslant 1 098$, on tire $\overline{SEND}\geqslant 9 136$, donc $S=9$.
• Deuxième étape : on a donc $9 000+\overline{END}+1 000+\overline{RE}=10 000+\overline{NEY}$, ce qui ramène à un problème de taille plus modeste, où les chiffres représentées par les lettres sont à prendre dans [2 ;8] :
  

  $$\overline{END}+\overline{RE}=\overline{NEY}$$

  
  $\overline{NEY}$ s’obtient en ajoutant à $\overline{END}$ un nombre inférieur à 100, donc $N = E + 1$. Il vient alors $\overline{ND}+\overline{RE}=\overline{EY}+100$ et $\overline{ED}+\overline{RE}=\overline{EY}+90$, d’où :
  

  $$D+\overline{RE}=Y+90$$

• Troisième étape : de $D+\overline{RE}>90$ et $R\neq 9$ ($R=9$ donnerait $R=S$ ) on tire $R=8$. $D+\overline{RE}=Y+90$ devient alors $D+E=Y+10$, les chiffres $D$, $E$, $Y$ étant à prendre dans [2 ;7]. On a $D+E\leqslant 7+6$ , donc $Y$ vaut 2 ou 3.
  Si on avait $Y=3$, on aurait soit $D=7$, $E=6$, ce qui est exclu car comme $N=E+1$, on aurait donc $D=N=7$, soit $D=6$, $E=7$, ce qui donnerait $N=8$, donc $N=R$.
  La seule possibilité est donc $Y=2$, ce qui donne $D=7$, $E=5$ ou $D=5$, $E=7$ ; mais la seconde éventualité est exclue car menant à $N=8=R$.
  Reste à voir que l’unique possibilité restante convient bien. On vérifie :

$$\mathbf{9 567+1 085=10 652}$$

Problèmes multiplicatifs

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.

Très simple : une puissance quatrième

$\overline{ABC}=\overline{C}^{4}$

Solution

On a $100\lt C^{4}<1 000$. Mais $3^{4}=81$, $4^{4}=256$, $5^{4}=625$, $6^{4}=1 296$. $C$ vaut donc 4 ou 5. Le chiffre des unités de $C^{4}$ étant $C$ seul $C=5$ convient. On a bien $\mathbf{625=5^{4}}$.

$\overline{ABCD}=\overline{D}^{4}$

Solution

On a $1 000\lt D^{4}$ donc $D\geqslant 6$. Si D vaut 7, 8 et 9, le chiffre des unités de $D^{4}$ vaut respectivement 1, 6 et 1, différent de $D$ dans ces trois cas. $6^{4}=1 296$ convient donc $D=6$.

Assez simple

Un exemple historique

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.

Un autre exemple tiré de Sphinx

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.

Solution

Pour plus de commodité, nous allons utiliser des lettres à la place des trous à compléter pour les deux nombres dont on fait le produit. Les lettres représenteront dans ce cas ci des chiffres a priori non forcements distincts :

$$\overline{AB3C}\times\overline{PQ3}$$

• De l’analyse du premier produit partiel $\overline{AB3C}\times 3=\overline{3\bullet\bullet\bullet}$, on tire $A=1$ et $B\leqslant 3$. $B=3$ étant exclu par l’énoncé, $B$ vaut 0, 1 ou 2.
• Du deuxième produit partiel $\overline{1B3C}\times Q=\overline{\bullet\bullet\bullet\bullet33}$ on tire $Q\geqslant \dfrac{10 033}{1 239}\approx 8,09$. Donc $Q=9$.
• Toujours dans le deuxième produit partiel, le chiffre des unités de $\overline{1B3C}\times 9=\overline{\bullet\bullet\bullet\bullet33}$ impose $C=7$
• Il reste à déterminer $B$ et $P$.
• Le cas $B=0$ peut être exclu en regardant le deuxième produit partiel qui a cinq chiffres. Si $B=0$, le deuxième produit partiel vaudrait $1 037\times 9 = 9333$ qui a le double défaut de ne comporter que quatre chiffres et d’avoir un 3 pour chiffre des centaines (ce qui aurait du être révélé selon l’énoncé). Ainsi $B=1$ ou $B=2$.
• Le produit $\overline{1B37}\times \overline{P93}$ a sept chiffres. Il est au moins égal à 1 000 000. On a donc $1 237\times \overline{P93}\geqslant\overline{1B37}\times \overline{P93}\geqslant 1 000 000$, d’où on déduit $\overline{P93}\geqslant \dfrac{1 000 000}{1 237}$, d’où $\overline{P93}\geqslant 808$. $P$ vaut 8 ou 9.
• Cas où $P=9$ : en regardant le troisième produit partiel on aurait $\overline{1B37}\times 9\geqslant 1 137\times 9=10 233$, ce qui est impossible car ce produit est annoncé avec quatre chiffres. On a donc $P=8$.
• Deux produits sont à essayer : 1 137×893 et 1 237×893
  • Le premier essai est infructueux car un 3 non révélé par l’énoncé apparaît au résultat.

    

  • 1 237×893 remplit toutes les conditions, donc convient.

    

Un problème de congruences [3]

Solution

$$\overline{MATH} \times \overline{MATH} = \overline{\bullet\bullet\bullet\bullet MATH}$$

Posons $x=\overline{MATH} $. La principale information que nous ayons est $x^{2}\equiv x \mod 10 000$ :

• $10^{4}$ divise $x(x-1)$
  De plus :
• $x$ et $x-1$ sont premiers entre eux.
• $10^{4}=2^{4}\times 5^{4}$

Cela signifie que chacun des deux nombres $2^{4}$ et $5^{4}$ divise $x$ ou $x-1$. Ils ne peuvent pas diviser le même car $x$, qui n’a que quatre chiffres, serait divisible par 10 000 ce qui n’est pas possible pour un nombre avec quatre chiffres.

Donc :

• 625 divise $x$ et 16 divise $x-1$ (premier cas), ou
• 16 divise $x$ et 625 divise $x-1$ (deuxième cas).

• Premier cas : Posons $x=625\times h$. De $625\equiv 1 \mod 16$ [4] on tire $x\equiv h \mod 16$. On veut que $x-1$ soit multiple de 16, donc que $h$ soit de la forme $16\times u+1$ et $x=625\times(16u+1)$. La valeur 625 ($u=0$) n’a pas assez de chiffres, la suivante, $625\times17=10 625$ a trop de chiffres. On peut donc exclure ce premier cas.
• Deuxième cas : Posons $x-1=625\times k$ et donc $x=625\times k +1$. On sait que 16 divise $x$. Ainsi $625\times k +1\equiv 0 \mod 16$. Comme $625\equiv 1 \mod 16$, $k+1\equiv 0 \mod 16$. Pour $k=15$ on a $x=625\times 15 +1 = 9 376$. Les autres valeurs de $k$ fournissent pour $x$ des écritures à au moins cinq chiffres, ce qui les exclut.
• Reste à déterminer si $\overline{MATH}=9 376$ convient. La seule condition à vérifier est que le carré de $\overline{MATH}$ ait huit chiffres. Or $\mathbf{9 376^{2}=97 909 376}$, ce qui règle la question.
  

Pour finir : hommage à une gloire nationale

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.

Conclusion

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 ?

Les cryptarithmes (un prétexte pour faire de l’algorithmique)

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.