Kartenspiel gleiche symbole finden

Hallo,

mich beschäftigt eine Frage, die ich mir beim Spielen eines Kartenspiels gestellt habe.
Es besteht aus 55 Karten mit je 8 Symbolen auf jeder einzelnen Karte (insgesamt gibt es 50 verschiedene Symbole aus denen die 8 Symbole ausgewählt sind).

Vergleicht man nun zwei beliebige der 55 Karten, so ist genau ein Symbol auf beiden identisch. (*)

Nun frage ich mich: Wenn ich mir zum Beispiel die Anzahl der Karten vorgebe (hier 55) und möchte, dass auf jeder Karte 8 Symbole abgebildet sind, die die Regel (*) erfüllen, wie komme ich dann auf die minimale Anzahl an Symbolen, die ich dafür benötige?

Oder andersrum: Wenn ich mir 50 Symbole vorgebe und auf jeder Karte sollen 8 Symbole drauf sein, wie komme ich dann auf die Anzahl der Karten?

Vielleicht ist es ja ganz einfach, ich grüble jedenfalls seit 2 Tagen drüber :-)

Ich hatte mir überlegt, wenn man zwischen jeder der 55 Karten genau eine Verbindungslinie zieht, dann gibt es ja 54+353+52+...+1 = 1485

Also ich hab mir folgendes überlegt:

Deine 55 Karten bilden 55 stabile Mengen mit jeweils 8 Knoten, die für die 8 Symbole stehen.
Zwei Knoten sind verbunden genau dann wenn sie das gleiche Symbol darstellen

Aus jeder stabilen Menge musst genau eine Kante zu den anderen stabilen MEngen führen, d.h. (wie du gesagt hast es gibt)
54+53+52+..+1=:Sum Kanten in diesem Graph, das sind auch alle.

Jetzt überlegt man sich dass die Zusammenhangskomponenten im Graphen Cliquen bilden müssen. Denn sei vi Knoten aus stabilen Menge Si:
vj sei mit vk verbunden und vk mit vl verbunden daraus folgt vj ist mit vl verbunden, weil vj das gleiche Symbol wie vk ist, vk geliche Symbol mit vj, also vi gleiches symbol wie vj.
Und Anzahl der versch. Zusammnhangskomp. = Anzhal der versch Symbole

Die Anzahl der Kanten der Clique auf k Knoten ist k*(k-1)/2, k max 8

insgesamt gilt Anzahl der Kanten der Clique = Sum

Gesucht ist
min(k aus N) Summe( i=1,..k) Anzahl der Kanten(Ck) = Sum

Also suche minimale Anzhal an Cliquen sodass die Gleichung stimmt.
Dachte zuerst dass das äquivalent dazu ist dass jeder Summand links möglcihst groß ist, das musst aber nicht so sein, denke ich.

Den Rest musst man sich selbst überlegen xD

Vielen Dank für deinen Beitrag zu meinem Problem :)
Darüber muss ich mal weiter nachdenken, ich bin in Graphentheorie noch nicht ganz so sehr bewandert.

Es sei

Ich habe ein wenig herumprobiert, aber noch kein Paar

Die Fall

Folgender Kartensatz beweist

NACHTRAG:
Wie wir mittlerweile erfahren, hat Newton2's Kartenspiel 57_Symbole insgesamt (und nicht_50), so dass das Spiel mit

Hallo,

falls Newton2 im Themenstart recht hat, ist (8, 50) so ein Paar.

Gruß
Zvz

-----------------
Jeden Tag eine gute Einsicht.

Guten Abend zusammen :)

Für den Fall m=3 kann man folgendermassen klassifizieren:

Die erste Karte kann o.B.d.A die Symbole 1,2,3 tragen, Jede der folgenden Karten muss dann genau eine der drei Ziffern 1, 2 oder 3 enthalten. Dabei sei 1 eines der (oder genau) das Symbol, das/die am häufgsten auf den Karten vorkommt.

Wenn 1 nur zweimal vorkommt, dann können es insgesamt nur 2+ 2x1 = 4 Karten sein, dh die Lösung ist nicht optimal für alle Fälle mit n>6 (siehe Beispiel von Goswin bzw. obige Liste). Damit sind die Fälle interessant, in denen die 1 auf mindestens drei Karten vorkommt.

Da sie wann immer sie vorkommt zwei unigue verwendete Begleiter braucht, kann sie maximal nur [ (n-1)/2 ] fach vorkommen, dh für die Fälle n=7 und n=8 auch nur genau dreimal.

