Möglichkeiten, bestimmte Zahlen zu bestimmten Anforderungen aufzuschreiben

Question

Man soll die natürlichen Zahlen von 1 bis 15 so in einer Reihe hintereinander aufschreiben, dass jede der 15 zählen nur einmal vorkommt und die Summe je zweier benachbarter Zahlen eine Quadratzahl ist. Wie viele Möglichkeiten gibt es (aus matheolympiade von letztem jahr)

Answer 1

Schreibt man zunächst für jede der Zahlen 1 bis 15 ihre möglichen Nachfolger auf, erhält man folgende Tabelle

1 - 3, 8, 15

2 - 7, 14

3 - 1, 6, 13

4 - 5, 12

5 - 4, 11

6 - 3, 10

7 - 2, 9

8 -1

9 - 7

10 - 6, 15

11 - 5, 14

12 - 4, 13

13 - 3, 12

14 - 2, 11

15 - 1, 10

Erstellt man daraus einen Graphen, dann sieht der etwa so aus:

Man erkennt sehr schön, den Zyklus 1, 3, 6, 10, 15, aber auch, dass nur die Zahlen 8 bzw, 9 für Anfang und Ende der Kette in Frage kommen. Schaut man etwas genauer hin, dann erkennt man, dass es nur zwei Wege gibt, alle Zahlen genau einmal zu betreten, nämlich:

8, 1, 15, 10, 6, 3, 13, 12, 4, 5,11,14, 2, 7, 9

sowie den entsprechenden Rückweg.