Rutschpartien

01.12.2023, 13:07

Finn_

Rutschpartien

Wir schreiben das Jahr 2050. Zur Bewältigung der Klimakrise wurde am Sösestausee im Harz vor einigen Jahren ein neues Kernkraftwerk in Betrieb genommen, dessen Abwärme nun ein Geflecht künstlicher Onsen speist. Herzstück dieser Urlaubsorte ist ein an jedem Tag des Jahres geöffnetes Erlebnisbad mit sieben großen Türmen, zwischen denen sich Wasserrutschen befinden.

Die 16 Rutschen verbinden die Türme folgendermaßen:

zwei von Turm 1 zu Turm 3;
jeweils eine von Turm 1 zu Turm 2, 4;
jeweils eine von Turm 2 zu Turm 3, 5;
jeweils eine von Turm 3 zu Turm 2, 4;
jeweils eine von Turm 4 zu Turm 1, 5, 6, 7;
eine von Turm 5 zu Turm 2;
jeweils eine von Turm 6 zu Turm 4, 7;
eine von Turm 7 zu Turm 1.

Eine kleine Gruppe Göttinger Studenten wollte sich nie von den Bädern bezirzen lassen, erhielt dann aber Jahreskarten geschenkt. Um jeden Tag anders zu erleben, wollen sie unterschiedliche Routen wählen. Start- und Zielturm gelten hierbei als unveränderliche Treffpunkte; ebenso soll die Anzahl der Rutschpartien stets dieselbe sein. Wie müssen diese Parameter gewählt werden, um nicht weniger und nicht mehr Routen zu erhalten als das Jahr Tage hat?

01.12.2023, 14:39

Finn_

Auf diesen Beitrag antworten »

[attach]57376[/attach]
Erlebnisbad Sösestausee. Historische Ansicht vor Fertigung der letzten Ausbaustufe.

06.12.2023, 09:27

Finn_

Auf diesen Beitrag antworten »

Algorithmische Bewältigung des Problems via Traversierung des gerichteten Graphen. Der Algorithmus ist allgemein gehalten. Zur Berücksichtigung der doppelten Kante von Turm 1 zu Turm 3 dürfen Kanten hierbei ein Gewicht bekommen, das als Multiplikator wirkt.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:

# Nachbarknoten von x und dessen Gewicht
def adjacent(graph, x):
    for y in graph[x]:
        yield y if isinstance(y, tuple) else (y, 1)

# Rekursive Formulierung der Traversierung, listet die Knoten auf,
# die von node aus in length Schritten erreicht werden. Hierbei
# akkumuliert multi das Produkt der Gewichte.
def traverse(graph, node, length, multi = 1):
    if length == 0:
        yield (node, multi)
    else:
        for (x, w) in adjacent(graph, node):
            yield from traverse(graph, x, length - 1, multi*w)

# Es ist acc ein Wörterbuch von Akkumulatoren, das zu 
# jedem Knoten node die Zahl der Pfade von start nach
# node Zählt.
def count_paths(graph, start, length):
    acc = {}
    for (node, count) in traverse(graph, start, length):
        if not node in acc:
            acc[node] = count
        else:
            acc[node] += count
    return acc

G = {
    1: [(3, 2), 2, 4], 2: [3, 5], 3: [2, 4],
    4: [1, 5, 6, 7], 5: [2], 6: [4, 7], 7: [1]
}

template = "Von Turm {} zu Turm {} in {} Rutschpartien."
for length in range(1, 10):
    for start in range(1, 8):
        for (end, count) in count_paths(G, start, length).items():
            if count == 365:
                print(template.format(start, end, length))

06.12.2023, 11:07

Finn_

Auf diesen Beitrag antworten »

Es geht aber auch eleganter hinsichtlich der Zeitkomplexität.

Satz. Ist $\begin{eqnarray*} A \end{eqnarray*}$ die Adjazenzmatrix des Graphen, so ist $\begin{eqnarray*} (A^n)_{ij} \end{eqnarray*}$ die Zahl der Pfade, die in $\begin{eqnarray*} n \end{eqnarray*}$ Schritten vom Knoten $\begin{eqnarray*} i \end{eqnarray*}$ zum Knoten $\begin{eqnarray*} j \end{eqnarray*}$ führen. Bei mehrfachen Kanten steht in der Adjazenzmatrix das Gewicht.

Beweis. Induktion über $\begin{eqnarray*} n \end{eqnarray*}$ . Der Induktionsanfang in $\begin{eqnarray*} n=1 \end{eqnarray*}$ entspricht genau der Definition der Adjazenzmatrix. Tatsächlich gilt die Aussage bereits für $\begin{eqnarray*} n=0 \end{eqnarray*}$ . Im Induktionsschritt sei die Aussage für $\begin{eqnarray*} n-1 \end{eqnarray*}$ vorausgesetzt. Der Zielknoten $\begin{eqnarray*} j \end{eqnarray*}$ ist unter Umständen in einem Schritt von $\begin{eqnarray*} k \end{eqnarray*}$ aus erreichbar, je nach Eintrag $\begin{eqnarray*} A_{kj}. \end{eqnarray*}$ Die Zahl der Pfade in $\begin{eqnarray*} n-1 \end{eqnarray*}$ Schritten von Startknoten $\begin{eqnarray*} i \end{eqnarray*}$ nach $\begin{eqnarray*} k \end{eqnarray*}$ ist $\begin{eqnarray*} (A^{n-1})_{ik}. \end{eqnarray*}$ Die Zahl der Pfade von $\begin{eqnarray*} i \end{eqnarray*}$ nach $\begin{eqnarray*} j \end{eqnarray*}$ in $\begin{eqnarray*} n \end{eqnarray*}$ Schritten ist demzufolge die Summe