Kommt sie dreimal vor, so bilden sich daraus für die Karten, auf denen die 2 vorkommt, zwei Blöcke (4,5 und 6,7), aus denen sie je eine Ziffer enthalten müssen, und zwar wiederum eindeutig. Damit gibt es zwei weitere Möglichkeiten ( zB 2:4:6 und 2:5:7). Da dasselbe Argument auch für die Anzahl der Karten gilt, die die 3 enthalten, kann es insgesamt nur 3 + 2 + 2 = 7 Möglichkeiten geben. Und das sind genau die tatsächlich auch realisierten Fälle

K[3,7]=7
K[3,8]=7

Und - weil ein Bild mehr sagt als 1000 Worte:

...

-----------------
Rhetorische Figur des Tages: Das Oxymeron
Und - hier und heute - erinnern wir an Tiro

...

kommt die 1 jedoch viermal (oder noch öfter) vor, so hat sie mindestens 3 Blöcke von Begleitziffern, und eine Karte, auf der 2 oder 3 vorkommt, könnte es nicht geben, da sie nicht aus jedem dieser Blöcke eine Ziffer enthalten könnte.

Damit macht es dann nur Sinn, für höhere Werte von n auf die Lösungen zu gehen, in denen ein Symbol allen Karten gemein ist, dh es gibt dann jeweils 1 + [(n-3)/2] Möglichkeiten.

Damit nehme ich an dass insgesamt gilt:

K(3,n) = 7 für n = 7..14
K(3,n) = [(n-1)/2] für n>14

Einen schönen Samstagabend wünscht
gonz

PPS:

nach dem Schema kann man zeigen, dass

und damit insbesondere K(8,57)=57. Also fast, aber eben nur fast, die angegebenen Werte.

gonz

Wow, vielen Dank für eure vielen Antworten zum Thema. Da bin ich ja schonmal beruhigt, dass es nicht ganz so trivial ist ;)

Da ihr interessiert an den Werten n=50, m=8 und K(m,n)=55 seid, kann ich euch auf das Spiel verweisen, welches mich dazu veranlasst hat überhaupt darüber nachzudenken
Hier der Link:

Viele Grüße
Newton2

P.S. Unten in der Beschreibung stehen die konkreten Werte, die ich oben angab.

Hallo Newton :)

Vielen Dank für die Link! Hast du nochmal nachgesehen, dass wirklich je zwei Karten genau ein Symbol gemeinsam haben? * ggg

Grüsse
und einen schönen Start in die Woche allerseits

gonz

Das Kartenspiel ist nicht symmetrisch angelegt.

"Dobbelgänger" 25.12.2012 in Amazon-Rezensionen schreibt:

Das Spiel ist echt super witzig, jedoch fehlen zwei wichtige Schneemann Karten! Man muss davon ausgehen, dass der Hersteller uns diese absichtlich vorenthält, um Mathenerds in den Wahnsinn zu treiben. Es zeigt sich leicht, dass es

Für symmetrisch angelegte Kartensätze (

eine nötige Bedingung ist [aber siehe Nachtrag]. Der Beschreibungsfilm des Kartenspiels (

Der Rezensent "Dobbelgänger" irrt wenn er meint, die fehlenden Karten auf 3432 Weisen zusammenstellen zu können; das hängt von den bereits vorhandenen Karten ab, und ich kann mir denken, dass es womöglich gar keine Weise gibt, zwei zusätzliche Karten zusammenzustellen. Ich kann zum Beispiel mit 4 Symbolen pro Karte und 4*3+1=13 Symbolen insgesamt durchaus 10_Karten finden, die zueinander genau ein gemeinsames Symbol haben, aber 13 solche Karten kann ich nicht finden. Es ist also nicht gesagt, dass die Hersteller vorhatten, "Mathenerds in den Wahnsinn zu treiben"; sie hielten sich vielleicht einfach nur an was möglich ist.

NACHTRAG:
Die vermutete Beziehung für symmetrische Kartensätze ist falsch; es muss heißen

Hallo Goswin,

Grüsse
und beruhigt dass Theorie und Praxis zusammenpassen

gonz

Es sind aber nur 55 Karten drin!

Hallo Newton :)

Das würde doch soweit passen, dann hätte man aus den 57 möglichen Karten eben 2 herausgelassen (warum auch immer), die man auf (mindestens) (bzw. wahrscheinlich genau) eine Art ergänzen kann, Goswin schreibt ja auch, welche das sind (eben "Schneemannkarten"). Bei der Aufteilung in das 1+m(m-1) Schema kann man sich eine beliebige Karte herausgreifen, und deren 8 Symbole kommen dann auf je sieben weiteren Karten vor (das schreit geradezu nach Gruppentheorie, ich hab aber aktuell leider nur kombinatorische Beweise gefunden).

Grüsse
gonz

Ja, danke gonz für die Erläuterung, klingt sehr plausibel.
Ganz schön tricky das ganze ;)
Du hast recht, sicher kann man das auch mit Gruppentheorie lösen, aber in das Gebiet bin ich noch nicht tief genug eingedrungen...
Danke jedenfalls euch allen, die ihr mir weitergeholfen habt!

