Covering und Lotto Designs

von Hans Schmidt, Magdeburg

Die neuere Lotto Gewinnklasse Zweier plus Superzahl regt möglicherweise Lottofreunde zu folgender mathematischer Fragestellung an: Wieviele Tipps und welche genau, benötigt man, um garantiert zwei Richtige zu erzielen?

Bevor wir darauf eingehen, zuerst eine kurze Einführung in die Theorie kombinatorischer Designs.

Lotto Designs sind eine Verallgemeinerung der t-Designs bzw. Blockpläne, die wir als bekannt voraussetzen. Als Zwischenschritt definieren wir eine andere Verallgemeinerung des t-Designs, nämlich das Covering Design in Anlehnung an [2] wie folgt:

Es sei $v\ge k\ge t$. Ein t-(v,k,$\lambda$) Covering Design ist ein Paar (V,$\mathcal{B}$) mit V als eine Menge von v Elementen (den Punkten) und $\mathcal{B}$ einem Mengensystem von k-Untermengen von V (den sogenannten Blöcken) mit folgender Eigenschaft: Jede der insgesamt ${v \choose t}$ t-Untermengen von V muss in mindestens $\lambda$ Blöcken enthalten sein. Die minimale Blockzahl $C_{\lambda}(v,k,t)$ bezeichnet die kleinstmögliche Zahl solcher Blöcke.

Beispiel 1: Die Lotto Teil-Systeme 9/12 und 10/15 für 6aus49 und 6aus45 sind keine 3-Designs, sondern nur 2-Designs nämlich ein 2-(9,6,5) Design bzw. BIBD(9,12,8,6,5) und ein 2-(10,6,5) Design bzw. BIBD(10,15,9,6,5). Sie sind aber zusätzlich auch 3-(9,6,2) und 3-(10,6,2) Covering Designs! Sicher ist hier $C_2(9,6,3)\le 12=C_5(9,6,2)$ und $C_2(10,6,3)\le 15=C_5(10,6,2)$. Ob sogar Gleichheit gilt, ist dem Autor nicht bekannt.

Beispiel 2: Wir betrachten das 3-(8,6,1)-Covering Design, bzw. wegen $\lambda=1$ kürzer geschrieben das (8,6,3)-Covering Design, mit den Blöcken:

$$\mathcal{B}_{8,4}\; = \{\{1, 2, 3, 4, 5, 6\}, \{1, 2, 3, 4, 7, 8\}, \{1, 2, 5, 6, 7, 8\}, \{3, 4, 5, 6, 7, 8\}\}$$

Man teile die 8-Menge in {1,2,3,4,5,6} und {7,8} auf. Der erste Block ist klar. Die restlichen Blöcke werden benötigt, um alle restlichen Dreier {x,y,7}, {x,y,8}, {x,7,8} zu erhalten. Weniger als vier Blöcke reichen dazu nicht aus, da die Blöcke mindestens 4 Elemente gemeinsam haben. Man deshalb mit 3 Blöcken nicht mal $20+16+16=52$ der 56 Dreier überdecken kann. Weiter ist $\lambda=1$, denn z.B. $\{2,3,5\}$ ist nur einmal vertreten. Also ist die minimale Blockzahl $C_1$(8,6,3) =C(8,6,3)=4 .

Kommen wir jetzt zur Definition des Lotto Designs:

Es sei $v\ge \{k,p\}\ge t$. Ein t-(v,k,p,$\lambda)$ generalisiertes Covering Design (engl. general cover) ist ein Tripel (V, $\mathcal{P},\mathcal{B}$) mit V als Menge mit v Elementen, $\mathcal{P}$ als Mengensystem aller ${v \choose p}$ p-Untermengen von V und $\mathcal{B}$ einem Mengensystem von k-Untermengen von V (den sogenannten Blöcken) mit folgender Eigenschaft: Jede p-Untermenge P aus $\mathcal{P}$ hat mit mindestens $\lambda$ Blöcken wenigstens t Elemente gemein. Ist $\lambda=1$ spricht man vom (v,k,p,t)-Lotto Design. Die minimale Blockzahl $L(v,k,p,t)$ bezeichnet die kleinstmögliche Blockzahl des Lotto Designs.

Bevor wir uns ein Beispiel ansehen, beweisen wir folgenden Satz:

