Les nouvelles technologies pour l’enseignement des mathématiques
Intégration des TICE dans l’enseignement des mathématiques

MathémaTICE, première revue en ligne destinée à promouvoir les TICE à travers l’enseignement des mathématiques.

Les cryptarithmes
Article mis en ligne le 7 décembre 2017
dernière modification le 27 novembre 2017

par Patrick Raffinat, Pierre Legrand

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 cryptarithmes (point de vue historique, exemples)

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 :

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

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

Solution

La ligne donnant $\overline{ABC}\times A=\overline{\bullet{} \bullet{} A}$ est « plus courte » que les deux autres. De la comparaison des produits partiels, on peut donc déduire $A\lt B$ et $A\lt C$. Comme $A$ n’est pas nul, $B$ et $C$ sont supérieurs ou égaux à 2.

De $\overline{ABC}\times A=\overline{\bullet \bullet A}$ on déduit que le chiffre des unités de $C\times A$ est $A$. Ainsi $C\times A-A=(C-1)\times A$ est multiple de 10.
A fortiori 5 divise $(C-1)\times A$, donc il divise $A$ ou $C-1$. Deux cas sont à examiner : $A=5$ ou $C=6$.

On peut appliquer le même raisonnement à $\overline{ABC}\times B=\overline{\bullet \bullet \bullet B}$. Ainsi soit $B=5$ soit $C=6$.

Si l’on avait $C\neq 6$, on aurait d’après ce qui précède $A= B=5$, ce qui est exclu. On a donc $C=6$.

10 divise $(C-1)\times A$ et $(C-1)\times B$, soit $5\times A$ et $5\times B$. $A$ et $B$ sont donc pairs. Ils valent 2, 4 ou 8. Comme $A \lt B$, on peut exclure le cas $A=8$. Il reste $A=2$ ou $A=4$, et $B=4$ ou $B=8$.

Supposons $A=4$. $\overline{ABC}\times A>1 600$ conduit à une contradiction car ce produit partiel n’a que trois chiffres. Ainsi $A=2$.

$B$ vaut donc 4 ou 8. Le premier cas conduit pour le troisième produit partiel à $\overline{ABC}\times B=246\times 4=984<1 000$. Ce produit n’a que trois chiffres au lieu de quatre.

Finalement $B=8$. On vérifie que $\mathbf{286\times826=236 236}$ convient bien.

Un exemple historique

première page de l’édition du numéro 2, février 1932
Cliquer pour agrandir

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.

Solution

  • $D\times \overline{ABC}$ et $E\times \overline{ABC}$ finissent tous deux par $\overline{EC}$. Donc 100 divise $(D-E)\times\overline{BC}$. Il en résulte que 25 divise $\overline{BC}$ ou 5 divise à la fois $\overline{BC}$ et $D-E$. Dans les deux cas cela donne $C=5$ ou $C=0$.
  • En regardant l’addition des dizaines dans le détail de l’opération, on voit que $C=0$ entraînerait $E=B$. On a donc $C=5$.
  • 4 divise $(D-E)\times\overline{BC}$ et est premier avec $\overline{BC}$, puisque $C=5$. Donc 4 divise $(D-E)$, qui vaut ainsi $-8$, $-4$ , $4$ ou $8$.
  • 25 divise $(D-E)\times\overline{BC}$ et est premier avec $D-E$. Donc 25 divise $\overline{BC}$ qui se termine par 5. Les multiples impairs de 25 se terminent par 25 ou 75. Donc $B$ vaut 2 ou 7.
  • $\overline{ABC}$ est multiple de 25. C’est le cas aussi de $\overline{FEC}$ car $\overline{FEC}=\overline{ABC}\times E$. De plus $\overline{FEC}$ est impair puisque de terminant par 5. $\overline{EC}$ vaut donc 25 ou 75. Si on avait $E=2$, le produit $\overline{ABC}\times E$ serait pair. C’est impossible car il est égal à $\overline{FEC}$ qui est impair .
  • On a donc : $\overline{EC}=75$, $\overline{BC}=25$ , soit $C=5$, $E=7$, $B=2$.
  • De $D-E=\pm 4$ ou $D-E=\pm 8$ et $E=7$ la seule possibilité pour $D$ est $D=3$.
  • De $\overline{ABC}\times D=\overline{DEC}$ on tire $\overline{ABC}\times 3=375$. $\mathbf{\overline{ABC}=125}$. Comme $\mathbf{\overline{DE}=37}$, la solution est bien déterminée.
  • On a procédé par conditions nécessaires. Il reste à vérifier que cette solution convient bien.

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)

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 :

  1. for N in range(1,10) :
  2.         for O in range(1,10) :
  3.                 for U in range(0,10) :
  4.                         for I in range(0,10) :
  5.                                 NON = 100*N + 10*O + N
  6.                                 OUI = 100*O + 10*U + I
  7.                                 if (NON+NON==OUI) :
  8.                                         print(NON)
  9.                                         print(OUI)

