Kombinatorik-Workshop: Das große Abenteuer des Zählens

Ein interaktiver, ganztägiger Workshop, um die Geheimnisse der Kombinatorik zu lüften – von einfachen Zählproblemen bis zur Struktur komplexer Spiele.

Das große Abenteuer des Zählens

Ein ganztägiger Workshop, um die Geheimnisse der Kombinatorik zu lüften – von einfachen Zählproblemen bis zur Struktur komplexer Spiele.

Station 1: Der Funke

Warum brauchen wir Kombinatorik? Wir starten mit einigen Problemen, die zeigen, wie schnell simples Abzählen unmöglich wird und wie elegant mathematische Strukturen helfen können.

Das Handschlagproblem

Wenn sich 10 Personen die Hand geben, wie viele Handschläge gibt es?

Ansatz: C(10, 2) = ?

Lösung anzeigen

Handschläge: 45

Jeder Handschlag ist eine Kombination (Auswahl) von 2 Personen aus n, die Reihenfolge ist egal.

Anagramm-Rätsel

Wie viele unterscheidbare (nicht notwendig sinnvolle) Wörter lassen sich aus den Buchstaben des Wortes „PERMUTATIONEN“ bilden?

Ansatz: 13! / (2! · 2! · 2!) = ?

Lösung anzeigen

Möglichkeiten: 778.377.600

Es ist eine Permutation mit Wiederholung, da die Buchstaben E, T, und N jeweils zweimal vorkommen. Wir teilen durch die Permutationen der doppelten Buchstaben.

Das Kleiderschrank-Problem

Du hast 5 T-Shirts, 3 Hosen und 2 Paar Schuhe. Wie viele verschiedene Outfits kannst du zusammenstellen?

Ansatz: 5 × 3 × 2 = ?

Lösung anzeigen

Outfits: 30

Nach dem fundamentalen Zählprinzip (Produktregel) werden die Möglichkeiten für jede Wahl multipliziert.

Wege auf dem Gitter

Wie viele kürzeste Wege gibt es von Start zu Ziel? Auf einem kleinen Gitter kann man noch zählen. (Die Lösung entdecken wir in Station 4!)

Station 2: Das Handwerkszeug

Um Zählprobleme zu meistern, brauchen wir vier grundlegende Werkzeuge. Diese ergeben sich aus zwei einfachen Fragen: Ist die Reihenfolge wichtig? Und sind Wiederholungen erlaubt? Erkunde die vier Fälle!

Variation mit Wiederholung
Passwort
Variation ohne Wiederholung
Medaillen
Kombination mit Wiederholung
Gummibärchen
Kombination ohne Wiederholung
Lotto

Wähle einen Fall aus!

Klicke auf einen der vier Bereiche oben, um das passende Ankerbeispiel zu sehen und damit zu experimentieren.

Station 3: Das Schubfachprinzip

Eines der stärksten Beweisprinzipien der Mathematik ist verblüffend einfach: Wenn man mehr Tauben als Schubfächer hat, müssen sich mindestens zwei Tauben ein Fach teilen. Lasst uns sehen, welche überraschenden Wahrheiten wir damit beweisen können.

Haare auf dem Kopf

Gibt es in Berlin (ca. 3.7 Mio Einwohner) zwei Menschen mit exakt der gleichen Anzahl Haare? Ein Mensch hat max. 150.000 Haare.

Objekte (Tauben): 3.700.000 Berliner

Fächer (Schubladen): 150.001 mögl. Haaranzahlen (0-150k)

Schlussfolgerung

Da 3,7 Mio > 150.001, ist die Aussage wahr!

Die Denksportaufgabe

In jeder Gruppe von 5 Leuten gibt es immer zwei, die gleich viele Freunde innerhalb der Gruppe haben. Warum?

Schritt-für-Schritt-Beweis
  1. Objekte: Die 5 Personen.
  2. Fächer: Die mögl. Anzahl an Freunden (0, 1, 2, 3, oder 4).
  3. Das Problem: Es gibt 5 Objekte und 5 Fächer. Das Prinzip scheint nicht zu greifen.
  4. Der Trick: Können die "Freundes-Anzahlen" 0 und 4 gleichzeitig vorkommen? Nein! Wenn eine Person 0 Freunde hat (niemanden kennt), kann keine andere Person 4 Freunde haben (alle kennen).
  5. Schlussfolgerung: Es gibt nur maximal 4 verschiedene Freundes-Anzahlen in der Gruppe. Wir haben also 5 Personen auf 4 Fächer verteilt. Das Prinzip greift!