Satz 1: Es sei $v=v_1+v_2$ und $p=p_1+p_2-1$, dann gilt:

$$L(v,k,p,t)\le L(v_1,k,p_1,t)+L(v_2,k,p_2,t)$$

Beweis: Jede p-elementige Untermenge P von $V=V_1 \dot\cup V_2$, ist eindeutig in eine Teilmenge von $V_1$ und von $V_2$ zerlegbar. Dann liegen aber entweder $p_1$ Elemente oder mehr in $V_1$ oder andernfalls mindestens $p_2$ Elemente in $V_2$. Also gibt es entweder einen Block des $(v_1,k,p_1,t)$-Lotto Designs oder des $(v_2,k,p_2,t)$-Lotto Designs, der mit entsprechender Teilmenge von P mindestens t Elemente gemeinsam haben muss.

Beispiel 3: Mit diesem Satz erzeugen wir ein (16,6,5,3)-Lotto Design¹ :

$$L(16,6,5,3)\le L(8,6,3,3)+L(8,6,3,3)=C(8,6,3)+C(8,6,3)=8$$

Zunächst ist zu bemerken, das (v,k,t,t) Lotto Design ist nichts anders als ein (v,k,t) Covering Design! Mittels Beispiel 2 ist dann auch klar, wie man die 8 Blöcke gewinnt. Nach [2] ist interessanterweise L(16,6,5,3)=7 oder 8 und damit noch eine offene Frage! Ist die minimale Blockzahl noch unbekannt oder verschieden von der Blockzahl, sollte die Blockzahl mitangegeben werden. Etwa so: (16,6,5,3,=8) Lotto Design, 3-(9,6,2,=12) Covering Design.

Anwendung auf Lotto-Systeme

Dazu werden die speziellen Lotto Designs vom Typ (45,6,6,2) und (50,6,6,2) näher untersucht. Um deren minimalen Blockzahlen nach Oben abschätzen zu können, verwenden wir folgenden Satz:

Satz 2: $L(v,k,p,2)\le\min_{a_1+\ldots+a_{p-1}=v}(C(a_1,k,2)+\ldots+C(a_{p-1},k,2))$

Beweis: Wir zerlegen die Menge $V=A_1 \dot\cup A_2 \ldots\dot\cup A_{p-1}$ in lauter disjunkte Teilmengen $A_i$ mit $a_i$ Elementen. Wählt man eine beliebige p-Untermenge aus, muss - wegen dem Schubfachprinzip - mindestens ein $A_j$ zwei Elemente enthalten. $C(a_j,k,2)$ ist gerade die kleinste Anzahl von k-Blöcken, um alle Zweier von $A_j$ mindestens einmal zu überdecken. Da jedes $A_i$ dafür infrage kommt, folgt daraus die gesuchte Abschätzung.
Um die oberen Schranken berechnen zu können, greifen wir auf die Tabelle der minimalen Blockzahlen enthalten in [2] zurück. Auszugsweise sind nur die von uns benötigten C(v,6,2) für v=6..22 hier wiedergegeben. Die Tabelle lautet:

v	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
C(v,6,2)	1	3	3	3	4	6	6	7	7	10	10	12	12	15	16	17	19

Die Berechnung führt man am besten mit einem CAS wie z.B. MAPLE durch. Die Partitionen von $v$ stehen dort auf Kommando bereit und können mit dem select-Kommando auf solche, die aus genau p-1 Summanden bestehen und deren Summanden eine Maximalgröße (hier 22) nicht überschreiten, eingeschränkt werden. Eine Maximalgröße ist deshalb möglich, weil die mit kleineren Summanden bereits berechneten Schranken 15 und 19 dann offenbar nicht mehr unterboten werden können. Die minimalen Blockzahlen sind nämlich mit zunehmenden $v$ stets monoton nichtfallend. Das CAS liefert als kleinste obere Schranken:

L(45,6,6,2)$\le$ 15=C(9,6,2)+ C(9,6,2)+C(9,6,2)+C(9,6,2)+C(9,6,2),
L(50,6,6,2)$\le$ 19=C(9,6,2)+ C(9,6,2)+C(9,6,2)+C(9,6,2)+C(14,6,2)
Wenn nun diese Schranken sogar gleich den minimalen Blockzahlen wären, und nicht größer, hätten wir die Blöcke-Konstruktion der Lotto Designs auf kleinere Covering Designs zurückgeführt! Dies ist tatsächlich der Fall. Die minimalen Blockzahlen L(45,6,6,2)=15 sowie L(50,6,6,2)=L(49,6,6,2)=19 (!!) werden im Artikel von BATE und VAN REES [1] bewiesen.

