Lösungsbeschreibung des Preisrätsels vom Dezember 2017

Netzwerk-Varianten für die Verbindung der Ecken eines Würfels

1.) Bezeichnungen für Knoten und Kanten

Beschriftung der Knoten und Kanten

Bild 1

Die nebenstehende Abbildung dient zur Festlegung aller für die weiteren Schritte notwendigen Bezeichnungen.

Dabei sind die Eckpunkte des Würfels (Knoten des Netzwerks) mit den großen Buchstaben von A bis H benannte und die Kanten des Würfels (auch Kanten des Netzwerks) mit den Zahlen von 1 bis 12 beschriftet. Diese Festlegung ist absolut willkürlich und würde bei veränderter Festlegung keinen Einfluss auf die Ergebnisse für dieses Rätsel haben.

Das Koordinatensystem ist ebenfalls willkürlich und dient dazu, die Rotationen um verschiedene Achsen festzulegen.

Auch für Personen, die eine gute räumliche Vorstellung von rotierten Körpern haben, ist es fast unmöglich, dieses Rätsel ohne Rechnerunterstützung zu lösen. Deshalb wird hier auch sehr ausführlich der Weg der Programmierung beschrieben. Dazu wird der Code in der Programmiersprache PHP gezeigt, der auch in dieser Internetseite beim Aufruf serverseitig abläuft und alle Ergebnisse jeweils neu berechnet. Andere Programmiersprachen sind aber genauso geeignet.

2.) Anzahl aller Varianten

Die erste Frage kann noch mit einfacher Mathematik beantwortet werden. Es gib 12 Würfelkanten, denen 7 Netzwerkkanten in allen Variationen zugeordnet werden sollen. Dabei ist die Reihenfolge nicht von Bedeutung, denn es würde beim Austausch zweier Kanten trotzdem das gleiche Netzwerk entstehen. Zur Berechnung wird eine Formel aus der Kombinatorik verwendet: $$\rand{ \text{Anzahl aller Varianten}={n\choose k}={12\choose 7}= 792}$$

3.) allgemeiner Programmaufbau

Da nun klar ist, das mit einer recht großen Anzahl von Varianten begonnen werden muss, ist eine Vorgehensweise für das Aussortieren der Wiederholungen zu planen, die durch Drehungen des Würfels um alle seine Achsen sich ergeben und in der Zahl 792 enthalten sind. Es ist sinnvoll, eine erste Liste von der Länge 792 mit Zahlen zu füllen, die den jeweils einzigartigen Typ einer Variation kennzeichnet. Gleichzeitig wird eine zweite Liste aufgebaut, die die Eigenschaften dieser als verschieden von bisher gefundenen Varianten sammelt. Dabei entsteht automatisch die Antwort auf die zweite Frage, nämlich die Länge dieser zweiten Liste. Abschließend kann dann aus den abgespeicherten Eigenschaften die Antwort zur dritten Frage abgeleitet werden.

4.) das Durchlaufen der ersten Liste

Es macht keinen Sinn, die erste Liste mit den Zahlen von 1 bis 792 zu durchlaufen, denn diese Zahlen stehen in keiner erkennbaren Verbindung zu der Art des Netzwerks. An einem sehr kleinen Beispiel soll gezeigt werden, wie die Vorgehensweise stattdessen geplant ist.

Die folgende Tabelle zeigt die Variationen, wenn $n=5$ und $k=3$ ist. Das ergibt ${5\choose 3}=10$ Varianten. Der Schlüssel ist der assoziative Index für die Liste und entsteht aus den Kanten des Netzwerks.

lfd. NrVariationSchlüssel
11,2,3123
21,2,4124
31,2,5125
41,3,4134
51,3,5135
61,4,5145
72,3,4234
82,3,5235
92,4,5245
103,4,5345

Tabelle 1

Man sieht hier, wie sich die Variationen entwickeln. Die erste der drei Ziffern durchläuft die Werte von 1 bis 3, die zweite die Werte von 2 bis 4, die dritte von 3 bis 5, und das so, dass die jeweilige Ziffer immer größer als ihr linker Nachbar ist, also eine aufsteigend sortierte Reihenfolge der drei Ziffern. Das kann man mit dem folgenden Programmteil auch für $n=12$ und $k=7$ erreichen:

for ($a1=1;$a1<=6;$a1++)
{
    for ($a2=$a1+1;$a2<=7;$a2++)
    {
        for ($a3=$a2+1;$a3<=8;$a3++)
        {
            for ($a4=$a3+1;$a4<=9;$a4++)
            {
                for ($a5=$a4+1;$a5<=10;$a5++)
                {
                    for ($a6=$a5+1;$a6<=11;$a6++)
                    {
                        for ($a7=$a6+1;$a7<=12;$a7++)
                        {
                            $a=[$a1,$a2,$a3,$a4,$a5,$a6,$a7];
                            typ($a);
                        }
                    }
                }
            }
        }
    }
}

Programmcode 1

Man könnte auch zum gleichen Ergebnis gelangen, wenn man statt der sieben geschachtelten Schleifen eine einzige in einem Unterprogramm mit Abbruchkriterium einsetzen würde und dieses Unterprogramm sich selbst aufrufen lässt. Diese iterative Methode ist zwar eleganter und flexibler aber bei weitem nicht so übersichtlich.

5.) verschiedene Unterprogramme

In der Zeile 16 von Programmcode 1 befindet sich der Aufruf eines Unterprogramms, welches nacheinander mit den 792 Werten der Varianten versorgt wird. Darin wird dann auch der Schlüssel (wie in Tabelle 1) für den Zugriff auf die Elemente der ersten Liste (assoziatives Array: $liste[ ]) erzeugt.
Falls an dieser Stelle in der ersten Liste noch kein Eintrag existiert, wird die laufende Nummer für neue Varianten (Variable: $nummer) dort eingetragen (Programmcode 2 Zeile 16). Das geschieht aber nicht nur für eine Variante, sondern auch für alle $4\cdot 6=24$ (4 Himmelsrichtungen, 6 Grundseiten) durch Drehungen entstehende Varianten gleichen Typs, die im Unterprogramm in Zeile 12 von Programmcode 2 erzeugt werden.
In der zweiten Liste (Array: $typen[ ]) wird ein Eintrag dieses neuen Typs mit dem Schlüssel der laufenden Nummer und der Zusatzdimension "Kanten" vorgenommen. Ein weiterer Eintrag startet die Zählung dieses Typs mit dem Wert 1 in der Zusatzdimension "Zahlen". Anschließend wird die Nummer um eins erhöht.
Falls schon ein Eintrag in der ersten Liste vorliegt wird der Eintrag als Schlüssel für die zweite Liste benutzt, um dort die "Zahlen"-Dimension um eins zu erhöhen.

Dieser Weg scheint umständlich, aber ist sehr effektiv bei der Findung der tatsächlichen Zahlen für jeden Typ. Die 24 Einträge erzeugen nämlich nicht immer 24 neue Varianten eines Typs. Es werden teilweise schon erfolgte Einträge mit dem gleichen Wert überschrieben. Darum muss sich die gewählte Methode aber nicht kümmern, da sie von den Überschreibungen nichts sieht. Sie kommt erst später an die Speicherzellen und erhöht dann den Zählerstand nur einmal (Programmcode 2 Zeile 10).

function typ($a)
{
    global $liste;
    global $typen;
    global $nummer;

    $key = $a[0].$a[1].$a[2].$a[3].$a[4].$a[5].$a[6];
    if(array_key_exists ($key, $liste))
    {
        $typen[$liste[$key]]["zahlen"]++;
    }else{
        $g = gleiche($a);
        for($i=0; $i<24; $i++)
        {
            $key = $g[$i][0].$g[$i][1].$g[$i][2].$g[$i][3].$g[$i][4].$g[$i][5].$g[$i][6];
            $liste[$key] = $nummer;
        }
        $typen[$nummer]["kanten"] = $a;
        $typen[$nummer]["zahlen"] = 1;
        $nummer++;
    }
}

Programmcode 2


Wie im einzelnen die 24 gleichen, aber durch Drehungen unterschiedlich erscheinenden Varianten gefunden werden, wird im folgenden Unterprogramm gezeigt:

function gleiche($sample)
{
sort($sample);
$g[0] = $sample;
$g[1] = rotx($g[0]);
$g[2] = rotx($g[1]);
$g[3] = rotx($g[2]);

$g[4] = roty($g[0]);
$g[5] = rotx($g[4]);
$g[6] = rotx($g[5]);
$g[7] = rotx($g[6]);

$g[8] = roty($g[4]);
$g[9] = rotx($g[8]);
$g[10] = rotx($g[9]);
$g[11] = rotx($g[10]);

$g[12] = roty($g[8]);
$g[13] = rotx($g[12]);
$g[14] = rotx($g[13]);
$g[15] = rotx($g[14]);

$g[16] = rotz($g[0]);
$g[17] = rotx($g[16]);
$g[18] = rotx($g[17]);
$g[19] = rotx($g[18]);

$g[20] = rotz(rotz($g[16]));
$g[21] = rotx($g[20]);
$g[22] = rotx($g[21]);
$g[23] = rotx($g[22]);

return $g;
}

Programmcode 3

Dabei sind die Unterprogramme $\text{rotx()}$, $\text{roty()}$ und $\text{rotz()}$ Rotations-Tranformationen um die jeweilige x-, y- oder z-Achse. Die Tranformation $\text{\$trans} = [2,3,4,1,9,12,11,10,6,7,8,5]$ für eine 90°-Drehung um die x-Achse bedeutet ein Austausch der Kanten:

von123456789101112
nach234191211106785

was am Bild 1 nachzuvollziehen ist. Nach jeder Drehung müssen die Kanten in aufsteigender Reihenfolge sortiert werden, denn nur so findet man in der ersten Liste entsprechende Einträge.

function rotx($sample)     // rotiert 90° um x-Achse
{
    $trans = [2,3,4,1,9,12,11,10,6,7,8,5];
    for ($i=0; $i<count($sample); $i++)
    {
        $result[$i] = $trans[$sample[$i]-1];
    }
    sort($result);
    return $result;
}

function roty($sample)     // rotiert 90° um y-Achse
{
    $trans = [9,10,11,12,6,7,8,5,2,1,4,3];
    for ($i=0; $i<count($sample); $i++)
    {
        $result[$i] = $trans[$sample[$i]-1];
    }
    sort($result);
    return $result;
}

function rotz($sample)     // rotiert 90° um z-Achse
{
    $trans = [8,7,6,5,1,2,3,4,10,11,12,9];
    for ($i=0; $i<count($sample); $i++)
    {
        $result[$i] = $trans[$sample[$i]-1];
    }
    sort($result);
    return $result;
}

Programmcode 4

6.) Datenausgabe

Eigentlich ist schon fast alles fertig und versteckt sich nur in der zweiten Liste. Die Antwort auf die zweite Frage ist die Länge der zweiten Liste, was gleichbedeutend mit dem Wert von $nummer ist. $$\rand{ \text{Anzahl verschiedener Typen}=38 }$$
Eine vollständige Tabelle aller Typen und deren Eigenschaften ist für dieses Rätsel nicht verlangt, aber hier sinnvoll, um die Vorgehensweise zu erkennen.

Die Ausgabe dieser Daten bedeutet, dass man alle Typen der zweiten Liste durchläuft und die Inhalte zeilenweise ausgibt.
Währenddessen werden noch einige wichtige Aktionen durchgeführt, die die Eigenschaften des jeweiligen Netzwerks erforschen.

Es ist z.B. von Interesse, wie viele Kanten an einem Knoten zusammenkommen. Die Zahl ist im Bereich von 0 bis 3. Bei einem Knoten mit 0 Kanten ist klar, das er nicht vom Netzwerk erreicht wird, also es ein unvollständiges Netzwerk ist. Bei einem Knoten mit 3 Kanten ist es keinesfalls ein lineares, sondern ein verzweigtes Netzwerk. Ein unzusammenhängendes Netzwerk, welches zwar an jedem Knoten mindestens eine Kante hat, zerfällt aber in zwei Teile. Dies ist immer dann der Fall, wenn sich in einem Teil des Netzwerks ein Ring bildet. Der Ring bindet eine Kante mehr als erforderlich ein, die an anderer Stelle zur Anbindung fehlt.

Die obigen Eigenschaften sind also noch aus den bekannten Kanten auszufiltern.

Im Programm wird jeder Kante nach folgendem Prinzip eine Zahl zugeordnet:

//                   H G F E D C B A
$punkte = [ bindec('0000000001000100'), //  1
            bindec('0000000000010001'), //  2
            bindec('0001000100000000'), //  3
            bindec('0100010000000000'), //  4
            bindec('0000010000000100'), //  5
            bindec('0000000100000001'), //  6
            bindec('0001000000010000'), //  7
            bindec('0100000001000000'), //  8
            bindec('0000000000000101'), //  9
            bindec('0000000001010000'), // 10
            bindec('0101000000000000'), // 11
            bindec('0000010100000000'), // 12
    ];

Programmcode 5


Die Werte der Kanten sind zeilenweise gelistet, mit der Nummer der Kante als Kommentar rechts außen. Es handelt sich um eine Umwandlung eines Binär-Textes in eine Dezimalzahl. In der Kommentarzeile oben erkennt man die Buchstaben der Knoten. Für jeden Knoten sind 2 Bit reserviert, denn es werden, wie schon oben erwähnt, Zahlen von 0 bis 3 erwartet. Man kann anhand der Abbildung 1 das obige Muster mit den Beziehungen von Knoten und Kanten vergleichen. Z.B. sagt die erste Zeile aus, dass es sich um die Kante 1 handelt, mit den Endpunkten B und D, die jeweils durch eine 1 im Bitmuster gekennzeichnet sind.
Wenn man nun von jeder Kante eines Typs die obige Zahl ausliest und alle sieben addiert, erhält man ein Ergebnis, bei dem in jeweils 2 Bit die Zahl der Kanten am jeweiligen Knoten anliegen. Es muss keine Zuordnung zu bestimmten Knoten geben. Deshalb sind auch keine Rotationen zur Überprüfung erforderlich. Es kann beim durchsehen der Bits gleich ein passendes Ergebnis-Bit für eine Null und ein anderes für eine drei gesetzt werden. Hier folgt der Programmcode:

$kenn = 0;

    for($j=0; $j<7; $j++)
    {
        $kenn += $punkte[$typen[$i]["kanten"][$j]-1];
    }

    $bit = 0;

    for($j=0; $j<=7; $j++)
    {
        $k = $kenn % 4;
        $kenn = ($kenn - $k)/4;
        if($k==3) {$bit = $bit | 1;}
        if($k==0) {$bit = $bit | 2;}
    }

Programmcode 6

Damit ist die Information "unvollständig" und "verzweigt" für diesen Typ mit der laufenden Nummer $i bekannt und in der Variablen $bit zur späteren Auswertung abgelegt.

Die Erkennung von Ringen ist etwas schwieriger. Zunächst muss man erkennen, dass es nicht nur eine Sorte von Ringen gibt. Die einfachste Form ist der 4er-Ring, der eine Seite des Würfels umrahmt. Dieser kann natürlich auf jeder Würfelseite auftreten und muss erkannt werden. Eine zweite Form ist ein 6er-Ring, der zwei benachbarte Seiten des Würfels umrahmt. Auch hier gilt, das alle gedrehten Ringe dieser Art erkannt werden müssen. Zuletzt gibt es eine Variante des 6er-Rings. Er verbindet auf zwei Wegen mit jeweils drei Kanten zwei gegenüberliegende Knoten des Würfels.

Ein beliebiger Repräsentant jeder Form ist leicht zu finden. Die übrigen werden mit der bereits bekannten Methode von Unterprogramm $gleiche (Programmcode 3) erzeugt. Dann muss nur noch festgestellt werden, ob eines der vielen Ringmuster im jeweiligen Typ der zweiten Liste enthalten ist und wenn ja, dann muss ein weiteres Ergebnis-Bit dafür gesetzt werden. Hier folgt die Fortsetzung von Programmcode 6:

$a = $typen[$i]["kanten"];

    $b = [2,3,6,7];         // 4er-Ring
    $g = gleiche($b);
    if (test($a,$g)) {$bit = $bit | 4;}

    $b = [1,3,5,8,11,12];   // 6er-Ring
    $g = gleiche($b);
    if (test($a,$g)) {$bit = $bit | 4;}

    $b = [1,3,5,7,10,12];   // zweiter 6er-Ring
    $g = gleiche($b);
    if (test($a,$g)) {$bit = $bit | 4;}

    if(   $bit == 0                          ) { $kat[0]++; } // linear
    if( (($bit & 1) > 0) && (($bit & 4) == 0)) { $kat[1]++; } // verzweigt
    if(  ($bit & 2) > 0                      ) { $kat[2]++; } // unvollständig
    if( (($bit & 2) == 0) && (($bit & 4) > 0)) { $kat[3]++; } // geteilt

    $text="";
    if( $bit == 0 ) {$text .= "linear ";}
    if( ($bit & 1)) {$text .= "verzweigt ";}
    if( ($bit & 2)) {$text .= "unvollständig ";}
    if( ($bit & 4)) {$text .= "Ring";}