Télécharger

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.

NON + NON = OUI en programmation visuelle

L’équivalent Scratch du programme Python donné en introduction est quelque peu « indigeste », parce qu’il n’y a pas de bloc « Pour » :

Donc, si on veut traiter ce problème avec Scratch au collège, il faut chercher à réduire le nombre de boucles. Cela est possible en calculant OUI à partir de NON, puis en extrayant les chiffres le composant à partir de divisions par 10 :

Même si ce programme Scratch n’est pas aussi « indigeste » que le premier, il est loin d’être simple et quelques exercices préparatoires semblent nécessaires :

  • afficher les deux chiffres d’un entier compris entre 10 et 99
  • afficher les trois chiffres d’un entier compris entre 100 et 999
  • afficher tous les entiers entre 0 et 9 à l’aide d’une boucle « Répéter »
  • ...

Le problème est plus abordable avec l’extension SofusPy [7] de Blockly : non seulement il y a des boucles « Pour », mais il y a aussi un bloc permettant de calculer le quotient d’une division par 10 sans recourir à la fonction PartieEntière (voir programme). Cerise sur le gâteau, SofusPy peut aussi engendrer automatiquement ce programme Python à partir du programme Blockly :

  1. for N in range(1,10):
  2.         for O in range(1,10):
  3.                 NON = 100*N + 10*O + N
  4.                 OUI = NON + NON
  5.                 I = OUI % 10
  6.                 OU = OUI // 10
  7.                 U = OU % 10
  8.                 O_OUI = OU // 10
  9.                 if (O_OUI == O) :
  10.                         print(NON)
  11.                         print(OUI)

Télécharger

Aucun test n’a été inséré pour vérifier que les lettres ont des valeurs différentes, afin de ne pas alourdir le code. Cela paraît d’autant moins nécessaire qu’on n’obtient que 5 solutions potentielles, dont 3 sont à éliminer :

  • 121 + 121 = 242 (à éliminer car O=I=2)
  • 242 + 242 = 484 (à éliminer car O=I=4)
  • 252 + 252 = 504
  • 373 + 373 = 746
  • 494 + 494 = 988 (à éliminer car U=I=8)

Pour en finir avec cet exemple, il est à signaler qu’il peut être traité avec une unique boucle, en s’inspirant de la solution donnée pour l’exemple suivant (OUI+OUI=NON).

OUI+ OUI= NON en programmation visuelle

Comme il me semble problématique d’imbriquer 3 boucles « Répéter » au collège (une pour O, une pour U et une pour I), je vais proposer une autre stratégie : faire varier OUI entre 100 et 999, puis en déduire NON, puis extraire les chiffres de ces deux nombres pour faire des tests :

