{"id":3262,"date":"2022-03-27T23:15:11","date_gmt":"2022-03-27T21:15:11","guid":{"rendered":"https:\/\/vielhuber.de\/?p=3262"},"modified":"2022-03-28T01:32:31","modified_gmt":"2022-03-27T23:32:31","slug":"mathematik-im-spiel-dobble","status":"publish","type":"post","link":"https:\/\/vielhuber.de\/blog\/mathematik-im-spiel-dobble\/","title":{"rendered":"Mathematik im Spiel Dobble"},"content":{"rendered":"\n

Beim letzten Familienabend wurde das Spiel Dobble<\/a> (in der Harry Potter Edition) begeistert von den Kindern zu Tisch gebracht. Nach der 5ten verlorenen Runde (ohne sichtbaren Treffer meiner Karte mit der Spielkarte) wurde mir unter meinem Erstaunen mitgeteilt, dass jeder Spieler in jeder Runde immer einen Treffer finden kann. Doch meine Ungl\u00e4ubigkeit wurde nur mit weiteren, verlorenen Runden quittiert \u2013 die Kinder waren einfach schneller.<\/p>\n\n\n\n\n\n\n\n

Grund genug, sich das Spiel aus mathematischer Sicht genauer anzusehen. Zun\u00e4chst zum Spielprinzip: Dobble ist ein simples Kartenspiel mit \\(55\\) runden Karten, die jeweils acht verschiedene Symbole zeigen. Alle Karten werden reihum ausgeteilt, nur die letzte Karte bleibt in der Tischmitte. Nun m\u00fcssen alle Spieler gleichzeitig die Symbole auf der Karte mit den Symbolen ihrer aktuell oben liegenden Karte vergleichen. Hat ein Spieler das auf beiden Karten gleiche Symbol gefunden, kann er seine Karte auf den Stapel ablegen, indem er als Schnellster das Symbol benennt. Gewonnen hat der Spieler, der zuerst alle seine Karten abgelegt hat.<\/p>\n

Wie kann es nun sein, dass es \\(55\\) solcher Karten gibt, die so konstruiert wurden, dass jeweils 2 beliebige Karten jeweils genau ein gemeinsames Symbol haben? Wie viele solcher Symbole m\u00fcssen dazu minimal verwendet werden? Wie viele solcher Karten gibt es maximal?<\/p>\n

Zun\u00e4chst konstruieren wir diese Karten durch folgende logische Schritte (alle nachfolgend konstruierten Karten haben die Eigenschaft, dass sie aufsteigend sortiert sind): Die erste Karte muss 8 verschiedene Symbole tragen, lautet also:<\/p>\n

$$\\left(\\begin{array}{c} 1 \\\\ 2 \\\\ 3 \\\\ 4 \\\\ 5 \\\\ 6 \\\\ 7 \\\\ 8 \\end{array}\\right)$$<\/p>\n

Wie konstruieren nun die folgenden Karten so, dass sie mit der ersten Karte genau ein gemeinsames Symbol haben:<\/p>\n

$$\\left(\\begin{array}{c} 1 \\\\ x_{1.2} \\\\ x_{1.3} \\\\ x_{1.4} \\\\ x_{1.5} \\\\ x_{1.6} \\\\ x_{1.7} \\\\ x_{1.8} \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ x_{2.2} \\\\ x_{2.3} \\\\ x_{2.4} \\\\ x_{2.5} \\\\ x_{2.6} \\\\ x_{2.7} \\\\ x_{2.8} \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ x_{3.2} \\\\ x_{3.3} \\\\ x_{3.4} \\\\ x_{3.5} \\\\ x_{3.6} \\\\ x_{3.7} \\\\ x_{3.8} \\end{array}\\right), \\ldots, \\left(\\begin{array}{c} 1 \\\\ x_{k.2} \\\\ x_{k.3} \\\\ x_{k.4} \\\\ x_{k.5} \\\\ x_{k.6} \\\\ x_{k.7} \\\\ x_{k.8} \\end{array}\\right)$$<\/p>\n

Bereits hier lassen sich beliebig viele solcher Karten konstruieren (man f\u00fcllt die Stellen einfach aufsteigend beginnend mit \\(9\\) auf). Dieser triviale Fall ist aber uninteressant, da wir an einem Set mit minimaler Symbolanzahl (und maximaler Kartenzahl) interessiert sind. Wir betrachten nun jeweils das zweite Symbol \\( x_{l.2} \\) jeder Karte, f\u00fcr das offensichtlich gelten muss: \\( x_{1.2} \\neq x_{2.2} \\neq x_{3.2} \\neq \\ldots \\neq x_{k.2} \\). Wir haben also zwingend \\( k \\) neue Symbole eingef\u00fchrt. Nun ist aber \\( k \\leq 8-1 = 7 \\), da keines der \\( 7 \\) Symbole \\( x_{1.2},\\, x_{1.3},\\, x_{1.4},\\, x_{1.5},\\, x_{1.6},\\, x_{1.7},\\, x_{1.8} \\) (der Karte ganz links) mit dem jeweils zweiten Symbol der anderen Karten \u00fcbereinstimmen darf (sonst g\u00e4be es zwei gleiche Symbole).<\/p>\n

Damit haben wir maximal diese 7 neuen Karten gefunden:<\/p>\n

$$\\left(\\begin{array}{c} 1 \\\\ x_{1.2} \\\\ x_{1.3} \\\\ x_{1.4} \\\\ x_{1.5} \\\\ x_{1.6} \\\\ x_{1.7} \\\\ x_{1.8} \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ x_{2.2} \\\\ x_{2.3} \\\\ x_{2.4} \\\\ x_{2.5} \\\\ x_{2.6} \\\\ x_{2.7} \\\\ x_{2.8} \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ x_{3.2} \\\\ x_{3.3} \\\\ x_{3.4} \\\\ x_{3.5} \\\\ x_{3.6} \\\\ x_{3.7} \\\\ x_{3.8} \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ x_{4.2} \\\\ x_{4.3} \\\\ x_{4.4} \\\\ x_{4.5} \\\\ x_{4.6} \\\\ x_{4.7} \\\\ x_{4.8} \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ x_{5.2} \\\\ x_{5.3} \\\\ x_{5.4} \\\\ x_{5.5} \\\\ x_{5.6} \\\\ x_{5.7} \\\\ x_{5.8} \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ x_{6.2} \\\\ x_{6.3} \\\\ x_{6.4} \\\\ x_{6.5} \\\\ x_{6.6} \\\\ x_{6.7} \\\\ x_{6.8} \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ x_{7.2} \\\\ x_{7.3} \\\\ x_{7.4} \\\\ x_{7.5} \\\\ x_{7.6} \\\\ x_{7.7} \\\\ x_{7.8} \\end{array}\\right)$$<\/p>\n

Mit demselben Argument konstruieren wir nun die n\u00e4chsten \\(7\\) Karten (die erste dieser Karten muss ja mit unserer Ausgangskarte kollidieren, und zwar nicht mit \\(1\\), da sie sonst bei den \\(7\\) zuvor gefundenen Karten w\u00e4re):<\/p>\n

$$\\left(\\begin{array}{c} 2 \\\\ x_{8.2} \\\\ x_{8.3} \\\\ x_{8.4} \\\\ x_{8.5} \\\\ x_{8.6} \\\\ x_{8.7} \\\\ x_{8.8} \\end{array}\\right), \\left(\\begin{array}{c} 2 \\\\ x_{9.2} \\\\ x_{9.3} \\\\ x_{9.4} \\\\ x_{9.5} \\\\ x_{9.6} \\\\ x_{9.7} \\\\ x_{9.8} \\end{array}\\right), \\left(\\begin{array}{c} 2 \\\\ x_{10.2} \\\\ x_{10.3} \\\\ x_{10.4} \\\\ x_{10.5} \\\\ x_{10.6} \\\\ x_{10.7} \\\\ x_{10.8} \\end{array}\\right), \\left(\\begin{array}{c} 2 \\\\ x_{11.2} \\\\ x_{11.3} \\\\ x_{11.4} \\\\ x_{11.5} \\\\ x_{11.6} \\\\ x_{11.7} \\\\ x_{11.8} \\end{array}\\right), \\left(\\begin{array}{c} 2 \\\\ x_{12.2} \\\\ x_{12.3} \\\\ x_{12.4} \\\\ x_{12.5} \\\\ x_{12.6} \\\\ x_{12.7} \\\\ x_{12.8} \\end{array}\\right), \\left(\\begin{array}{c} 2 \\\\ x_{13.2} \\\\ x_{13.3} \\\\ x_{13.4} \\\\ x_{13.5} \\\\ x_{13.6} \\\\ x_{13.7} \\\\ x_{13.8} \\end{array}\\right), \\left(\\begin{array}{c} 2 \\\\ x_{14.2} \\\\ x_{14.3} \\\\ x_{14.4} \\\\ x_{14.5} \\\\ x_{14.6} \\\\ x_{14.7} \\\\ x_{14.8} \\end{array}\\right)$$<\/p>\n

Dieses Argument l\u00e4sst sich f\u00fcr die n\u00e4chsten \\(7\\) Karten ebenso fortf\u00fchren; Insgesamt noch \\(8-2 = 6\\) mal. Die letzten \\(7\\) Karten lauten demnach:<\/p>\n

$$\\left(\\begin{array}{c} 8 \\\\ x_{50.2} \\\\ x_{50.3} \\\\ x_{50.4} \\\\ x_{50.5} \\\\ x_{50.6} \\\\ x_{50.7} \\\\ x_{50.8} \\end{array}\\right), \\left(\\begin{array}{c} 8 \\\\ x_{51.2} \\\\ x_{51.3} \\\\ x_{51.4} \\\\ x_{51.5} \\\\ x_{51.6} \\\\ x_{51.7} \\\\ x_{51.8} \\end{array}\\right), \\left(\\begin{array}{c} 8 \\\\ x_{52.2} \\\\ x_{52.3} \\\\ x_{52.4} \\\\ x_{52.5} \\\\ x_{52.6} \\\\ x_{52.7} \\\\ x_{52.8} \\end{array}\\right), \\left(\\begin{array}{c} 8 \\\\ x_{53.2} \\\\ x_{53.3} \\\\ x_{53.4} \\\\ x_{53.5} \\\\ x_{53.6} \\\\ x_{53.7} \\\\ x_{53.8} \\end{array}\\right), \\left(\\begin{array}{c} 8 \\\\ x_{54.2} \\\\ x_{54.3} \\\\ x_{54.4} \\\\ x_{54.5} \\\\ x_{54.6} \\\\ x_{54.7} \\\\ x_{54.8} \\end{array}\\right), \\left(\\begin{array}{c} 8 \\\\ x_{55.2} \\\\ x_{55.3} \\\\ x_{55.4} \\\\ x_{55.5} \\\\ x_{55.6} \\\\ x_{55.7} \\\\ x_{55.8} \\end{array}\\right), \\left(\\begin{array}{c} 8 \\\\ x_{56.2} \\\\ x_{56.3} \\\\ x_{56.4} \\\\ x_{56.5} \\\\ x_{56.6} \\\\ x_{56.7} \\\\ x_{56.8} \\end{array}\\right)$$<\/p>\n

W\u00fcrde man nun eine weitere Karte $$\\left(\\begin{array}{c} 9 \\\\ x_{57.2} \\\\ x_{57.3} \\\\ x_{57.4} \\\\ x_{57.5} \\\\ x_{57.6} \\\\ x_{57.7} \\\\ x_{57.8} \\end{array}\\right)$$ konstruieren wollen, misslingt dies, da diese Karte kein gemeinsames Symbol mit der Anfangskarte hat. Damit haben wir maximal \\(1 + 8 \\cdot 7 = 57\\) Karten konstruiert. Unser Ziel ist es nun, auch minimal ebenso viele zu konstruieren.<\/p>\n

Dazu sehen wie uns die ersten 7 neuen gefundenen Karten an und kommen zum Schluss, dass wir hier zwingend \\(7 \\cdot 7\\) neue Symbole brauchen (keine Karte darf ein Symbol doppelt haben und jedes zu vergebene Symbol darf nicht doppelt vorkommen, da die \\(1\\) bereits doppelt ist):<\/p>\n

$$\\left(\\begin{array}{c} 1 \\\\ 9 \\\\ 10 \\\\ 11 \\\\ 12 \\\\ 13 \\\\ 14 \\\\ 15 \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ 16 \\\\ 17 \\\\ 18 \\\\ 19 \\\\ 20 \\\\ 21 \\\\ 22 \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ 23 \\\\ 24 \\\\ 25 \\\\ 26 \\\\ 27 \\\\ 28 \\\\ 29 \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ 30 \\\\ 31 \\\\ 32 \\\\ 33 \\\\ 34 \\\\ 35 \\\\ 36 \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ 37 \\\\ 38 \\\\ 39 \\\\ 40 \\\\ 41 \\\\ 42 \\\\ 43 \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ 44 \\\\ 45 \\\\ 46 \\\\ 47 \\\\ 48 \\\\ 49 \\\\ 50 \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ 51 \\\\ 52 \\\\ 53 \\\\ 54 \\\\ 55 \\\\ 56 \\\\ 57 \\end{array}\\right)$$<\/p>\n

Damit ben\u00f6tigen wir minimal \\(8 + (7 \\cdot 7) = 57\\) Symbole (also genauso viele Symbole wie Karten!). Mit dieser Anzahl versuchen wir nun auszukommen und eine Konstruktionsvorschrift f\u00fcr alle anderen Elemente zu finden. Dazu konstruieren wir ein etwas kleineres Dobble, das nur \\(3\\) Symbole pro Karte tr\u00e4gt und erhalten als Anfangskarte<\/p>\n

$$\\left(\\begin{array}{c} 1 \\\\ 2 \\\\ 3 \\end{array}\\right)$$<\/p>\n

sowie die weiteren Karten<\/p>\n

$$\\left(\\begin{array}{c} 1 \\\\ 4 \\\\ 5 \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ 6 \\\\ 7 \\end{array}\\right)$$<\/p>\n

$$\\left(\\begin{array}{c} 2 \\\\ x_{3.2} \\\\ x_{3.3} \\end{array}\\right), \\left(\\begin{array}{c} 2 \\\\ x_{4.2} \\\\ x_{4.3} \\end{array}\\right)$$<\/p>\n

$$\\left(\\begin{array}{c} 3 \\\\ x_{5.2} \\\\ x_{5.3} \\end{array}\\right), \\left(\\begin{array}{c} 3 \\\\ x_{6.2} \\\\ x_{6.3} \\end{array}\\right)$$<\/p>\n

mit insgesamt \\(1 + 3 \\cdot 2 = 7\\) Karten und \\( 3 + (2 \\cdot 2) = 7\\) Symbolen. Durch etwas Probieren (und Einsetzen der bereits vergebenen Symbole) erh\u00e4lt man folgendes Dobble:<\/p>\n

$$\\left(\\begin{array}{c} 1 \\\\ 2 \\\\ 3 \\end{array}\\right)$$<\/p>\n

$$\\left(\\begin{array}{c} 1 \\\\ 4 \\\\ 5 \\end{array}\\right), \\left(\\begin{array}{c} 1 \\\\ 6 \\\\ 7 \\end{array}\\right)$$<\/p>\n

$$\\left(\\begin{array}{c} 2 \\\\ 4 \\\\ 6 \\end{array}\\right), \\left(\\begin{array}{c} 2 \\\\ 5 \\\\ 7 \\end{array}\\right)$$<\/p>\n

$$\\left(\\begin{array}{c} 3 \\\\ 4 \\\\ 7 \\end{array}\\right), \\left(\\begin{array}{c} 3 \\\\ 5 \\\\ 6 \\end{array}\\right)$$<\/p>\n

L\u00e4sst sich das auch systematisch finden? Dazu tragen wir die neu vergebenen Symbole \\(4, 5, 6, 7\\) in eine quadratische Matrix auf:<\/p>\n

$$\\begin{array}{ccc} 4 & & 5 \\\\ & & \\\\ 6 & & 7\\end{array}$$<\/p>\n

Nun denken wir uns f\u00fcr die ersten beiden Karten (beginnend bei den Startsymbolen \\(4\\) und \\(5\\)) vertikale Verbindungslinien zu den unteren Symbolen \\(6\\) und \\(7\\):<\/p>\n

$$\\begin{array}{ccc} 4 & & 5 \\\\ \\vdots & & \\vdots \\\\ 6 & & 7\\end{array}$$<\/p>\n

Da sich diese Linien nicht schneiden, erhalten wir (durch zeilenweises Auftragen der Symbole an den Verbindungslinien) die n\u00e4chsten g\u00fcltigen Karten:<\/p>\n

$$\\left(\\begin{array}{c} 2 \\\\ 4 \\\\ 6 \\end{array}\\right), \\left(\\begin{array}{c} 2 \\\\ 5 \\\\ 7 \\end{array}\\right)$$<\/p>\n

Schlie\u00dflich denken wir uns Verbindungslinien mit einer anderen Steigung (in diesem Fall mit der Steigung \\(1\\)):<\/p>\n

$$\\begin{array}{ccccc}\u00a0& 4 & & 5 & \\\\ \\ddots & & \\ddots & & \\ddots \\\\ & 6 & & 7 &\\end{array}$$<\/p>\n

Die zweite Verbindungslinie (zwischen \\(5\\) und \\(6\\)) verl\u00e4sst die Matrix am rechten Rand und tritt am linken Rand wieder ein. Durch die geschickte Wahl der Steigung stellen wir zum einen sicher, dass sich die Verbindungslinien jeweils untereinander nicht schneiden aber auch die vorherigen (vertikalen) Verbindungslinien nicht schneiden. Diese Konstruktionsidee f\u00fchrt schlussendlich zu folgender Konstruktionsformel:<\/p>\n

Ein Dobble mit \\(k \\in \\mathbb{N} \\, | \\, (k-1) \\text{ prim} \\) hat je \\(1+(k \\cdot (k-1)) = k^2-k+1 = k + (k-1)(k-1)\\) Karten und Symbole. F\u00fcr die Karte \\(K_x\\) mit \\(x \\in \\mathbb{N}\\) und \\(0 \\leq x \\leq (k-1) \\cdot k\\) gilt:<\/p>\n

$$K_x = \\left(\\begin{array}{c} f(x,1) \\\\ f(x,2) \\\\ \\vdots \\\\ f(x,k) \\end{array}\\right), \\,\\, m = \\left\\lfloor \\frac{x-1}{k-1} \\right\\rfloor + 1,$$<\/p>\n

$$f(x,y) = \\left\\{\\begin{array}{ll} y & \\text{falls } x = 0 \\\\ \\lfloor \\frac{x-1}{k-1} \\rfloor + 1, &\\text{sonst falls } y = 1 \\\\ (k+1) + (k-1)(x-1) + (y-2), & \\text{sonst falls } 0 < x < k \\\\ \\left( \\left((m-1)(k-1)+x\\right)-1+ \\left( (m-2)(y-2) \\right) \\right) \\% (k-1) &\\text{sonst} \\\\ + (k+1) + (k-1)(y-2)&\\end{array}\\right.$$<\/p>\n

Von diesen Karten gibt es damit \\((k-1)\\cdot k + 1 = k + (k-1)(k-1)\\) St\u00fcck. Nun ist nur noch abschlie\u00dfend zu zeigen:<\/p>\n

$$ \\forall x_1 < x_2 \\in \\{ 1, \\ldots, k+(k-1)(k-1) \\} \\, \\exists \\, ! \\, y_1, y_2 \\in \\{ 1, \\ldots, k \\}: f(x_1, y_1) = f(x_2, y_2) $$<\/p>\n