1. Rappels sur les Systèmes à Base de Connaissances

lire n
s <- 0
pour i variant de 1 à n
  s <- s + i
finpour
imprimer s

lire n
imprimer (n * (n + 1) / 2)

  S E N D
  M O R E
---------
M O N E Y

• Je commence par ré-écrire le problème :

  D + E = Y + 10r1
  r1 + N + R = E + 10r2
  r2 + E + O = N + 10r3
  r3 + S + M = O + 10r4
  r4 = M
  S # 0
  M # 0
  

• Je considère l'équation la plus contrainte, r4 = M. Je sais que M ne peut pas être nul, mais ça ne me suffit pas.
• Je démontre un lemme : une retenue ne peut être égale qu'à 0 ou 1.
• Donc M = 1, et r4 = 1.
• Je propage :

  D + E = Y + 10r1
  r1 + N + R = E + 10r2
  r2 + E + O = N + 10r3
  r3 + S + M = O + 10*1
  r4 = M
  M = 1
  r4 = 1
  S # 0
  M # 0
  

• Je nettoie :

  D + E = Y + 10r1
  r1 + N + R = E + 10r2
  r2 + E + O = N + 10r3
  r3 + S = O + 9
  M = 1
  S # 0
  

• Je prends l'équation la plus contrainte, r3 + S = O + 9. r3 + S vaut au maximum 10, O ne peut pas valoir 1 (valeur déjà prise par M), donc O = 0.
• Je propage et je nettoie :

  D + E = Y + 10r1
  r1 + N + R = E + 10r2
  r2 + E = N + 10r3
  r3 + S = 9
  O = 0
  M = 1
  

• De deux choses l'une : r3 = 0 et S = 9, ou r3 = 1 et S = 8. Mais si je commence comme ça, je vais me retrouver avec un processus combinatoire. Donc je refuse cette solution de facilité. Je regarde l'équation r2 + E = N + 10r3.
• r2 + E vaut au plus 10, et N ne peut valoir 0. Donc r3 = 0, et S = 9.
• Je propage et je nettoie :

  D + E = Y + 10r1
  r1 + N + R = E + 10r2
  r2 + E = N 
  S = 9
  O = 0
  M = 1
  

• Puisque je cherche une bijection, je ne peux pas avoir E = N, donc r2 =1.

  D + E = Y + 10r1
  r1 + N + R = E + 10
  1 + E = N 
  S = 9
  O = 0
  M = 1
  

• Je considère le couple d'équations 1 + E = N et r1 + N + R = E + 10. Je peux ré-écrire :

  r1 + 1 + E + R = E + 10, ou
  r1 + R = 9
  

  R ne peut pas valoir 9 (valeur de S), donc R = 8 et r1 = 1.
• Je propage et je nettoie :

  D + E = Y + 10
  1 + E = N
  R = 8 
  S = 9
  O = 0
  M = 1
  

• Arrivé là, je ne vois plus d'astuce. Je vais raisonner, non plus sur le problème, mais sur moi : si je m'obstine à ne pas vouloir faire de combinatoire, peut-être ne trouverai-je jamais la solution ; par contre, si j'accepte de faire un petit peu de combinatoire, je trouverai la solution en au plus 4⁶ essais (il me reste 4 inconnues, prenant leurs valeurs dans [2 3 4 5 6 7]).
• Allons y, mais astucieusement. Y + 10 est au moins égal à 12. N et E sont très fortement liés. De deux choses l'une : soit D < E, soit N < D.
• Premier cas : puisque je veux au moins 12, commençons par les plus grandes valeurs possibles : N = 7, E = 6, D = 5 ; cela fait D + E = 11, insuffisant ; inutile d'essayer des valeurs plus petites. La moitié de la combinatoire est déjà éliminée.
• Reste l'hypothèse D = 7, N = 6, E = 5. Ca marche. Mais c'est limite (12), donc inutile d'essayer d'autres cas.