Re: Ein simples, schwieriges Matherätsel

Mark Dominus stellte in seinem Blog The Universe of Discourse dieses simple, doch nicht ganz einfache Rätsel: Verbinde die vier Zahlen 6, 6, 5, 2 in beliebiger Reihenfolge mit plus, minus, mal und/oder geteilt sowie gegebenenfalls Klammern so, dass sie 17 ergeben. Beispielsweise ist (6 − 2) × 6 − 5 = 19, gesucht ist aber eine Formel für 17.

Ich überlegte einige Zeit, ohne eine Lösung zu finden, und entschied mich dann dazu, ein Computerprogramm zu schreiben, welches das Problem knackt. Dass ich PHP als Programmiersprache wählte, hat keinen wichtigen Grund. Es war Bequemlichkeit – ich bin mit ihr am besten vertraut.

Programm zur Lösung

Schauen wir uns zuerst die vier Zahlen an. Im Allgemeinen gibt es n! Möglichkeiten, n Objekte nacheinander anzuordnen. Da allerdings zwei der vier Zahlen 6, 6, 5, 2 identisch sind, sind jeweils zwei der 4! = 24 Möglichkeiten ununterscheidbar und wir brauchen nur 12 Möglichkeiten zu betrachten. Das ist nicht viel Schreibarbeit, sodass ich alle möglichen Reihenfolgen per Hand notiert habe:

<?php

$zahlen = [
   [2, 5, 6, 6],
   [2, 6, 5, 6],
   [2, 6, 6, 5],
   [5, 2, 6, 6],
   [5, 6, 2, 6],
   [5, 6, 6, 2],
   [6, 2, 5, 6],
   [6, 2, 6, 5],
   [6, 5, 2, 6],
   [6, 5, 6, 2],
   [6, 6, 2, 5],
   [6, 6, 5, 2]
];

An drei Stellen, immer zwischen zwei Zahlen, steht das Symbol einer beliebigen der vier Grundrechenarten. Das ergibt 4³ = 64 Möglichkeiten, die Operatoren plus, minus, mal und geteilt zu kombinieren. 64 waren mir zu viel, um sie per Hand zu tippen, sodass ich all jene Kombinationen automatisch vorbereiten lies:

$operatoren = [];
foreach (['+', '-', '*', '/'] as $x) {
   foreach (['+', '-', '*', '/'] as $y) {
      foreach (['+', '-', '*', '/'] as $z) {
         $operatoren[] = [$x, $y, $z];
      }
   }
}

Zudem gibt es eine Reihe von Möglichkeiten, Klammern zu setzen. Diese elf habe ich wiederum per Hand notiert und hoffe, dabei keine vergessen zu haben. Im Folgenden symbolisiert %d stets eine Zahl und %s einen Operator. (Diese Darstellung ergibt sich aus den Anforderungen der PHP-Funktion sprintf.)

$klammern = [
   '%d %s %d %s %d %s %d',
   '(%d %s %d) %s %d %s %d',
   '%d %s (%d %s %d) %s %d',
   '%d %s %d %s (%d %s %d)',
   '(%d %s %d) %s (%d %s %d)',
   '(%d %s %d %s %d) %s %d',
   '%d %s (%d %s %d %s %d)',
   '((%d %s %d) %s %d) %s %d',
   '(%d %s (%d %s %d)) %s %d',
   '%d %s ((%d %s %d) %s %d)',
   '%d %s (%d %s (%d %s %d))'
];

Nun werden alle 12 Möglichkeiten, die Zahlen anzuordnen, jeweils mit allen 64 Möglichkeiten, die Operatoren zu wählen, jeweils mit den 11 Möglichkeiten, Klammern zu setzen, kombiniert und das Ergebnis ausgewertet. Von den insgesamt 12 × 64 × 11 = 8448 Kombinationen werden nur jene mit dem Wert 17 ausgegeben.

header ('Content-type: text/plain');

foreach ($zahlen as list ($a, $b, $c, $d)) {
   foreach ($operatoren as list ($x, $y, $z)) {
      foreach ($klammern as $vorlage) {
         $term = sprintf ($vorlage, $a, $x, $b, $y, $c, $z, $d);
         if (17 == @eval ("return $term;")) {
            print ("$term = 17\n");
         }
      }
   }
}

Ergebnis

Die Ausgabe des Programmes sieht wie folgt aus – mathematisch sind all jene Formeln äquivalent, sodass wir beispielhaft (2 + 5 ∕ 6) × 6 = 17 als Lösung herausgreifen können:

(2 + 5 / 6) * 6 = 17
(2 + (5 / 6)) * 6 = 17
(5 / 6 + 2) * 6 = 17
((5 / 6) + 2) * 6 = 17
6 * (2 + 5 / 6) = 17
6 * (2 + (5 / 6)) = 17
6 * (5 / 6 + 2) = 17
6 * ((5 / 6) + 2) = 17

Anmerkung

Das Programm erstellt auch Terme, in denen die nicht definierte Division durch null vorkommt, zum Beispiel 2 + 5 ∕ (6 − 6). Eine Fehlermeldung in jenen Fällen wird mit dem Zeichen @ vor eval im Programm unterdrückt. Beim Anschauen der Ausgabe des Programmes muss aber darauf geachtet werden, dass keine Division durch null unter den Ergebnissen auftaucht. Dies habe ich beachtet.