Theorem: Auszugsweise entnommen aus [2]:
Die Werte von C(v,k,2) sind bekannt in folgenden Fällen:
1. C(v,k,2) = 3 für 1 < v / k $\le$ 3 / 2 ...
5. C(v,k,2) = 7 für 2 < v / k $\le$ 7 / 3, außer wenn 3 v = 7 k - 1
Wir benötigen demnach ein Methode die es erlaubt, aus den 3 Blöcken des (3,2,2) Covering Designs die 3 Blöcke des (9,6,2) Covering Designs und aus den 7 Blöcken des (7,3,2) Covering Designs die 7 Blöcke des (14,6,2) Covering Designs zu ermitteln!

Die Erweiterungsmethode

Diese Methode wird im Artikel von GORDON, KUPERBERG und PATASHNIK [3] erwähnt. Wir betrachten zunächst die folgende Block-Konstruktion eines $(d\cdot v,d\cdot k,2)$-Covering Designs aus d Kopien eines (v,k,2)-Covering Designs :
Jedem Block $B=(b_1,\ldots,b_k)$ des (v,k,2)-Covering Designs ordnen wir vermöge Abbildung: $B \mapsto (B,B_1,B_2,\ldots,B_{d-1})$ genau d Blöcke zu, wobei für die d-1 hinzukommenden Blöcke $B_j=(b_1+j\cdot v,\ldots,b_k+j\cdot v), j=1..d-1$ gelten soll. Alle so gebildeten Blöcke enthalten, zusammengenommen, genau $d\cdot v$ verschiedene Elemente. Anschließend vereinigen wir die d-Tupel der eingeführten Blöcke zu einem einzigen neuen Block mit jeweils genau $d\cdot k$ Elementen. Wir erhalten so ein Blocksystem mit offenbar ebensovielen Blöcken wie das Ausgangsdesign. Die Konstruktion beschreibt letztlich nichts anderes als die Ersetzung eines jeden Elements im Block des Ausgangsdesigns durch wohlbestimmte d neue Elemente, welche zusammen dann den neuen Block bilden.

Wir beweisen, dass die Überdeckungseigenschaft für die neuen Blöcke erhalten bleibt!

Satz 3: Es sei d,v$\ge$2. Das durch d-fache Ersetzung aus dem (v,k,2)-Covering Designs konstruierte neue Blocksystem, enthält alle Paare aus $d\cdot v$ Elementen, ist also ein $(d\,v,d\,k,2)$-Covering Design.²
Beweis: Wir haben da zum Einen, die durch d-fache Ersetzung jedes Ausgangselementes bedingten ${d \choose 2}$ neu hinzukommenden Paare, also insgesamt ${d \choose 2}\, v$ weitere neue Paare im neuen Blocksystem. Zum Anderen kommen an Stelle von jedem Paar im Block des Ausgangsdesign, jetzt $d^2$ weitere neue Paare im neuen Block hinzu, also ingesamt $d^2\,{v \choose 2}$ weitere neue Paare. Das ergibt folgende Anzahl verschiedener Paare:

$${d \choose 2}\, v+ d^2\,{v \choose 2}=\frac{d\, v\cdot(d-1) +d\,v\cdot d\,(v-1)}2=\frac{d\,v(d\,v-1)}2={d\,v \choose 2}$$

Jedes denkbare Paar gebildet, aus den $d\cdot v$ Elementen des neuen Blocksystems, ist damit in mindestens einem der neuen Blöcke enthalten.