@Goswin: Wo hast du denn die Behauptung her, dass das Spiel 57 Symbole hat, wie du oben schreibst?

Produktvideo in deinem Link :)

Gruß
Zvz

Jetzt hab ich es gesehen, danke! :)
Dann steht es blöd in der Anleitung, da steht nämlich 50 Symbole. Heißt ja nicht genau 50 ;)

Ich unterscheide im folgenden zwischen "zulässigen Kartensätzen" (jede Karte hat dieselbe Anzahl unterschiedlicher Symbole) und "symmetrischen Kartensätzen" (jede Karte hat dieselbe Anzahl unterschiedlicher Symbole und jedes Symbol ist auf gleich vielen Karten abgebildet).  Symmetrie kann für den Spielverlauf wichtig sein: im unsymmetrischen Extremfall würde jede Karte

Satz:
Ein symmetrischer Kartensatz (jede Karte hat dieselbe Anzahl unterschiedlicher Symbole und jedes Symbol ist auf gleich vielen Karten abgebildet), mit

Beweis:
Es sei

Die Anzahl der Kartenpaare, die ein fest vorgegebenes Symbol enthalten, ist dann

Das beweist einen Teil der Aussage, und wegen

Jeder symmetrische Kartensatz ist auch zulässig; aus der eben gefundenen Gleichung und dem Satz im vergangenen

Wegen

Das vollendet den Beweis.

Die folgende Tabelle liefert einfache

In diesem letzten Teil meiner Beitrags-Trilogie geht es mir um maximale symmetrische Kartensätze. Wie bewiesen, gilt für jeden zulässigen Kartensatz

Ob es maximale unsymmetrische zulässige Kartensätze gibt weiß ich nicht; da ich unsymmetrische Kartensätze für relativ uninteressant halte, interessiert mich diese Fragestellung deutlich weniger.

Wie in den letzten zwei Beiträgen, sei

Alle diese nötigen Bedingungen für maximale symmetrische Kartensätze erleichtern die Suche nach konkreten Spielen mit vielen Karten, und in der Tat war es mir danach einfach, die folgenden Kartensätze zu finden. Dabei ist es egal, ob wir in einem beliebigen Schema den Karten Zeilen und den Symbolen Spalten zuordnen oder ob wir umgekehrt verfahren;

Jede echte Teilmenge eines maximalen symmetrischen Kartensatzes ist ein nichtmaximaler zulässiger Kartensatz;  diejenigen Teilmengen mit

Die Problemstellung in diesem Thema erinnert an die Faktorpläne in der statistischen Versuchsplanung.

@Newton2:
Besitzt du das Spiel?  Wenn ja, könntest du einmal alle Karten mit dem Schneemann-Symbol aus dem Spiel herausnehmen und für den Rest der Karten überprüfen, ob die Verteilung symmetrisch ist oder nicht? Ich kenne einen  maximaler symmetrischen Kartensatz mit

Ich habe einen Algorithmus, der einen Kartensatz aufstellt und für

Da der obige Algorithmus Verknüpfungen endlicher Körper verwendet, legt das die Vermutung nahe, dass er sich erweitern lässt, und dass für alle

Neben

NACHTRAG:
Die obige Vermutung ist inzwischen bewiesen; wir kennen nun unendliche viele symmetrische Kartensätze, die sich in drei Familien aufteilen lassen:

  (1) Für alle  

(2) Für alle  

(3) Für alle  

Ein kleiner noch offener Fall ist  

2013-07-24 14:34 - Goswin in Beitrag No. 21 schreibt:
Ein kleiner noch offener Fall ist  

ich habe das Thema nich sehr intensiv verfolgt, aber wenn ich das Problem richtig verstanden habe, dann habe ich eine Lösung zu diesem "kleinen offenn Fall"

Ich bezeichne die 26 Symbole praktischerweise mit A-Z. Dann sieht eine Lösung so aus (jede Zeile ist eine Karte)

ABCDEF--------------------
A-----GHIJK---------------
A----------LMNOP----------
-B--------KL----QRS-------
-B----G-----M--------VW--Z
--C---G------N--Q--TU-----
--C----H------O--R-----X-Z
---D---H---L-------T--W-Y-
---D----I-----O---S-UV----
----E---I---M---Q------XY-
----E----J-----P-R--U-W---
-----F---J---N----S-----YZ
-----F----K----P---T-V-X--

Kitaktus

