Send More Money durch Logik

Man kann das „Send More Money“-Problem, das ich in dem Artikel „Send More Money in PHP programmiert“ per Computer-Programm gelöst habe, auch durch logische Überlegung zu einer Lösung bringen.

Zur Erinnerung:

 SEND
+MORE
-----
MONEY
=====


soll eine sinnvolle Addition ergeben, wenn man jeden Buchstaben so durch eine Ziffer ersetzt, dass verschiedene Buchstaben auch verschiedene Ziffern repräsentieren.

Definiert wird, dass keine Zahl mit einer Null beginnen darf. Daraus folgt: S ungleich 0, M ungleich 0.

Bei allen Berechnungen darf man nie aus den Augen verlieren, dass bei der Addition zweier einstelliger Zahlen eine Summe > 10 herauskommen kann, also ein Übertrag, der bei der nächsthöheren Stelle berücksichtigt werden muss.

Wir haben also folgende Teil-Lösung:

 SEND   SEND
+1ORE  +MORE
-----  -----
1ONEY  MONEY
=====  =====


Da M = 1 ist, muss bei der Addition der Tausender-Stellen ein Übertrag entstanden sein. Es gilt also: S + 1 > 9. S kann also 8 oder 9 sein.

Nehmen wir einmal S = 8 an, dann wäre die Summe von S + M:
1. Ohne Übertrag: 8 + 1 = 9
2. Mit Übertrag 8 + 1 + 1 = 10

Wenn S = 9 ist, dann gilt:
1. Ohne Übertrag: 9 + 1 = 10
2. Mit Übertrag: 9 + 1 + 1 = 11

Die Summe kann nicht 9 sein, weil für die Zehntausenderstelle ein Übertrag benötigt wird, um M zu erhalten.
Die Summe kann auch nicht 11 sein, da dann die Buchstaben M und O gleich wären.

Es kann also S = 9 ohne Übertrag oder S = 8 mit Übertrag richtig sein. Das stellen wir zurück. In jedem Fall ist die Summe 10 und damit der Buchstabe O = 0.

Es ergibt sich folgende neue Teil-Lösung:

 SEND   SEND
+10RE  +MORE
-----  -----
10NEY  MONEY
=====  =====


Weil E + 0 = N an der Hunderter-Stelle zu berechnen ist, E und N aber verschieden sein müssen, steht fest, das die Zehner-Stellen einen Übertrag erzeugt haben. Außerdem können wir sagen: N = E + 1. Damit N (als Summe der Hunderter-Stellen) einen Übertrag für die Tausender-Stellen erzeugen kann (wir wissen aber nicht, ob das tatsächlich der Fall ist!), muss N > 9 sein, was aber nur der Fall ist, wenn E = 9 ist. Das wiederum führt zu einer Summe E + O + Übertrag = 9 + 0 + 1 = 10. Damit wäre N = 0. Die Null ist aber bereits dem O zugewiesen. Ein Übertrag für die Tausender-Stelle ist also nicht möglich. Daraus ergibt sich, dass S (siehe oben!) 9 sein muss.

Es ergibt sich folgende neue Teil-Lösung:

 9END   SEND
+10RE  +MORE
-----  -----
10NEY  MONEY
=====  =====


Nun wird es komplizierter.

Schauen wir uns einmal die Zehner-Stellen an: N + R = E. Wir wissen, dass die Hunderter-Stellen einen Übertrag brauchen, also gilt N + R = E + 10. Wir wissen von weiter oben auch, dass N = E + 1. Außerdem kann von den Einer-Stellen ein Übertrag vorhanden sein.

Setzen wir nun (N = E + 1) in den ersten Term ein, ergibt sich: (E + 1) + R = E + 10. Durch Termumformungen ergibt sich R = 9. Dies bedeutet, dass wir entweder R = 8 mit Übertrag aus den Einer-Stellen oder R = 9 ohne Übertrag aus den Zehner-Stellen haben. Die 9 ist allerdings bereits an den Buchstaben S vergeben. Es bleibt R = 8 und ein Übertrag aus den Einer-Stellen.

Neue Teil-Lösung:

 9END   SEND
+108E  +MORE
-----  -----
10NEY  MONEY
=====  =====


Nun schauen wir uns die letzten Stellen an: Y = D + E. Und wir müssen einen Übertrag für die Zehner-Stellen erzeugen. D + E = Y +10. Auch hier setzen wir wieder (N = E + 1) ein und erhalten: D + (N – 1) = Y + 10 oder D + N = Y +11.

Was hilft uns das weiter?

D + N muss Y + 11 ergeben. Die Ziffern 0, 1, 8 und 9 stehen nicht mehr zur Verfügung. Y muss also auf jeden Fall eine 2 oder größer (maximal 7) sein, was dazu führt, dass Y + 11 mindestens 13 ist. Wenn man sich alle möglichen Summanden-Paarungen für D und N ansieht, die 13 oder mehr ergeben, findet man nur genau drei Ergebnisse:

1. D = 7 und N = 6
2. D = 6 und N = 7
3. D = 7 und N = 7

Die 3. Lösung ist ungültig, weil zwei verschiedene Buchstaben denselben Wert annehmen würden.

Bei den Lösungen 1. und 2. ergibt sich als Summe von D und N jeweils 13. Da D + N = Y + 11 ist, muss Y = 2 sein.

Wieder eine Zwischen-Lösung:

 9END   SEND
+108E  +MORE
-----  -----
10NE2  MONEY
=====  =====


Wir wissen bereits, dass D und N jeweils entweder 6 oder 7 sind. Nehmen wir also wieder unseren Term N = E + 1. (Der ist offensichtlich für alles gut! 🙂 )

Und setzen ein:
1. 6 = E + 1 => E = 5
2. 7 = E + 1 => E = 6

Für Fall 1. gilt: N = 6, D = 7, E = 5
Für Fall 2. gilt: N = 7, D = 6, E = 6

Jetzt erkennt man sofort, das bei Fall 2 zwei verschiedene Buchstaben den gleichen Wert annehmen, was nicht erlaubt ist. Die einzige richtige Lösung ist also Fall 1: N = 6, D = 7, E = 5. Ups … alle drei fehlenden Buchstaben auf einen Schlag!

Die endgültige Lösung ist also:

 9567   SEND
+1085  +MORE
-----  -----
10652  MONEY
=====  =====


Einfacher und schneller findet man die Lösung natürlich durch Aufruf meines PHP-Skripts.