Neue Bahnhöfe

In einem kleinen Land werden auf jedem Bahnhof Fahrkarten zu jedem anderen Bahnhof verkauft. Dann wird das Streckennetz erweitert und 34 neue Fahrkartenarten kommen hinzu. Wie viele Bahnhöfe gibt es nun?

Da es nicht viele Möglichkeiten für die Antwort gibt, löst das folgende Programm das Rätsel durch Ausprobieren aller Möglichkeiten.

Die Funktion fahrkarten berechnet die Zahl der Fahrkartenarten für eine gegebene Zahl n von Bahnhöfen.

(defproc fahrkarten (n)
  (* n (- n 1)))

Die Funktion fahrkarten-differenz rechnet aus, wie viele Fahrkartenarten hinzukommen, wenn die Zahl der Bahnhöfe von m auf n erhöht wird.

(defproc fahrkarten-differenz (n m)
  (- (fahrkarten n)
     (fahrkarten m)))

Die Funktion suche-fahrkarten-paare liefert eine Liste von Zahlenpaaren n und m, für die die Zahl der hinzukommenden Fahrkartenarten gleich der gesuchten Differenz ist. Die Paare werden aus der Liste der Kandidaten herausgefiltert.

(defproc suche-fahrkarten-paare (differenz kandidaten-paare)
  (select-if
    (lambda (paar) (= differenz (fahrkarten-differenz (first paar) (second paar))))
    kandidaten-paare))

Die Funktion paare-bis liefert eine Liste von Zahlenpaaren n und m. Dabei ist n kleiner oder gleich dem angegebenen Limit und n ist größer als m und beide sind ganze Zahlen und größer als Null.

(defproc paare-bis (limit)
  (select-if
    (lambda (paar) (> (first paar) (second paar)))
    (cartesian-product
      (range 2 (+ 1 limit))
      (range 1 limit))))

Die Funktion suche-fahrkarten-paare-bis kombiniert paare-bis und suche-fahrkarten-paare. Hier werden durch einen Aufruf von paare-bis erst alle Möglichkeiten erzeugt und dann mit einem Aufruf von suche-fahrkarten-paare ausprobiert.

(defproc suche-fahrkarten-paare-bis (differenz limit)
  (suche-fahrkarten-paare differenz (paare-bis limit)))

Diese letzte Funktion kann zum Lösen des Rätsels benutzt werden.

> (suche-fahrkarten-paare-bis 34 18)
((10 8) (18 17))

Es gibt also zwei Lösungen für das Rätsel: Entweder gibt es nach der Erweiterung des Streckennetzes 10 Bahnhöfe (und vor der Erweiterung gab es 8) oder es gibt danach 18 Bahnhöfe (und es kam einer hinzu).

Quelle
Richard Zehl
"Denken mit Spaß"

Link
http://www.spiegel.de/wissenschaft/mensch/wie-viele-neue-bahnhoefe-gibt-es-raetsel-der-woche-a-1226779.html


fahrkarten.sheet.xml