Hallo,
mein Sohn hat das Spiel Dobble geschenkt bekommen und mich hat gleich nach dem ersten Spiel die dahinter steckende Mathematik interessiert. In meinen Versuchen eine Lösung zu finden habe ich eine Matrix aufgestellt bei der die erste Zeile nach unten immer um eine Stelle nach rechts versetzt wird. Für m = 4 kann das dann so aussehen:
1100101000000
0110010100000
0011001010000
0001100101000
0000110010100
0000011001010
0000001100101
1000000110010
0100000011001
1010000001100
0101000000110
0010100000011
1001010000001
Damit dabei dann auch tatsächlich eine Lösung ensteht, muss die erste Zeile so gewählt werden, das jeder Abstand von 1 bis m-1 genau einmal vorkommt. Dabei muss man sich die Zeile, wie einen Kreis vorstellen, nach der letzen Stelle kommt wieder die erste. Bis m = 4 sind die Lösungen noch einigermaßen trivial. Für m = 5 habe ich nach einigen Probieren noch eine Lösung gefunden. Für größere m hab ich dann ein Programm geschrieben, welches die folgenden Lösungen für die Positionen in der ersten Zeile produzierte:
5 - 1,2,5,15,17
6 - 1,2,16,20,22,25
7 - nix gefunden
8 - 1,2,6,28,35,38,44,46
9 - 1,2,13,21,27,31,34,36,58
10 - 1,2,7,11,24,27,35,42,54,56
Ab 11 dauert die Berechnung zu lange. Hier muss ich mein Programm noch stark optimieren.

Gruß Nolle

Hallo,
ich hab mein Programm jetzt optimiert und bis zur 14 Lösungen rechnen lassen. Hier also wieder die Positionen in den ersten Zeilen:
11 - nix gefunden
12 - 1,2,16,26,46,53,59,62,64,81,85,93
13 - nix gefunden
14 - 1,2,11,32,57,60,64,72,77,83,99,101,137,151

Gruß Nolle

2015-12-28 11:28 - nolle in Beitrag No. 24 schreibt:
In meinen Versuchen eine Lösung zu finden habe ich eine Matrix aufgestellt bei der die erste Zeile nach unten immer um eine Stelle nach rechts versetzt wird. Für m = 4 kann das dann so aussehen:
1100101000000
0110010100000
0011001010000
0001100101000
0000110010100
0000011001010
0000001100101
1000000110010
0100000011001
1010000001100
0101000000110
0010100000011
1001010000001
Damit dabei dann auch tatsächlich eine Lösung ensteht, muss die erste Zeile so gewählt werden, das jeder Abstand von 1 bis m-1 genau einmal vorkommt. Dabei muss man sich die Zeile, wie einen Kreis vorstellen, nach der letzen Stelle kommt wieder die erste.

Hallo Nolle, willkommen auf Matroids Matheplaneten!

Dein Beispiel freilich kann ich nicht ganz nachvollziehen. Dort ist

😄 Nachtrag, ich glaube ich habe es jetzt: du meinst mit "Abstand" die Differenz der Indices zweier Einsen, also die Anzahl der Nullen zwischen zwei Einsen plus_1.

Hallo Goswin,
sorry, wenn ich mich da etwas ungeschickt ausgedrückt habe, ich meinte tatsächlich die Differenz der Indizes zweier Einsen.
Außerdem musste gerade feststellen, dass ich mich vertippt habe. Die Differenzen von 1 bis n-1 (nicht m-1) müssen jeweils genau einmal vorkommen. Im Beispiel m=4 also n=13 sieht das folgendermaßen aus.
Indizes der ersten Zeile: 1,2,5,7
Differenzen:
1= 2-1
2= 7-5
3= 5-2
4= 5-1
5= 7-2
6= 7-1
7= 13 + 1-7 (nach der 13 kommt wieder die 1)
8= 13 + 2-7
9= 13 + 1-5
10= 13 + 2-5
11= 13 + 5-7
12= 13 + 1-2

Hi,

bin auf Umwegen zufällig hier gelandet und zu dem Schluss gekommen, dass das hier behandelt Problem sehr eng mit dem etwas allgemeineren

Viele Grüße
salomeMe

EDIT: Die Lösungsmengen beider Probleme haben eine Schnittmenge mit unendlich vielen Lösungen. Die Behauptung, dass das Keksproblem allgemeiner ist, ist aber falsch, da dass andere Problem viele Freiheitsgrade hat, die ich in der Eile übersehen hatte.

Hallo zusammen, wie sieht das Beispiel für q=5 aus?
Da müsste es ja 31 Karten geben, ich steht aber ziemlich auf dem Schlauch.
Vielen Dank vorab!