Cryptarithme

Un cryptarithme est une chaîne d'opérations où chaque lettre différente désigne un chiffre différent. Par exemple, supposons que nous ayons

  ABC
+ BBB
-----
  345

Après quelques tâtonnements, on obtiendra A=1, B=2 et C=3. Par contre, pour des cryptarithmes plus complexes, il faut utiliser une démarche plus rigoureuse qui fait appel à la logique.

La démarche suivante pour trouver une solution est donnée à titre didactique. Elle offre un modèle de résolution sur lequel s'appuyer pour résoudre des problèmes semblables.

Trouver une solution

Plusieurs cryptarithmes n'ont qu'une seule solution, d'autres en présentent plusieurs.

  SEND
+ MORE
------
 MONEY

Avant de résoudre ce problème, il faut identifier le plus de contraintes possibles (plus il y en a, plus rapidement la solution apparaîtra) :

• Les chiffres possibles sont {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
• Tous les chiffres complètement à gauche de chaque nombre n'égalent jamais zéro. Donc, S doit être différent de zéro, tout comme M.
• Lorsque l'on additionne deux chiffres, il peut y avoir une retenue. Par exemple, 5 + 7 = 12, le 1 sera mis en retenue dans la colonne suivante.
• On additionne au plus deux chiffres à la fois. Il est donc impossible que la retenue soit plus grande que 1 (ex. : 8 + 9 = 17)
• Pour faciliter le travail, on indiquera les retenues par des lettres minuscules : a, b et c.
• Finalement, la lettre E revient le plus souvent. Cela servira probablement à accélérer la recherche vers la solution.

Nous sommes prêts à commencer.

  abc
  SEND
+ MORE
------
 MONEY

M est le dernier chiffre à la gauche de MONEY. Il est tentant de poser M=1 ou M=2, car la somme maximale est donnée par (8 + 9), qui égale 17. Pour qu'elle fasse au moins 20, il faudrait que a=3, ce qui est impossible ici. Donc, M=1.

Nous avons maintenant

  abc
  SEND
+ 1ORE
------
 1ONEY

Le 1 de MONEY provient de la retenue calculée à partir de (a + S + 1), ce qui amène trois additions possibles :

• Si a=0, nous avons (0 + 9 + 1)
• Si a=1,
  • nous avons (1 + 8 + 1)
  • nous avons aussi (1 + 9 + 1)

Supposons que a=0, nous avons alors

  0bc
  9END
+ 10RE
------
 10NEY

Cette hypothèse semble raisonnable, car (0 + 9 + 1) = 10 et (E+0) donne probablement un nombre plus petit que 10. Puisque E est différent de N, il faut donc que b=1.

  01c
  9END
+ 10RE
------
 10NEY

En inspectant rapidement la solution partielle, on voit que E se répète trois fois. C'est cette lettre qui, probablement, nous amènera le plus rapidement vers la solution, car si nous posons une valeur fausse pour elle, cela aura une incidence sur les trois nombres.

En se basant sur cette solution partielle, il faut que E soit différent de 0, 1 et 9 (car ils sont déjà pris).

Avec b=1, il faut que E soit différent de 8 car (1 + E + 0) = N, mais 9 est déjà pris. Donc, E vaut 2, 3, 4, 5, 6 ou 7.

Posons E=2, on a donc

  01c
  92ND
+ 10R2
------
 10N2Y

Par cette nouvelle addition, nous savons que N=3

  01c
  923D
+ 10R2
------
 1032Y

Est-il possible que (c + 3 + R) égale 12? Le chiffre 9 est déjà pris, ce qui exclut c=0. R=7 ne fonctionne pas, car (1 + 3 + 7) = 11 (le chiffre 1 est déjà pris). Dans ce cas de figure, il faut donc que R=8 et c=1.

  011
  923D
+ 1082
------
 1032Y

L'hypothèse E=2 amène une contradiction, car (D + 2) doit valoir au moins 10, alors que 8 et 9 sont déjà pris.

Posons E=3, on a donc

  01c
  93ND
+ 10R3
------
 10N3Y

Par cette nouvelle addition, nous savons que N=4.

  01c
  934D
+ 10R3
------
 1043Y

Est-il possible que (c + 4 + R) égale 13? Il y a deux possibilités :

• (1 + 4 + 8) = 13, ce qui oblige à poser D=9, mais il est déjà pris.
• (0 + 4 + 9) = 12, mais 9 est déja pris.

L'hypothèse E=3 amène une contradiction.

Posons E=4, on a donc

  01c
  94ND
+ 10R4
------
 10N4Y

Par cette nouvelle addition, nous savons que N=5.

  01c
  945D
+ 10R4
------
 1054Y

Est-il possible que (c + 5 + R) égale 14? Il y a deux possibilités :

• (1 + 5 + 8) = 14,
  • ce qui oblige à poser D=6 et amène Y=0, ce qui est impossible.
  • ce qui oblige à poser D=7 et amène Y=1, ce qui est impossible.

L'hypothèse E=4 amène une contradiction.

Posons E=5, on a donc

  01c
  95ND
+ 10R5
------
 10N5Y

Par cette nouvelle addition, nous savons que N=6.

  01c
  956D
+ 10R5
------
 1065Y

Est-il possible que (c + 6 + R) égale 15? Il y a une seule possibilité :

• (1 + 6 + 8) = 15, ce qui oblige à poser D=7 et amène Y=2.

  011
  9567
+ 1085
------
 10652

Le cryptarithme est résolu.

   SEND + MORE = MONEY
   9567 + 1085 = 10652

D'autres solutions ?

Y a-t-il d'autres solutions à ce cryptarithme?

Posons E=6, on a donc

  01c
  96ND
+ 10R6
------
 10N6Y

Par cette nouvelle addition, nous savons que N=7.

  01c
  967D
+ 10R6
------
 1076Y

Est-il possible que (c + 7 + R) égale 16? Il y a une seule possibilité :

• (1 + 7 + 8) = 16, ce qui oblige à poser D=5 et amène Y=1, ce qui est impossible.

Posons E=7, on a donc

  01c
  97ND
+ 10R7
------
 10N7Y

Par cette nouvelle addition, nous savons que N=8.

  01c
  978D
+ 10R7
------
 1087Y

Est-il possible que (c + 8 + R) égale 17? Les deux possibilités sont impossibles :

• (0 + 8 + 9) = 17, mais 9 est déjà pris.
• (1 + 8 + 8) = 17, mais 8 est déjà pris.

Nous avons épuisé toutes les possibilités. La solution trouvée plus haut est unique.