Zum Inhalt springen

22 Ein besonderes Spiel

© Friederike Hofmann, MATH+

Autor*innen: Alex McDonough (UC Davis), Ulrich Reitebuch (FU Berlin), Martin Skrodzki (TU Delft)

Aufgabe

Die Spieleabteilung des Weihnachtsforschungszentrums entwickelt ständig neue Spiele, damit es den Kindern auf der ganzen Welt nicht langweilig wird. In diesem Jahr hat sie sich ein Spiel ausgedacht, das sich speziell an Einzelkinder richtet: Es handelt sich um ein Solitärspiel, das auf einem Brett mit n\times 3 Feldern gespielt wird.

Jedes Feld kann genau einen Spielstein aufnehmen. Es gibt drei verschiedene Arten von Spielsteinen und n Spielsteine von jeder Art: Quadrate, Kreise und Rauten. Für jeden Typ sind die n Spielsteine mit den Zahlen 1 bis n beschriftet.

Eine Anordnung von Spielsteinen heißt stabil, wenn:

(a) In keiner Reihe befindet sich ein Quadrat rechts von einem Kreis oder einer Raute. In keiner Reihe befindet sich ein Kreis rechts von einer Raute.

(b) In den Spalten gelten die in Abbildung 1 dargestellten vertikalen Bedingungen für die Zahlen auf den Spielsteinen:

Abbildung 1: Die vertikalen Bedingungen für die Zahlen auf den Spielsteinen.

D. h. die nummerierten Quadrate, Kreise und Rauten müssen so platziert werden, dass die Ungleichungen aus Abbildung 1 erfüllt sind. Beispielsweise:

      • Ein Quadrat mit der i kann sich unterhalb eines Kreises oder einer Raute mit der Zahl j mit i\leq  j befinden.
      • Dagegen kann ein Kreis mit der Zahl i nur unterhalb einen Quadrats liegen, wenn das Quadrat die Zahl j mit i < j hat.

(c) In Reihen gelten für die Zahlen auf den Spielsteinen die horizontalen Bedingungen aus Abbildung 2, auch wenn die jeweiligen Spielsteine nicht direkt nebeneinander liegen:

Abbildung 2: Die horizontalen Bedingungen für die Zahlen auf den Spielsteinen.

Beispiele für eine stabile und eine instabile Anordnung der Spielsteine auf einem Spielbrett der Größe 2\times 3 sind in Abbildung 3 dargestellt:

Abbildung 3: Eine stabile und eine instabile Anordnung auf einem Spielbrett der Größe 2\times 3 Brett. Die linke Anordnung der Spielsteine ist stabil, alle Bedingungen sind erfüllt. Die rechte Anordnung der Spielsteine ist instabil: Während alle Spalten sowie die untere Reihe alle Bedingungen erfüllen, verstößt die obere Reihe gegen Regel (c), da der Kreis mit der größeren Zahl rechts vom Kreis mit der kleineren Zahl platziert ist (rot markiert).

Beachte, dass es zwar Bedingungen für die Zahlen verschiedener Spielsteintypen gibt, wenn sie vertikal platziert werden. Die horizontale Anordnung der Zahlen aber nur innerhalb eines Typs eingeschränkt ist. Das heißt, wenn zwei Spielsteine desselben Typs in derselben Zeile stehen, müssen sie von links nach rechts entsprechend ihrer Nummern angeordnet werden (auch wenn sie nicht nebeneinander stehen). In Reihen müssen zwei Spielsteine unterschiedlichen Typs nur die Regel (a) erfüllen, unabhängig von ihrer Nummerierung. Das heißt, ein Quadrat mit der Zahl 5 kann links von einem Kreis mit der Zahl 3 stehen.

Frage: Wie viele stabile Anordnungen der Spielsteine gibt es auf einem Brett der Größe 4\times 3 ?

Antwortmöglichkeiten:

  1. 1
  2. 2
  3. 3
  4. 4
  5. 3\cdot 4
  6. 3!\cdot 4
  7. 4!\cdot 3
  8. 3!\cdot 4!
  9. (3\cdot 4)!/3!^4
  10. (3\cdot 4)!

Projektbezug:

Die vorgestellte Aufgabe ist Teil einer offenen Frage in einem aktuellen Kombinatorik-Projekt.

In dem Projekt untersuchen wir ein Objekt namens neighborhood grid, das mit dem Auffinden von Beziehungen in Datensätzen in Verbindung steht (für mehr Details siehe unseren Artikel unter https://arxiv.org/abs/1710.03435). Grob gesagt, beschleunigt die Datenstruktur die Leistung bestimmter Algorithmen zur Teilchen- oder Zellsimulationen, indem sie schnelle, approximative Antworten auf die Frage liefert: Was sind für ein bestimmtes Teilchen oder eine Zelle die nächstgelegenen anderen Teilchen oder Zellen in seiner Umgebung?