Sammelbilderproblem

Datei:Basketball-sammelkarten hg.jpg

Basketball-Sammelbilder

Das Sammelbilderproblem, Sammler-Problem, Sammelalben-Problem oder Problem der vollständigen Serie (englisch Coupon Collector's Problem) befasst sich mit der Fragestellung, wie viele Bilder einer Sammelbildserie zu kaufen sind, um ein Sammelalbum vervollständigen zu können.

Beim klassischen Sammelbilderproblem wird davon ausgegangen, dass alle Bilder verdeckt gekauft werden und gleich häufig vorkommen. Die letztere Voraussetzung ist aber beispielsweise bei Sammelkartenspielen, auch Trading Card Games genannt, nicht erfüllt, da hier das Vorkommen der einzelnen Karten teilweise stark variiert. Eine weitere wichtige Rolle spielt die Möglichkeit des Nachkaufens und Tauschens von Karten. Mit Hilfsmitteln der Wahrscheinlichkeitstheorie sowie Monte-Carlo-Simulationen können Sammelstrategien optimiert werden, um das Sammelalbum möglichst kostengünstig zu füllen.

Das Sammelbilderproblem ist insbesondere aufgrund der Beliebtheit der Fussball-Sammelalben eines der wenigen mathematischen Probleme, über das regelmäßig in den Massenmedien berichtet und diskutiert wird.

Geschichte

Historisches Eishockey-Sammelbild

Sammelbilder haben eine lange Tradition, schon im 19. Jahrhundert gab es Sammelbilder als Produktzugaben z. B. bei Schokolade oder Zigaretten. Eine Variante bestand darin, dass Coupons gesammelt werden mussten und der Sammler nach Einsendung einer vollständigen Serie eine Prämie erhielt. In den 1930-er Jahren erschienen Bilder von Film- oder Sportstars auf der Deckel-Innenseite von Eiscreme-Packungen. Aber es gab auch schon früh andere Sammelobjekte, z. B. Buttons oder Figuren in Cornflakes-Packungen. Erst in den 1960-er Jahren haben sich vermehrt Sammelalben etabliert, bei denen die Bilder verdeckt in Tüten oder Päckchen verkauft wurden, d. h. ohne dass der Sammler weiß, welche Bilder er erhält. Mit der Einführung von Fußballsammelalben, vorangetrieben durch die Firma Panini, wurde das Sammeln zu einem Massenphänomen, insbesondere zu Fußball-Welt- oder Europameisterschaften. Mittlerweile sind Sammelalben zu Standard-Merchandising-Artikeln z. B. für Kinofilme geworden.

Die grundlegenden kombinatorischen Betrachtungen gehen bereits auf Markow zurück. Die konkrete mathematische Behandlung begann 1930 mit George Pólya, der das Problem aus Sicht des Herstellers darstellt: „Jede Packung unserer Ware enthält zwei verschiedene Blumenbilder; die volle Kollektion umfasst 72 verschiedene Blumenbilder; wer eine volle Kollektion sammelt und einsendet, erhält kostenlos eine Prämie. Der Verkäufer, der solche Reklame macht, muss sich vernünftigerweise die Frage vorlegen: Wie groß ist die Durchschnittszahl der verkauften Packungen pro Prämie?“ Diese Arbeit prägte daher den Namen als Coupon Collector's Problem. Teilweise wurde es auch als Dixie Cup Problem bezeichnet (nach den Eiskrembechern, die nach der Herstellerfirma als Dixie Cup bezeichnet wurden). Beginnend mit William Fellers Standardwerk zur Wahrscheinlichkeitstheorie haben sich zahlreiche Mathematiker mit dem Sammelbilderproblem beschäftigt. Dadurch hat sich das Sammelbilderproblem als klassische mathematische Aufgabenstellung etabliert.

Manchmal wird die Aufgabenstellung auch als Sammelbilderparadoxon bezeichnet. Dies rührt daher, dass überraschend viele Bilder benötigt werden, wenn man das Sammelalbum ohne Tauschen oder Nachkaufen vervollständigen möchte. Für Pólyas Blumenbilder-Kollektion muss man im Durchschnitt 174 Päckchen, also 348 Blumenbilder sammeln (bei nur 72 unterschiedlichen Bildern), für das aktuelle Sammelalbum zur EURO 2016 benötigt man sogar 4828 Bilder (bei 680 unterschiedlichen Bildern). Dieses Paradoxon kann dadurch erklärt werden, dass das Verhältnis der im Mittel benötigten Bilder zur Anzahl der unterschiedlichen Bilder stärker als linear anwächst.

Das klassische Sammelbilderproblem

Im klassischen Sammelbilderproblem soll die Frage beantwortet werden, wie viele Sammelbilder ein Einzelsammler im Mittel kaufen muss, um eine vollständige Serie von $n$ Sammelbildern zu erhalten, wenn Tauschen und Nachkaufen ausgeschlossen ist und er jedes Bild einzeln kauft. Schon Pólya hatte die klassische Aufgabenstellung definiert und wie folgt begründet: „Die Käufer tauschen ihre Bilder aus oder werfen sie fort, der Verkäufer kann ein Bild vorenthalten usw. Wie man sieht, kann die Nichterfüllung der Voraussetzungen sowohl die eine als auch die andere Partei begünstigen und eben deshalb scheint mir die Berechnung der Durchschnittszahl unter den besagten Voraussetzungen zumindest als erste Orientierung einen gewissen Wert zu haben“.

Der Ergebnisraum kann als Menge der möglichen Sammelbilderfolgen definiert werden:

$\Omega :=\{\omega =(\omega _{1},\omega _{2},\dotsc ):\omega _{i}\in \{1,2,\dotsc ,n\}\}$.

Urnenmodell des Sammelbilderproblems mit 6 Bildern

Mathematisch entspricht das Sammelbilderproblem einem Urnenmodell mit Zurücklegen und zwar bedeuten die gezogenen Zahlen die Nummern der Sammelbilder. Gesucht wird die Anzahl der Ziehungen, die nötig ist, bis jede Zahl mindestens einmal gezogen wurde. Dies bedeutet, dass die einzelnen gezogenen Nummern der Sammelbilder eine diskrete Gleichverteilung besitzen.

Wartezeit auf das nächste neue Bild

Die Zufallsvariable $X_{i}(\omega )$ ordnet jedem Ergebnis $\omega \in \Omega$ die Anzahl der Käufe zu, die gemacht werden müssen, um nach der $(i-1)$-ten verschiedenen Karte wieder eine neue, von den bisher gekauften verschiedene $i$-te Karte zu bekommen. Dies entspricht der Wartezeit auf das nächste neue Bild.

Histogramm einer Simulation (100.000 Realisierungen) des klassischen Pokémon-Problems. Man erkennt die große Streuung: Im schlechtesten Fall mussten 2522 Karten gekauft werden.

Da beim ersten Kauf sicher ein neues Bild kommt, ist die Wahrscheinlichkeit $P(X_{1}=1)=1$ . Beim Kauf des zweiten Bildes ist sie $P(X_{2}=1)=(n-1)/n$. Diese Zufallsvariable ist geometrisch verteilt. Allgemein ergibt sich:

$P(X_{i}=k)=\left({\frac {i-1}{n}}\right)^{k-1}\,\left({\frac {n-i+1}{n}}\right)$.

Als Erwartungswert für $X_{i}$ ergibt sich:

$E\left(X_{i}\right)={\frac {n}{n-i+1}}$.

Dies bedeutet insbesondere, dass man, um das letzte fehlende Bild der Sammlung zu erhalten, im Mittel $n$ Bilder kaufen muss. Das sind aber genauso viele Bilder, wie man überhaupt sammeln muss und erklärt, warum das Sammeln ohne Tauschen und Nachkaufen so teuer ist.

Wahrscheinlichkeitsverteilung

Die Zufallsvariable

$X:=\sum \limits _{i=1}^{n}X_{i}$,

gibt an, wie viele Käufe gemacht werden müssen, um alle Karten zu besitzen. Dies ist eine Summe unabhängiger geometrisch verteilter Zufallsvariabler, die eine diskrete Phasenverteilung besitzt. Die Wahrscheinlichkeitsverteilung kann durch Auswertung der zugehörigen Markow-Kette oder rekursiv berechnet werden.

Erwartungswert

Mittlere Anzahl S benötigter Bilder für eine vollständige Serie aus n Bildern mit Standardabweichung (grau)

Da die einzelnen Erwartungswerte der $X_{i}$ existieren, existiert auch der Erwartungswert $S$ für die neue Zufallsvariable:

$S=E(X)=\sum \limits _{i=1}^{n}E(X_{i})$.

Dann gilt:

$S={\frac {n}{n}}+{\frac {n}{n-1}}+{\frac {n}{n-2}}+\dotsb +{\frac {n}{1}}$

$S=n\cdot H_{n}{\text{ mit }}H_{n}=\sum _{k=1}^{n}{\frac {1}{k}}$

$H_{n}$ ist die $n$-te Partialsumme der harmonischen Reihe. $H_{n}$ ist also der Faktor, der angibt, wie viel mal mehr Bilder man kaufen muss im Vergleich zur Größe des Sammelalbums. Für große n gilt die Näherung durch den natürlichen Logarithmus: $H_{n}\approx \ln n+0{,}577$.

Päckchen

Datei:Fussball-Sammelbilderpaeckchen.JPG

Fussball-Sammelbilder-Päckchen

Sammelbilder werden in der Regel nicht einzeln, sondern in Päckchen (häufig auch Tüten oder Booster genannt) verkauft. Dabei wird vom Hersteller garantiert, dass innerhalb eines Päckchens kein Bild mehrfach vorkommt.

Die allgemeine Lösung ist kompliziert, aber der Vergleich der Ergebnisse ergibt, dass der Effekt der Päckchen eher gering ist, wenn die Päckchengröße im Verhältnis zur Gesamtzahl der Sammelbilder klein ist. Dies bedeutet für die meisten praktischen Anwendungen, dass die Päckchengröße vernachlässigt werden kann, denn die Wahrscheinlichkeit $P_{D}$, dass es in einem Päckchen mindestens eine doppelte Karte gibt, beträgt wie beim Geburtstagsparadoxon

$P_{D}=1-\left({\frac {n}{n}}\cdot {\frac {n-1}{n}}\cdot {\frac {n-2}{n}}\dotsm {\frac {n-p+1}{n}}\right)$.

Varianz

Da die Wartezeiten auf die jeweils nächsten neuen Bilder geometrisch verteilt und unabhängig sind, ergibt sich mit $q_{i}=P(X_{i}=1)$ für die Varianz $V$ der Anzahl der zu sammelnden Bilder

$V={\frac {1-q_{1}}{q_{1}^{2}}}+{\frac {1-q_{2}}{q_{2}^{2}}}+\cdots +{\frac {1-q_{n}}{q_{n}^{2}}}$

In der Abbildung wächst die Standardabweichung mit $n$ stark an.

Nachkaufen

Datei:Sammelbilder-Nachbestellschein.JPG

Ein Bestellschein, mit dem Sammelbilder beim Hersteller nachbestellt werden können.

Die meisten Hersteller bieten an, dass eine bestimmte Anzahl $K$ von Bildern (häufig 50) nachgekauft werden kann, in der Regel zu einem erhöhten Preis. Außerdem kann man gezielt bestimmte Sammelbilder kaufen, z. B. in speziellen Sammlerbörsen oder Online-Shops. Die wichtige Frage ist, wann sich Nachkaufen lohnt.

Fehlen noch $x$ Bilder und ein bestimmtes Bild wird zum Preis von $k$ angeboten, so lohnt sich der Kauf, wenn im Mittel die Kosten geringer sind als die Kosten für das das nächste Bild beim normalen Sammeln. Sei $b$ der normale Preis einen einzelnen Bildes, so lohnt sich der Kauf , wenn

$b{\frac {n}{x}}>k$.

Wenn die Möglichkeit besteht $K$ Bilder nachzukaufen, so lohnt es sich am meisten, diese komplett am Ende nachzukaufen. Man müsste sonst im Mittel

${\frac {n}{1}}+{\frac {n}{2}}+{\frac {n}{3}}+\dotsb +{\frac {n}{K}}=n\cdot H_{K}$

Bilder kaufen, statt $K$ Bilder nachzukaufen, und dieser Spareffekt kann sehr groß sein.

Tauschen

Datei:Sammelbilder-Tauschbörse.JPG

Plakat für eine Fussball-Sammelbilder-Tauschbörse zur EURO 2016

Eine weitere wichtige Erweiterung ist das Tauschen von Doppelten. Dies geschieht traditionell im Freundeskreis, zunehmend aber auch in organisierten Tauschbörsen z. B. über das Internet. In der mathematischen Modellierung wird in der Regel das faire Tauschen betrachtet, d. h. es wird jeweils ein Bild gegen ein anderes getauscht. Auch wird angenommen, dass die $m$ Tauschpartner kooperieren und solange gemeinsam sammeln und fair tauschen, bis jeder Sammler sein Album gefüllt hat. Dies entspricht dem Fall, als ob ein Sammler $m$ Sammelalben vervollständigt.

Für diesen Fall wurde bisher keine geschlossene Lösung gefunden, am Beispiel des WM-Albums wurde per Simulation gezeigt, dass der Effekt erheblich ist. Asymptotisch gilt für den Mittelwert bei einer festen Anzahl $m$ von Tauschpartnern

$S_{m}=n\ln n+(m-1)n\ln \ln n+O(n),\ \ {\text{für}}\ n\to \infty .$

Dies zeigt den Effekt des Tauschens: während der erste Sammler im Mittel $n\ln n$ Karten kaufen muss, braucht jeder weitere Sammler im Mittel nur $n\ln \ln n$ zusätzlich kaufen. Mit dieser Formel kann man grob abschätzen, wie viel Geld man durch das Tauschen sparen kann. Z. B. würden sich die Kosten für zwei Tauschpartner durch faires Tauschen auf etwa 60% der Kosten eines Einzelsammlers reduzieren.

Optimierte Sammelstrategie

Datei:Sammelbilder-Display.JPG

Ein Display (auch Box genannt) der Sammelbilderserie "Mission Tierfreunde".

Für die Kombination von Tauschen und Nachkaufen gibt es bisher keine analytischen Ergebnisse. Per Simulation wurde nachgewiesen, dass das Potenzial solcher optimierter Strategien erheblich ist. Es wird allerdings davon ausgegangen, dass in einem Display (das sind Verpackungen für den Handel mit 50 oder 100 Päckchen) keine Doppelten vorkommen.

Die Empfehlung aufgrund der Simulationsergebnisse ist die folgende optimierte Sammelstrategie:

1. Kauf eines Displays
2. Kauf weiterer Päckchen und Tausch möglichst vieler Bilder, bis nur noch die möglichen Nachkaufbilder fehlen
3. Nachkauf (am Schluss) der maximal erlaubten Zahl von Bildern beim Hersteller

In einem Jugend-forscht-Projekt wurde 2016 für das Szenario „faires Tauschen mit Nachkaufen“ der Faktor $f={\frac {S}{mn}}$ durch umfangreiche Simulationen untersucht, wobei $S$ die mittlere Anzahl insgesamt zu kaufender Bilder aller Tauschpartner ist. Der Faktor $f$ gibt mithin an, wieviel mal mehr Bilder jeder Sammler am Ende im Mittel gekauft hat, als das vollständige Album Bilder enthält. Während ohne Tauschen und Nachkaufen der Faktor für einen Einzelsammler gut durch den natürlichen Logarithmus der Anzahl der Sammelbilder angenähert werden kann (bzw. dem doppelten Logarithmus für eine große Anzahl von Tauschpartnern), konnten sie plausibel experimentell belegen, dass bei fairem Tauschen mit Nachkaufen, bei festem Nachkaufprozentsatz, $f\to 1$ strebt, wenn die Anzahl der tauschenden Sammler $m\to \infty$ strebt.

Kritik

Die Annahmen des klassischen Sammelbilderproblems werden häufig als unrealistisch kritisiert und insbesondere im Internet kursieren Gerüchte, dass die Hersteller entweder Bilder künstlich verknappen oder die Bilder nicht ordentlich mischen, d. h. zu viele Doppelte vorkommen oder manche Bilder zu selten.

Ein Journalist von Spiegel online untersuchte die Annahmen für das Sammelalbum zur Fußball-Weltmeisterschaft 2014 zusammen mit der Website stickermanager.com. Durch die Betrachtung des aufbereiteten Datenbestandes von 8,33 Millionen Einträgen kam der Statistiker Christan Hesse zu dem Ergebnis: „Die gravierenden Unterschiede lassen sich mit dem Wirken des Zufalls allein nicht erklären“. Dabei wurde angenommen, dass die Online-Umfrage repräsentativ ist. Allerdings galt dies nur für die deutsche Edition, z. B. bei der Schweizer Edition, die separat produziert wird und optisch unterscheidbar ist, traten die 2,36 Millionen registrierten Sticker gleichmäßig häufig auf. In einer systematischen Untersuchung des Herstellungsprozesses konnte nachgewiesen werden, dass bei der Verpackung von Displays systematische Abweichungen bzw. Muster entstehen, die sich signifikant vom zufälligen Mischen unterscheiden. Dies wirkt sich allerdings nicht machteilig für den Sammler aus.

Das allgemeine Sammelbilderproblem

Im allgemeinen Sammelbilderproblem kann die Wahrscheinlichkeit für jedes Bild unterschiedlich sein, und zwar $p_{i}$. Dies ist der allgemeinste Fall einer diskreten Wahrscheinlichkeitsverteilung. Die Lösung ist nicht mehr mit elementarer Wahrscheinlichkeitsrechnung herleitbar, sondern nur mit erzeugenden Funktionen. Für den Mittelwert ergibt sich

$S=\int _{0}^{\infty }{\big (}1-\prod _{i=1}^{n}(1-e^{-p_{i}t}){\big )}dt$.

Hiermit kann man für einen Sammler ohne Nachkaufen die mittlere Anzahl benötigter Karten für Trading Card Games berechnen.

Beispiele

Würfel

Spielwürfel

Für pädagogische Zwecke wird häufig das Sammelbilderproblem mit Hilfe eines normalen Spielwürfels eingeführt und veranschaulicht. In der Praxis könnte dies z. B. $n=6$ Sammelfiguren entsprechen, die einem Produkt beigemischt sind.

Man muss durchschnittlich 14,7 mal werfen, um jede Augenzahl mindestens einmal zu bekommen, denn es gilt

$S=6\cdot H_{6}=6\cdot \left(1+{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{5}}+{\frac {1}{6}}\right)={\frac {147}{10}}=14{,}7$.

Nimmt man die Päckchengröße $p=2$ an (dies entspricht Würfeln mit zwei Würfeln unter Ausschluss eines Paschs), so erhält man

$S=\left(1+1+{\frac {3}{2}}+{\frac {5}{3}}+3+5\right)={\frac {79}{6}}\approx 13{,}17$

Augenzahlen, d. h. man muss im Durchschnitt ${\frac {1}{2}}\cdot {\frac {79}{6}}\approx 6,58$ mal würfeln, da mit einem Wurf zwei Würfel (mit verschiedenen Augenzahlen) geworfen werden. Es gilt $P_{D}={\frac {1}{6}}$, d. h. man kann erwarten, durch das Päckchen im Mittel mindestens ein Bild zu sparen.

Eine einfache Erweiterung besteht darin, mit zwei unterscheidbaren Würfel zu spielen und damit ein Sammelalbum mit $n=36$ Sammelbildern zu simulieren. Dies entspricht dem von REWE herausgegebenen offiziellen DFB-Sammelalbum zur Euro 2016, wobei die Sammelbilder hier eine Produktzugabe für je 10€ Einkaufswert darstellen und nicht nachgekauft werden können. Hier benötigt man als Einzelsammler zum Vervollständigen schon fast 150 Sammelbilder. Das Tauschen bekommt eine besondere Bedeutung, denn beim fairen Tauschen müsste jeder weitere Sammler dann nur etwa 67 Bilder sammeln, und das wäre gleichzeitig auch der Grenzwert bei sehr vielen Tauschpartnern.

Pokémon

Pokémon-Sammelkarten

Es gebe 150 verschiedene Motive auf den Pokémon-Karten, die man kaufen muss und die Karten seien einzeln verpackt. Wenn es sich um ein klassisches Sammelalbum handeln würde, dann müsste ein Einzelsammler ohne Nachkaufen im Mittel ungefähr 839 Karten kaufen.

Allerdings ist Pokémon in Wirklichkeit ein Trading Card Spiel, d. h. es gibt mehr als 5 unterschiedliche Kartentypen mit unterschiedlichen Seltenheiten, von normal bis extrem selten. Den großen Unterschied kann man schon bei zwei Kartentypen erkennen, bei denen z. B. 30 von 150 Karten halb so häufig auftreten wie im klassischen Sammelbilderspiel. Dann müsste der Einzelsammler schon im Mittel etwa 1213 Karten kaufen. Gibt es 10 sehr seltene Karten, die zehnmal seltener auftreten, dann bräuchte er sogar etwa 4372 Karten. Dies bedeutet, dass Nachkaufen und Tauschen noch eine größere Bedeutung besitzen als bei den klassischen Sammelbildern.

Fußball-Sammelbilder

Das aktuelle Panini-Album zur Euro 2016 mit 680 Bildern kostet mindestens 95,20 € bei einem regulären Preis von 14 Cent pro Bild. Dies wäre gleichzeitig auch der erwartete Preis für das letzte fehlende Bild, wenn man es normal sammeln würde. Für den Faktor gilt $H_{680}\approx 7{,}1$, dies ergibt für einen Einzelsammler ohne Tauschen und Nachkaufen eine mittlere Anzahl zu kaufender Bilder von etwa 4828 (d. h. 965,5 Päckchen) und entspricht etwa 676 €. Aber auch die Standardabweichung ist groß (869 Bilder), d. h. in etwa 95,4 % aller Fälle müsste ein Einzelsammler zwischen 3090 und 6566 Bilder sammeln. Dies verdeutlicht, dass unbedingt getauscht und nachgekauft werden sollte, um die Kosten zu verringern.

Der Einfluss der Päckchen ist gering, bei 5-er Päckchen beträgt $P_{D}$ nur ungefähr 0,016, d. h. bei etwa jedem 60-ten Päckchen müsste man mal ein doppeltes Bild erwarten, wenn die Karten zufällig gemischt würden. Dieser Einfluss wird häufig überschätzt oder falsch eingeschätzt, bei exakter Rechnung muss man im Mittel 963,2 Päckchen kaufen, d. h. die Ersparnis beträgt im Mittel nur 12 Bilder und kann daher auch in Anbetracht der großen Standardabweichung praktisch vernachlässigt werden.

Kann man 50 Bilder nachkaufen, spart man etwa 3060 Bilder, d. h. dann braucht man näherungsweise im Mittel nur 1768 Karten zu kaufen sowie 50 Nachkaufkarten. Dies kostet dann etwa 257 € bei 20 Cent pro Nachkaufbild (ohne Berücksichtigung des Päckchen-Effekts). Auch die Standardabweichung sinkt auf etwa 82 Bilder, d. h. in etwa 95,4% aller Fälle müsste ein Einzelsammler zwischen 1604 und 1936 Bilder sammeln.

Bei einer unendlich großen Sammelgemeinschaft wäre der Faktor für jeden Sammler etwa 1,88, d. h. jeder müsste im Mittel etwa 1275 Bilder kaufen, was einem Preis von etwa 179€ entspricht. Für das WM-Album 2014 wurde abgeschätzt, dass man mit einer optimierten Sammelstrategie das Sammelalbum für etwa 125 € füllen kann. Berücksichtigt man die Preiserhöhung und die zusätzlichen Sammelbilder des EM-Albums, so ergibt sich mit dieser Strategie ein Preis von etwa 150 €. Im Grenzfall des konsequenten Nachkaufens mit einer endlich großen Sammelgemeinschaft würden sich 98,20 € pro Sammler ergeben.