Station 4: Das Pascalsche Dreieck

Dieses einfache Zahlendreieck ist eine Schatztruhe voller Muster und verbirgt die Lösungen zu vielen unserer Probleme. Lasst uns auf Entdeckungsreise gehen!

Station 5: Das große Finale – Die Welt des SET®-Spiels

SET® ist mehr als nur ein Spiel. Es ist ein perfektes Beispiel für eine endliche Geometrie, das uns von einfachen Zählprinzipien bis an die Grenzen moderner Forschung führt. Klicke auf die Titel, um die einzelnen Teile zu entdecken.

Teil I: Die Grundlagen – Die Kombinatorik des Kartendecks

Frage 1: Die Anatomie des Decks

Jede Karte hat vier Merkmale (Farbe, Form, Füllung, Anzahl) mit je drei Ausprägungen. Wie viele einzigartige Karten gibt es im Deck? Nutze das Multiplikationsprinzip!

Frage 2: Die Regel der Vervollständigung

Ein SET besteht aus drei Karten, bei denen jedes Merkmal entweder bei allen drei Karten gleich oder bei allen verschieden ist. Daraus folgt: Zwei beliebige Karten bestimmen eindeutig eine dritte, die das Set vervollständigt. Überprüfe es selbst!

Der SET-Finder
+
=
?

Frage 3: Die Gesamtzahl der SETs

Wie viele verschiedene 3-Karten-Kombinationen gibt es im gesamten 81-Karten-Deck, die ein Set bilden?

Lösungsweg anzeigen
  1. Wähle die erste Karte. Dafür gibt es 81 Möglichkeiten.
  2. Wähle die zweite Karte. Dafür gibt es noch 80 Möglichkeiten.
  3. Die dritte Karte ist durch die ersten beiden eindeutig bestimmt (nur 1 Möglichkeit).
  4. Das ergibt 81 × 80 × 1 = 6480 geordnete Paare, die Sets definieren. Aber hier zählt die Reihenfolge!
  5. Ein Set {A, B, C} ist dasselbe wie {B, A, C} etc. Es gibt 3! = 6 Anordnungen (Permutationen) für 3 Karten.
  6. Wir müssen das Ergebnis durch 6 teilen: 6480 / 6 = 1080.

Es gibt 1080 einzigartige SETs.

Frage 4: Die Wahrscheinlichkeit eines SETs

Wenn ich 3 Karten zufällig aus dem Deck ziehe, wie groß ist die Wahrscheinlichkeit, dass sie ein Set bilden?

Lösungsweg anzeigen

Wahrscheinlichkeit = (Anzahl günstige Ergebnisse) / (Anzahl mögliche Ergebnisse).

  • Anzahl günstige Ergebnisse (Anzahl SETs): 1080 (aus Frage 3).
  • Anzahl möglicher Ergebnisse: "Wie viele 3-Karten-Hände gibt es?". Das ist der Binomialkoeffizient C(81, 3).
  • C(81, 3) = (81 × 80 × 79) / (3 × 2 × 1) = 85.320.

Wahrscheinlichkeit = 1080 / 85.320 ≈ 1/79.

Teil II: Die Geometrie hinter dem Spiel – SET als Vektorraum

Jede Karte kann als Vektor im 4-dimensionalen Raum F₃⁴ über dem Körper {0, 1, 2} (Rechnen modulo 3) dargestellt werden. Ein SET ist dann eine "Gerade": Drei Vektoren x, y, z, deren Summe der Nullvektor ist: x + y + z = (0,0,0,0) mod 3.

Karten-zu-Vektor-Konverter

Übersetze eine Karte in ihre Koordinaten in F₃⁴ (Farbe, Anzahl, Form, Füllung).

Vektor: (0, 0, 0, 0)

Teil IIb: Fortgeschrittene Zählprobleme

Mit unseren Werkzeugen können wir nun die SETs klassifizieren. SETs sind nicht alle gleich aufgebaut. Man kann sie danach unterscheiden, in wie vielen Merkmalen ihre Karten übereinstimmen.

Problem 1: SETs mit 2 gleichen Merkmalen