Il y a alors 4 solutions potentielles, dont 2 sont à éliminer pour des doublons :

  • 106 + 106 = 212
  • 212 + 212 = 424 (à éliminer car O=I=2)
  • 318 + 318 = 636
  • 424 + 424 = 848 (à éliminer car O=I=4)

SEND + MORE = MONEY en Python

Pour ce cryptarithme, il est clair que le M de MONEY ne peut qu’être égal à 1, ce qui permet ici un gain de temps non négligeable : dans l’environnement de test que j’ai utilisé, le temps d’exécution est ainsi passé de 70 secondes à 8 secondes. Contrairement au cryptarithme NON + NON = OUI, il est conseillé de veiller dans le programme à ce que tous les chiffres soient différents car il y aurait ensuite trop de fausses solutions à éliminer « manuellement » :

  1. def differents(*args):
  2.         return len(set(args)) == len(args)
  3.  
  4. m = 1
  5. for s in range(1, 10):
  6.         for e in range(0, 10):
  7.                 for n in range(0, 10):
  8.                         for d in range(0, 10):
  9.                                 for o in range(0, 10):
  10.                                         for r in range(0, 10):
  11.                                                 for y in range(0, 10):
  12.                                                         if differents(s, e, n, d, m, o, r, y):
  13.                                                                 send = 1000 * s + 100 * e + 10 * n + d
  14.                                                                 more = 1000 * m + 100 * o + 10 * r + e
  15.                                                                 money = 10000 * m + 1000 * o + 100 * n + 10 * e + y
  16.                                                                 if send + more == money:
  17.                                                                         print(send)
  18.                                                                         print(more)
  19.                                                                         print(money)

Télécharger

Pour une utilisation en classe au lycée, le code de la fonction « differents » serait bien sûr à fournir aux élèves. Elle construit un ensemble à partir des 8 lettres, puis vérifie si la longueur de l’ensemble est 8, ce qui signifie alors qu’il n’y a pas de doublons.

Suite à la publication d’un article utilisant les permutations en Python [8], plusieurs membres du comité de rédaction ont alors songé à les utiliser ... sans proposer de solution toutefois ! Heureusement, il n’est pas difficile d’en trouver une avec un moteur de recherche car ce cryptarithme est très étudié :

  1. import itertools
  2. letters = ('s', 'e', 'n', 'd', 'm', 'o', 'r', 'y')
  3. digits = range(10)
  4. for perm in itertools.permutations(digits, len(letters)):
  5.         sol = dict(zip(letters, perm))
  6.         if sol['s'] == 0 or sol['m'] == 0:
  7.                 continue
  8.         send = 1000 * sol['s'] + 100 * sol['e'] + 10 * sol['n'] + sol['d']
  9.         more = 1000 * sol['m'] + 100 * sol['o'] + 10 * sol['r'] + sol['e']
  10.         money = 10000 * sol['m'] + 1000 * sol['o'] + 100 * sol['n'] + 10 * sol['e'] + sol['y']
  11.         if send + more == money:
  12.                 print(send)
  13.                 print(more)
  14.                 print(money)

Télécharger

Grâce au module itertools, toutes les permutations de 8 chiffres sont engendrées et associées aux 8 lettres du cryptarithme. A l’arrivée, on récupère un tableau associatif (appelé aussi dictionnaire) à partir duquel on peut calculer les nombres SEND, MORE et MONEY. Bien évidemment, cette solution n’est pas destinée à des lycéens, mais est fournie pour satisfaire l’insatiable curiosité des lecteurs de la revue !

Le temps d’exécution est alors de 4.5 secondes, et on peut l’abaisser à 0.4 secondes en adaptant le programme précédent puisqu’on sait que M vaut 1. Pour calculer ces divers temps d’exécution, qui varient bien sûr suivant l’ordinateur utilisé, il suffit de compléter les programmes par ces instructions :

  1. import time
  2. debut = time.clock()
  3. ...
  4. fin = time.clock()
  5. print fin - debut

Télécharger

Hommage à une gloire nationale en Python