$\begin{eqnarray*} \textstyle\sum_k (A^{n-1})_{ik} A_{kj} = (A^{n-1}A)_{ij} = (A^n)_{ij}. \end{eqnarray*}$ q.e.d.

Mir erscheint es fast absurd, dass ein, zumindest äußerlich, kompliziertes kombinatorisches Problem so einer einfachen Rechenregel genügt, die man dazu noch per Katzensprungbeweis geschenkt bekommt.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:

class Matrix:
    def __init__(self, a, dim = None):
        if dim != None:
            self.dim = dim
            self.a = a
        else:
            self.dim = (len(a), len(a[0]))
            self.a = [x for v in a for x in v]
    def __str__(self):
        n = self.dim[1]
        l = ["[{}]".format(", ".join(str(x) for x in self.a[k:k+n]))
            for k in range(0, len(self.a), n)]
        return "matrix(\n    {}\n)".format(",\n    ".join(l))
    def __mul__(self, rhs):
        assert self.dim[1] == rhs.dim[0]
        (m, p) = self.dim; n = rhs.dim[1]
        a = [sum(self.a[i*p + k]*rhs.a[k*n + j] for k in range(p))
            for i in range(m) for j in range(n)]
        return Matrix(a, (m, n))
    def __pow__(self, n):
        assert isinstance(n, int) and n >= 0
        a = self; acc = identity(self.dim[0])
        while True:
            if n%2 != 0: acc *= a
            if n == 0: return acc
            a *= a; n //= 2
    def __getitem__(self, t):
        return self.a[self.dim[1]*t[0] + t[1]]

def matrix(*a):
    return Matrix(a)

def identity(n):
    a = [1 if i == j else 0 for i in range(n) for j in range(n)]
    return Matrix(a, (n, n))

A = matrix(
    [0, 1, 2, 1, 0, 0, 0],
    [0, 0, 1, 0, 1, 0, 0],
    [0, 1, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 1, 1, 1],
    [0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0]
)

print("A**9 =", A**9)

template = "Von Turm {} zu Turm {} in {} Rutschpartien."
for n in range(1, 20):
    B = A**n
    for i in range(0, 7):
        for j in range(0, 7):
            if B[i, j] == 365:
                print(template.format(i + 1, j + 1, n))

Streng genommen muss man noch bestätigen, dass zu allen $\begin{eqnarray*} i,j \end{eqnarray*}$ die Folge $\begin{eqnarray*} n\mapsto (A^n)_{ij} \end{eqnarray*}$ für diese Matrix $\begin{eqnarray*} A \end{eqnarray*}$ zumindest ab $\begin{eqnarray*} n=20 \end{eqnarray*}$ durch 366 nach unten beschränkt ist.

08.12.2023, 15:27

Gualtiero

Auf diesen Beitrag antworten »

Auf jeden Fall eine schöne Aufgabe!
Obwohl ich ziemlich bald, nachdem ich ein wenig über meiner Schnellskizze sinniert hatte, die Hoffnung aufgegeben habe, dieses Problem durch händisches Abzählen lösen zu können. 365 Routen mit jeweils der gleichen Anzahl Rutschpartien!

[attach]57395[/attach]

Nur die Bedeutung der zweifachen Verbindung von T1 zu T3 habe ich richtig erkannt. Dadurch verdoppelt sich die Anzahl jener Routen, die Rutschpartie B enthalten, da diese ja durch C ersetzt werden kann.

Vielleicht werde ich meine Programmierkenntnisse auffrischen und meinen uralten C/C++ Compiler wieder mal anwerfen.

08.12.2023, 16:03

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Gualtiero
Nur die Bedeutung der zweifachen Verbindung von T1 zu T3 habe ich richtig erkannt. Dadurch verdoppelt sich die Anzahl jener Routen, die Rutschpartie B enthalten, da diese ja durch C ersetzt werden kann.

Naja, es werden dadurch auch Touren möglich, die mit nur einer Rutsche 1->3 gar nicht möglich wären. Zumindest (und so habe ich das verstanden), wenn pro Tour jede Rutsche maximal einmal benutzt werden darf.

08.12.2023, 17:22

Finn_

Auf diesen Beitrag antworten »

Rutschen sollen pro Tour mehrfach benutzt werden dürfen, nur der Weg als Ganzheit muss unterschiedlich sein. Man darf sich dies zum Beispiel so vorstellen, dass eine Warmwasserrutsche im Anschluss an eine Kaltwasserrutsche anders erlebt wird als nach dem Beginn der Tour oder einer anderen Warmwasserrutsche.

Beispiel. Linker Graph sei {(1, 2), (1, 3), (2, 4), (3, 4), (4, 1)}, der rechte gleichermaßen, aber (1, 2) eine Doppelkante.

[attach]57396[/attach]

Wege von 1 zu 2 der Länge 4 sind im linken Graph [1, 2, 4, 1, 2], [1, 3, 4, 1, 2], also 2 Wege. Im rechten Graph sind es vier unterschiedliche Wege [1, 2, 4, 1, 2] und zwei unterschiedliche Wege [1, 3, 4, 1, 2], also 6 Wege.

Neue Frage »

Antworten »

Rutschpartien

Verwandte Themen