Wie viele SETs gibt es, bei denen die drei Karten in genau zwei Merkmalen übereinstimmen und sich in den anderen beiden unterscheiden? (z.B. alle rot & oval, aber Anzahlen und Füllungen sind 1,2,3 und leer,gestreift,voll)

Lösungsweg anzeigen
  1. Wähle eine beliebige Startkarte (81 Möglichkeiten).
  2. Die zwei gleichen Merkmale sind dadurch festgelegt. Die anderen beiden müssen verschieden sein.
  3. Wähle die zweite Karte: Sie muss in 2 Merkmalen übereinstimmen (1 Möglichkeit) und in 2 Merkmalen verschieden sein (2 Möglichkeiten pro Merkmal, also 2*2=4 Wege). Das ist zu kompliziert.
  4. Einfacherer Weg:
  5. Wähle die 2 Merkmale, die gleich sind: C(4,2) = 6.
  6. Wähle die Ausprägungen für diese 2 Merkmale: 3 × 3 = 9. (z.B. "Rot" und "Oval")
  7. Die Karten müssen nun in diesen Merkmalen (Rot, Oval) übereinstimmen, und in den anderen beiden (Anzahl, Füllung) verschieden sein. Es gibt genau ein Set dieser Art (Karten mit {Anz:1, Füll:1}, {Anz:2, Füll:2}, {Anz:3, Füll:3}).
  8. Gesamtzahl: C(4,2) × 3 × 3 = 6 × 9 = 54 SETs.
Problem 2: SETs mit 0 gleichen Merkmalen

Wie viele SETs gibt es, bei denen sich die drei Karten in allen vier Merkmalen unterscheiden?

Lösungsweg anzeigen
  1. Wähle die erste Karte: 81 Möglichkeiten.
  2. Wähle die zweite Karte: Sie muss sich in allen 4 Merkmalen von der ersten unterscheiden. Für jedes Merkmal gibt es 2 verbleibende Ausprägungen. Also 2×2×2×2 = 16 Möglichkeiten.
  3. Die dritte Karte ist durch die ersten beiden eindeutig bestimmt.
  4. Wir haben 81 × 16 geordnete Paare gezählt. Jedes "total verschiedene" Set wird von 6 geordneten Paaren erzeugt.
  5. Korrektur: (81 × 16) / 6 = 216 SETs.

Teil III: An der Grenze der Forschung – Das Cap-Set-Problem

Das Cap-Set-Problem stellt eine fundamentale Frage: Was ist die maximale Anzahl von Karten, die man aus dem Deck auswählen kann, sodass sich kein einziges SET darunter befindet? Man spielt quasi "SET-Vermeiden".

Ein einfaches Beispiel: SET mit 2 Merkmalen

Stell dir ein Mini-SET nur mit Farbe und Anzahl vor. Es gibt 3x3=9 Karten. Man kann sie als Gitter anordnen. Ein SET ist eine Zeile, Spalte oder Diagonale. Wie viele Karten kannst du maximal platzieren, ohne ein SET zu bilden?

Man kann 4 Karten auswählen (z.B. die Ecken). Aber egal, wo man die 5. Karte hinlegt, sie vervollständigt immer ein SET. Die Antwort ist also 4.

Das Problem für unser Spiel (4 Merkmale)

Für unser Spiel mit 81 Karten ist dieses Problem extrem schwierig. Die Antwort wurde erst mit Computern gefunden und der Beweis ist sehr komplex. Das Ergebnis ist eine "magische Zahl":

Was ist die maximale Größe eines Cap-Sets?

Die maximale Größe eines Cap-Sets ist 20. Das bedeutet: Jede beliebige Ansammlung von 21 Karten auf dem Tisch muss garantiert mindestens ein SET enthalten!

Teil IV: Anwendung zentraler Prinzipien auf SET

Das Schubfachprinzip in SET

Wie viele Karten muss man mindestens ziehen, um zu garantieren, dass man zwei Karten hat, die sowohl in der Farbe als auch in der Form übereinstimmen?

Beweis mit Schubfächern

Fächer (Schubladen): Jede Kombination aus Farbe und Form ist ein Fach. Es gibt 3 Farben × 3 Formen = 9 Fächer.

Objekte (Tauben): Die gezogenen Karten.

Wie viele Karten braucht man?

Um sicherzustellen, dass ein Fach doppelt belegt ist, müssen wir nach dem Schubfachprinzip 9 + 1 = 10 Karten ziehen.