Le cryptarithme relatif à Brigitte Bardot est facile à résoudre, même s’il est fastidieux [9] d’extraire les 6 chiffres de la variable BARDOT :

  1. def differents(*args):
  2.         return len(set(args)) == len(args)
  3.  
  4. for S in range(1,10) :
  5.         for E in range(1,10) :
  6.                 for X in range(1,10) :
  7.                         SEX = 100*S+10*E+X
  8.                         B1 = (X*SEX) // 1000
  9.                         B2 = (E*SEX) // 1000
  10.                         BARDOT = SEX * SEX
  11.                         B3 = BARDOT // 100000
  12.                         if B1 == B2 and B1 == B3 :
  13.                                 T = BARDOT % 10
  14.                                 BARDO = BARDOT // 10
  15.                                 O = BARDO % 10
  16.                                 BARD = BARDO // 10
  17.                                 D = BARD % 10
  18.                                 BAR = BARD // 10
  19.                                 R = BAR % 10
  20.                                 BA = BAR // 10
  21.                                 A = BA % 10
  22.                                 if (differents(S,E,X,B1,A,R,D,O,T)) :
  23.                                         print(SEX)
  24.                                         print(BARDOT)

Télécharger

Pour une éventuelle utilisation en classe, mieux vaut remplacer ce cryptarithme par DIX fois DIX = QUATRE, plus neutre et moins inexact qu’il n’y paraît : en effet, 10 fois 10 en base 2 vaut 100, c’est à dire 4 en base 10.

ABC * BAC en programmation visuelle

L’intérêt de ce cryptarithme est qu’il peut être résolu avec une seule boucle : il est donc envisageable de le traiter au collège avec un programme visuel. Pour limiter le nombre de fausses solutions, j’utilise le fait que A est strictement inférieur à B et à C : en effet, A*ABC ne comporte que 3 chiffres, alors que B*ABC et C*ABC en comportent 4.

Il y a alors 3 solutions potentielles, dont 2 sont à éliminer :

  • 246 * 426 = 104796 (à éliminer car 4 *246 comporte 3 chiffres)
  • 286 * 826 = 236236
  • 486*846 = (à éliminer car 4*486 comporte 4 chiffres)

Conclusion

Au collège, il vaut mieux privilégier la résolution de cryptarithmes pouvant être résolus avec une seule boucle (voire deux), d’autant que Scratch ne propose pas de boucle « Pour ».

Au lycée, n’importe quel cryptarithme peut être abordé : avec Python, il est en effet aisé d’imbriquer des boucles « Pour » afin d’examiner toutes les possibilités et les élèves ont aussi plus d’expérience en codage. Le célèbre SEND + MORE = MONEY, qui comporte 8 lettres à découvrir, peut conduire à s’intéresser au temps d’exécution des programmes.

Sitographie

Proposée par Pierre Legrand :

  1. recreomath.qc.ca/r_crypt_c.htm. Ce site donne cent cryptarithmes additifs faciles. Un seul défaut : la plupart des problèmes ont plusieurs solutions.
  2. cryptarithms.awardspace.us/puzzles.html. Nettement plus ambitieux que le précédent. Les réponses sont données tout à la fin, mais sans justification.
  3. tkcs-collins.com/truman/alphamet/alphamet.shtml. Ce site donne plusieurs centaines de cryptarithmes additifs, avec une indication sur la difficulté (note de 1 à 5 dans le sens croissant). Les réponses sont données par un puzzle solver, mais pas le raisonnement.

Proposée par le comité de rédaction :

  1. http://graner.net/nicolas/nombres/crypt.php. Ce site propose un solveur de cryptarithmes écrit en perl et des compléments. Il permet également d’illustrer la partie programmation de résolution de cryptarithmes. Les cryptarithmes proposés peuvent bien entendu être plus complexes à résoudre que les exemples présents dans cet article ou encore dans les précédents sites.