Programmcode 7

Wie im Programmcode 7 zu sehen ist, wird auch gleich eine Auswertung der drei Bits durchgeführt. In der Variablen $kat werden die zur jeweiligen Kategorie gehörigen Typen gezählt und damit die Antwort der dritten Frage vorbereitet.

Es fehlt im Programmcode noch das Unterprogramm $test

function test($sample,$g)
{
    $merk = FALSE;
    for($i=0; $i<count($g); $i++)
    {
        $zahl = 0;
        for($j=0; $j<count($g[0]); $j++)
        {
            if (in_array($g[$i][$j], $sample, TRUE)) {$zahl++;}
        }
        if($zahl==count($g[0])) {$merk = TRUE;}

    }
    return $merk;
}

Programmcode 8

Nun ist alles beisammen und die Ausgabe der zweiten Liste in Tabellenform mit den ermittelten Eigenschaften kann erfolgen.

TypAnzahlKanten$bit-Eigenschaftenschematische Darstellung
1241,2,3,4,5,6,7Ring
Klick auf eine der linken Zeilen erzeugt die Darstellung des zugehörigen Netzwerk-Typs

2241,2,3,4,5,6,9verzweigt
3241,2,3,4,5,6,10linear
4241,2,3,4,5,7,9verzweigt
5241,2,3,4,5,7,11verzweigt
6241,2,3,4,5,8,9verzweigt Ring
7241,2,3,4,5,8,10verzweigt Ring
8241,2,3,5,6,7,9verzweigt unvollständig Ring
9241,2,3,5,6,7,10verzweigt unvollständig Ring
10241,2,3,5,6,7,11verzweigt Ring
11241,2,3,5,6,7,12verzweigt unvollständig Ring
12121,2,3,5,6,8,9verzweigt
13241,2,3,5,6,8,10verzweigt
14121,2,3,5,6,8,11linear
15241,2,3,5,6,9,10verzweigt unvollständig Ring
16241,2,3,5,6,9,11verzweigt
17241,2,3,5,6,9,12verzweigt unvollständig Ring
18121,2,3,5,6,10,11linear
19241,2,3,5,6,10,12verzweigt unvollständig Ring
20241,2,3,5,6,11,12verzweigt
21241,2,3,5,7,8,9verzweigt
22121,2,3,5,7,8,10verzweigt
23121,2,3,5,7,8,12linear
24241,2,3,5,7,9,10verzweigt unvollständig Ring
25121,2,3,5,7,9,11verzweigt
26241,2,3,5,7,9,12verzweigt unvollständig Ring
27241,2,3,5,7,10,12verzweigt unvollständig Ring
28241,2,3,5,7,11,12verzweigt
29241,2,3,5,8,9,10verzweigt Ring
30241,2,3,5,8,9,12verzweigt
31241,2,3,5,8,10,12verzweigt
32121,2,3,5,8,11,12Ring
33121,2,3,6,7,9,10verzweigt unvollständig Ring
34241,2,3,6,7,9,12verzweigt unvollständig Ring
35241,2,3,6,7,10,12verzweigt unvollständig Ring
36241,2,3,6,8,9,12verzweigt
37121,2,3,6,8,10,12verzweigt
38121,2,3,7,8,9,12linear

Tabelle 2


Die Antworten auf die dritte Frage ist nun das Zählergebnis der entsprechenden Eigenschaften. $$\rand{\begin{align} \text{Anzahl linearer Netzwerke}&=5 \\ \text{Anzahl verzweigter Netzwerke}&=15 \\ \text{Anzahl geteilter Netzwerke}&=6 \\ \text{Anzahl unvollständiger Netzwerke}&=12\end{align}}$$



Diese Informationen wurden zusammengestellt von

Kurzbewertung dieser Information:
sehr gut gut befriedigend
ausreichend mangelhaft ungenügend