Folgerung1: Sei $v'>v$ und $\frac{v'}{v}=\frac{k'}{k}=d$ (oder: v / k = v' / k'), dann gilt $C(v',k',2)\le C(v,k,2)$.

Folgerung2: Aus Symmetriegründen folgt Identität: ${d \choose 2}\, v+ d^2\,{v \choose 2}= {v \choose 2}\, d+ v^2\,{d \choose 2}$

Beispiel 4: Wegen $25\equiv 1 \bmod 6$ ist das (25,3,2)-Covering Design sogar ein Steiner-Tripelsystem mit $r=\frac{1\cdot 24}{2}=12$ und b = $\frac{25\cdot 12}{3}= 100$ Blöcken. Mit Erweiterungsfaktor d=2 erhalten wir daraus ein (50,6,2,=100)-Covering Design. Es ist also einerseits C(50,6,2)=L(50,6,2,2)$\le$ 100 andererseits aber L(50,6,6,2)=19. Ersteres überdeckt alle "Zweier", letzteres nur mindestens einen der "Zweier" eines beliebigen 6-Tupels.

Blöcke für (45,6,6,2) und (50,6,6,2) Lotto Designs
Mit der Erweiterungsmethode konstruiert man nun leicht, aus dem (3,2,2)-Covering Design (einem trivialen Steiner-System, darstellbar durch ein Dreieck):

$$\mathcal{B}_{3,3}= \{\{1,2\},\{2,3\},\{1,3\}\}$$

mittels Erweiterungsfaktor d=3, ein (9,6,2)-Covering Design :

$$\begin{align*} \mathcal{B}_{9,3}=\{&\{1,2\} \cup \{1+1\cdot 3,2+1\cdot 3\} \cup... ...dot 3\},\\ =\{&\{1,2,4,5,7,8\},\{1,3,4,6,7,9\},\{2,3,5,6,8,9\}\} \end{align*}$$

und aus dem (7,3,2)-Covering Design (einem Steiner-Tripelsystem, darstellbar durch eine FANO-Ebene):

$$\mathcal{B}_{7,7}=\{\{1,2,3\},\{1,4,5\},\{1,6,7\},\{2,4,6\},\{2,5,7\},\{3,4,7\},\{3,5,6\}\}$$

mittels Erweiterungsfaktor d=2, ein (14,6,2)-Covering Design :

$$\begin{align*} \mathcal{B}_{14,7}=\{&\{1,2,3\}\cup \{1+7,2+7,3+7\}, \{1,4,5\}... ...\},\\ &\{2,5,7,9,12,14\},\{3,4,7,10,11,14\},\{3,5,6,10,12,13\}\} \end{align*}$$

Aus $\mathcal{B}_{9,3}$ und $\mathcal{B}_{14,7}$ tatsächlich eine der vielen möglichen Varianten von Tippsystemen mit garantiert 2 Richtigen, für Auswahlwette 6aus45 und Lotto 6aus49, zu entwickeln, ist jetzt nicht mehr schwer. Die überschüssige Zahl 50 sollte dabei durch eine beliebige der Zahlen von $1\ldots49$ ersetzt werden.
Natürlich kann man alternativ, die Blöcke zum (9,6,2) und (14,6,2) Covering Design auch über die Website von
LA JOLLA : http://www.ccrwest.org/cover/table.html oder gleich das (49,6,6,2) Lotto Design über die Website : http://www.weefs-lottosysteme.de direkt entnehmen. Wer hingegen ein eigenes Lottodesign erwägt, schaue mal vorbei unter: http://lottoarchitect.anastasios-tampakis.net

Abschließend noch eine Warnung vor einem Trugschluss, der so lautet: Mit dem hier abgeleiteten Tippsystem hat man ja garantiert 2 Richtige. Also braucht es nur noch einen - mit bedingter Wahrscheinlichkeit - eintretenden dritten Treffer zum Gewinn!.
Leider ist das falsch, denn 2 Richtige sind erst nach der Ziehung der 6.ten Gewinnzahl garantiert. Weitere Richtige kann es danach aber nicht mehr geben - ausgenommen die Superzahl natuerlich. Die dafür ebenfalls infrage kommende Zusatzzahl von 6aus45, führt hingegen allein noch nicht zum Gewinn. In Hinblick auf die mittlere Gewinnerwartung, bringen Systemspiele keinerlei Vorteile gegenüber gleichvielen zufälligen Einzeltipps. Anders sieht es dagegen mit der Wahrscheinlichkeit überhaupt etwas zu gewinnen aus. Bei Wahl eines der offiziellen Lotto-Systemspiele, ist die Gewinnchance sogar signifikant schlechter! Aber auch bei den hier betrachteten Lotto Designs von 6aus45 und 6aus49 ist sie oft nur vergleichbar mit der gleichvieler Zufallstipps!

Erstfassung im Februar 2013

• Bibliographie
• Über dieses Dokument ...
• Über den Autor ...