Rätsel der Woche Epidemie auf dem Schachbrett
Die Ausbreitung von Krankheitserregern lässt sich auf verschiedene Arten modellieren – zum Beispiel mit Differenzialgleichungen. Eine andere, wesentlich anschaulichere Methode sind sogenannte zelluläre Automaten .
Um die soll es im folgenden Rätsel gehen. Lassen Sie sich von dem Begriff zellulärer Automat nicht abschrecken. Das Prinzip dahinter ist sehr einfach.
Wir modellieren die Ausbreitung eines Virus auf den 64 Feldern eines Schachbretts. Ein Feld ist entweder infiziert oder nicht infiziert. Das Virus breitet sich von Feld zu Feld immer weiter aus.
Für die Infektion von Feldern gilt folgende Regel: Ein bislang nicht infiziertes Feld wird infiziert, wenn mindestens zwei seiner Nachbarfelder bereits infiziert sind. In der folgenden Abbildung sind infizierte Felder grün markiert und die von ihnen neu infizierten Felder rot.
Als Nachbarfelder gelten nur direkt benachbarte Felder, die senkrecht oder waagerecht angrenzen. Eine Ansteckung über diagonal benachbarte Felder ist nicht möglich. Ein Feld kann deshalb höchstens vier Nachbarfelder haben, bei denen es sich anstecken kann.
Finden Sie die kleinstmögliche Anzahl infizierter Felder, die dazu führt, dass schließlich alle Felder des Schachbretts infiziert sind.
Zur Lösung bitte nach unten scrollen!
Michael Niestedt/ DER SPIEGEL
Lösung
Es reichen acht infizierte Felder – und zwar die acht Felder, die eine Diagonale quer über das Brett bilden. Bei dieser Anfangskonstellation sind sämtliche Felder nach sieben Schritten infiziert.
Wir müssen aber noch beweisen, dass es sich dabei auch um die kleinstmögliche Anzahl von Feldern zum Start der Epidemie handelt. Das gelingt mit einem raffinierten Trick, auf den ich selbst nicht gekommen bin.
Wir schauen uns den Umfang aller infizierten Flächen auf dem Schachbrett an. Mit Umfang ist die Länge der Außengrenzen gemeint. Eine isolierte, infizierte Zelle hat einen Umfang von vier, wenn ein Feld eine Seitenlänge von 1 hat. Zwei direkt aneinandergrenzende infizierte Zellen haben einen Umfang von sechs, sofern sie senkrecht oder waagerecht keine weiteren infizierten Nachbarn haben.
Von einem Infektionsschritt zum nächsten kann dieser Umfang über alle infizierten Flächen nicht zunehmen.
Warum nicht? Wir müssen dabei zwei Fälle unterscheiden. Hat ein nicht infiziertes Feld zwei infizierte Nachbarn, ändert sich der Umfang der infizierten Flächen durch die Infektion dieses Feldes nicht.
Ist ein bislang nicht infiziertes Feld hingegen von mehr als zwei infizierten Feldern umgeben, wird der Umfang über alle infizierten Flächen durch die Infektion kleiner.
Ganz zum Schluss sollen alle 64 Felder infiziert sein. Der Umfang der infizierten Fläche beträgt dann 32. Daraus folgt, dass der Umfang der infizierten Fläche zum Start bei mindestens 32 liegen muss.
32 ist jedoch auch der Umfang unserer oben beschriebenen Startkonstellation mit acht in der Diagonalen infizierten Feldern. Jedes dieser acht Felder hat nur einen oder zwei diagonale Nachbarn, jedoch keine senkrechte oder waagerechte.
Mit weniger als acht infizierten Feldern zum Start ist ein Gesamtumfang über alle infizierten Felder von 32 nicht möglich, weil dann schon der Umfang über alle Einzelfelder kleiner als 32 ist. Deshalb ist acht die kleinstmögliche Lösung.
Entdeckt habe ich diese Aufgabe auf dem Mathematikportal mathigon.org .
Sollten Sie ein Rätsel aus den vergangenen Wochen verpasst haben – hier sind die jüngsten zehn Folgen:
Kommen drei Logiker in eine Bar...: Die schönsten Mathe-Rätsel (Aus der Welt der Mathematik, Band 3)
Preisabfragezeitpunkt
01.04.2023 15.16 Uhr
Keine Gewähr
