DDR-Lotto [5 aus 35]

01.11.2007, 18:55

tigerbine

DDR-Lotto [5 aus 35]

In einer fröhlichen Runde Prost

wurde folgende Frage an mich herangetragen:

"Wie viele Scheine muss man spielen, um mit Sicherheit mindestens einen 3er zu haben?"

* 1 Schein == 1 Zahlenkombination

* Mit Sicherheit == einer Wahrscheinlichkeit von 1

Wie muss man denn da dran gehen?

LG,
tigerbine Wink

01.11.2007, 18:57

20_Cent

Auf diesen Beitrag antworten »

Ich würde den Worstcase berechnen: Anzahl der Möglichen Scheine mit keinem richtigen, Anzahl mit einer richtigen, Anzahl mit 2 richtigen. Wenn du die alle abgibst, und dann noch einen, dann muss mindestens einer 3 richtige haben.
mfG 20

03.11.2007, 12:34

tigerbine

Auf diesen Beitrag antworten »

Danke, und wie berechne ich diese Anzahlen? Erstaunt2

03.11.2007, 12:41

therisen

Auf diesen Beitrag antworten »

Das ist doch im Prinzip ein Bernoulli-Experiment. Bestimme daher zunächst die Wahrscheinlichkeit, mindestens 3 Richtige zu haben. "Günstige geteilt durch die Möglichen" (Laplace). Ich bezweifle allerdings sehr stark, dass du eine Wahrscheinlichkeit von 100% nach endlich vielen Spielen haben wirst.

Gruß, therisen

03.11.2007, 12:50

tigerbine

Auf diesen Beitrag antworten »

Ich fürchte, ich hab hier einen Knoten im Hirn. Denn ich bekomme es nicht hin, mit welchem System ich die Anzahl der "Günstigen" berechne.

Im Falle von 6 richtigen ist das ja einfach. Es gibt 5 aus 35 Möglichkeiten und einen günstigen Fall. Man müßte also 324.632 Scheine abgeben.

Im Falle von 0 richtigen, sollte man wohl um mit Sicherheit keinen Treffer zu haben, wohl keinen Schein abgeben.

Aber schon bei "mit Sicherheit mind. 1 Treffer" tue ich mich schwer. D.h. ich muss die Scheine so ausfüllen, dass ich alle Zahlen gespielt habe, aber so wenig wie möglich doppelt. Und das bekomme ich nicht hin.

03.11.2007, 12:52

20_Cent

Auf diesen Beitrag antworten »

Ich glaube so war das nicht gemeint.
Wenn man alle möglichen Kombinationen abgibt, dann hat man auf jeden Fall 5 richtige, einige Male 4 richtige, und noch mehr 3 richtige. (ich glaub sorum ists einfacher)
Im Prinzip muss man jetzt nur noch zählen, wie oft man 4 und 3 richtige hat, 5 richtige hat man ja nur einmal. 4 richtige müssten genau 5*30 mal vorkommen, denn die Reihenfolge ist egal, und man kann jede der 5 richtigen durch 30 andere ersetzen. (durch sich selbst ist sinnlos, und ebenso kann man nicht durch eine schon getippte zahl ersetzen)
3 richtige ist schon etwas schwieriger: Jeweils eine der 4 richtigen muss ausgetauscht werden, aber nicht so, dass zufällig wieder 4 richtige entstehen. also 5*30*4*29 würde ich sagen...

Jetzt zusammen addieren und von der Gesamtzahl abziehen, also von 35*34*33*32*31.

Ich hätte dann $\begin{eqnarray*} \frac{35!}{30!}-(1+5\cdot 30 + 5\cdot 30 \cdot 4 \cdot 29)=38938289 \end{eqnarray*}$ , kann aber gut auch falsch sein Augenzwinkern

03.11.2007, 16:48

Auf diesen Beitrag antworten »

Halten wir mal fest: Es geht also um eine Menge von strategisch ausgefüllten Scheinen für ein- und dieselbe Ziehung - ansonsten gilt therisens Einwand.

Nüchtern mathematisch kann man es so formulieren:

Zitat:

Sei $\begin{eqnarray*} \Omega=\{1,\ldots,35\} \end{eqnarray*}$ und $\begin{eqnarray*} U \end{eqnarray*}$ die Menge aller fünfelementigen Teilmengen von $\begin{eqnarray*} \Omega \end{eqnarray*}$ , d.h. es ist dann $\begin{eqnarray*} |U|=\binom{35}{5} \end{eqnarray*}$ .

Gesucht ist nun eine möglichst kleine Teilmenge $\begin{eqnarray*} V\subset U \end{eqnarray*}$ mit der Eigenschaft

$\begin{eqnarray*} \forall A\in U \quad \exists B\in V:\quad |A\cap B| \geq 3 \end{eqnarray*}$

Genauer habe ich noch nicht drüber nachgedacht, aber ich fürchte, es ist schwierigeres kombinatorisches Problem als bisher hier im Thread gedacht. verwirrt

03.11.2007, 16:57

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Halten wir mal fest: Es geht also um eine Menge von strategisch ausgefüllten Scheinen für ein- und dieselbe Ziehung - ansonsten gilt therisens Einwand.

Genau so ist es. Die Scheine werden apriori ausgefüllt und man will sicher sein, mindestens einen Dreier zu haben. Das eine Abgabe "mit Sicherheit" möglich ist, würde ich deswegen vermuten, weil man ja maximal alle 324.632 Scheine abgeben könnte.

Nun stellt sich die Frage, wenn man nicht auf den sicheren 5er besteht, ob man dann Tippscheine Einsparen kann. An einem kleineren Zahlenbeispiel habe ich das auch einmal versucht, konnte aber das System nicht übertragen.

Wenn Arthur aber schon sagt, das es komplizierter sein kann, dann habe ich ja Glück, dass ich nicht zu Prost

war, dass mir eine Einzeiler-Lösung nicht eingefallen ist. Pech aber auch, da es nun schwierig wird, die Scheinzahl zu bestimmen.

Über Hilfe würde ich mich freuen, und danke schon einmal für die bisherigen Ideen Wink

03.11.2007, 16:59

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Halten wir mal fest: Es geht also um eine Menge von strategisch ausgefüllten Scheinen für ein- und dieselbe Ziehung - ansonsten gilt therisens Einwand.

Ah, jetzt verstehe ich die Aufgabenstellung. Idee!

03.11.2007, 17:38

Auf diesen Beitrag antworten »

Untere Schranke für die Anzahl
Für ein konkretes $\begin{eqnarray*} B\in V \end{eqnarray*}$ gibt es

- genau ein $\begin{eqnarray*} A\in U \end{eqnarray*}$ mit $\begin{eqnarray*} |A\cap B|=5 \end{eqnarray*}$ (klar: A=B) ,
- genau $\begin{eqnarray*} \binom{5}{4}\cdot \binom{30}{1} = 150 \end{eqnarray*}$ Mengen $\begin{eqnarray*} A \end{eqnarray*}$ mit $\begin{eqnarray*} |A\cap B|=4 \end{eqnarray*}$ und
- genau $\begin{eqnarray*} \binom{5}{3}\cdot \binom{30}{2} = 4350 \end{eqnarray*}$ Mengen $\begin{eqnarray*} A \end{eqnarray*}$ mit $\begin{eqnarray*} |A\cap B|=3 \end{eqnarray*}$ .

D.h., ein $\begin{eqnarray*} B\in V \end{eqnarray*}$ kann 4501 Mengen aus $\begin{eqnarray*} U \end{eqnarray*}$ "abdecken". Damit ergibt sich die notwendige Abschätzung

$\begin{eqnarray*} |V| \geq \frac{|U|}{4501} = \frac{\binom{35}{5}}{4501} = 72.1 \end{eqnarray*}$ ,

also $\begin{eqnarray*} |V|\geq 73 \end{eqnarray*}$ . Das wird allerdings noch ziemlich grob sein, aber eine untere Schranke ist es immerhin.

Edit(DS): Ich *verschieb* mal in die HöMa.

05.11.2007, 01:48

20_Cent

Auf diesen Beitrag antworten »

Ok, ich gebs zu, ich hab keine Ahnung von Kombinatorik Augenzwinkern

Lag ja meilenweit daneben...

05.11.2007, 01:58

tigerbine

Auf diesen Beitrag antworten »

Ot
Dennoch danke für den Versuch... Wie lange würde es eigentlich dauern 324.632 Scheine von Hand zu schreiben...Zahlt Sehnenschäden die Kasse?

05.11.2007, 08:08

Auf diesen Beitrag antworten »

Nach der unteren geb ich mal noch eine obere Schranke an - um zu verdeutlichen, wieviel Arbeit da noch ansteht, wenn man den genauen Wert rauskriegen will. Augenzwinkern

Ich lass einfach zwei von den 35 Zahlen weg (z.B. 34 und 35). Aus den restlichen 33 Zahlen bilde ich sämtliche $\begin{eqnarray*} \binom{33}{3} \end{eqnarray*}$ Auswahlen von je 3 Zahlen und gebe diese als Tipps ab - die restlichen zwei Zahlen jedes Tipps seien beliebig gewählt. Dann habe ich unter den $\begin{eqnarray*} \binom{33}{3} = 5456 \end{eqnarray*}$ Tipps garantiert mindestens einen Dreier.

Folglich haben wir bisher $\begin{eqnarray*} 73 \leq |V| \leq 5456 \end{eqnarray*}$ , dieses Intervall sollte man schon noch etwas weiter einengen ... smile

07.11.2007, 14:04

tigerbine

Auf diesen Beitrag antworten »

Danke Dir Arthur,

mit dem Einengen muss ich dann mal überlegen. Wenn mir was einfällt, schreib ich es. Aber dank Dir habe ich ja schon mal etwas zum antworten. Prost

08.11.2007, 17:22

Auf diesen Beitrag antworten »

Ich hab mal ein wenig simuliert, und dadurch zumindest

$\begin{eqnarray*} |V| \leq 373 \end{eqnarray*}$

nachgewiesen, einfach indem ich eine solchen Systemtipp mit 373 Scheinen per Zufall und ein wenig Bruteforce generiert habe. Augenzwinkern

Die Methode ist eigentlich simpel: Generiere alle $\begin{eqnarray*} \binom{35}{5} = 324632 \end{eqnarray*}$ Tippscheine und greife einen davon als ersten Tipp des Systems heraus. Anschließend streiche alle 4501 "verwandten" Scheine aus der Menge aller 324632 Tipps heraus. Aus der verbliebenen Menge wähle man zufällig den zweiten Tipp des Systems heraus, streiche wieder die verwandten Scheine heraus, usw. solange überhaupt noch nicht gestrichene Tippscheine da sind.

Auf diese Weise erhält man einen brauchbaren Systemtipp, der allerdings in der Regel nicht optimal sein dürfte. Das sieht man schon daran, dass eine Wiederholung dieses Algorithmus (mit dann anderen Zufallsauswahlen) Systemtipps verschiedener Größe erzeugt:

379, 383, 374, 373, 378, ... smile

08.11.2007, 17:26

tigerbine

Auf diesen Beitrag antworten »

Und den Sprung von 5456 auf 373 nenne ich schon einmal beachtlich. Tanzen

08.11.2007, 20:20

Auf diesen Beitrag antworten »

So, wer unbedingt tippen möchte ... nunmehr genügen 370 Tippscheine. Dumm nur, dass diese Lottoform nicht mehr gespielt wird, aber für 6 aus 49 kann man sich natürlich ähnliches überlegen. Augenzwinkern

09.11.2007, 23:11

tigerbine

Auf diesen Beitrag antworten »

Der Programmierer...
der mir diese Aufgabe gestellt hat, ist nun wohl auch wieder so fit ( Prost

), dass er mir sein Ergebnis (ohne Programm) mitgeteilt hat: 336. Interessiert Dich sein Programm, oder kannst Du die Zahl gar unterbieten, Arthur?

Liebe Grüße,
tigerbine

10.11.2007, 13:13

Auf diesen Beitrag antworten »

Ist 336 der optimale Wert? Ein Beweis dafür würde mich schon interessieren, zumindest aber das Konstruktionsprinzip einer solchen Tippmenge.

10.11.2007, 18:30

tigerbine

Auf diesen Beitrag antworten »

Ob er optimal ist weiß ich nicht. Er hat was programmiert und das kam raus Augenzwinkern

Soll ich das Programm mal besorgen?

10.11.2007, 19:56

Tomtomtomtom

Auf diesen Beitrag antworten »

Das Problem eine scharfe Schranke anzugeben, ist schon bei wesentlich kleineren Zahlen als 3,5, und 35 verdammt schwer, wenn nicht unmöglich.

Praktisch kan man sich immer eine Algorithmus überlegen, der folgendermaßen abläuft:

Gegeben: Die Menge M aller möglichen 5-er Tipps.

Wiederhole
1.) wähle einen 5-er Tipp
2.) streiche aus M alle Tipps, bei denen man damit mindestens einen 3er erzielt
bis M leer ist.

Bei dem "wählen" kommt dann eine Heuristik ins Spiel.

Man kann etwa einen Tipp wählen, der aus der noch vorhandenen Menge M eine Maximalzahl von Elemente entfernt. Das ist aber rechnerisch aufwendig.

Oder man kann einen Tipp wählen, dessen Zahlen unter den bisher gewählten Tipps selten vorkamen.

Oder man welche Zahlen in den noch vorhandenen Elemente aus M wie oft vorkommen, und wählt den Tipp mit den 5 häufigsten Zahlen.

Oder, oder, oder...

Von einer solchen Strategie allerdings nachzuweisen, daß sie ideal ist, ist ziemlich hoffnungslos.

Wer googlen möchte findet Informationen unter dem Stichwort "Blockplan" und wer "Hardware" lieber mag, kann mal in Beutelspacher: Einführung in die endliche Geometrie reinschauen.

10.11.2007, 19:59

Auf diesen Beitrag antworten »

Zitat:

Original von Tomtomtomtom
Gegeben: Die Menge M aller möglichen 5-er Tipps.

Wiederhole
1.) wähle einen 5-er Tipp
2.) streiche aus M alle Tipps, bei denen man damit mindestens einen 3er erzielt
bis M leer ist.

Kommt mir bekannt vor. Aber ich lese auch nicht immer den ganzen Thread. Augenzwinkern

10.11.2007, 20:06

Tomtomtomtom

Auf diesen Beitrag antworten »

Ja ich habs auch gerade gemerkt. Sorry für die Wiederholung. Ich überlege gerade wie groß meine Chancen sind, den bisherigen Rekord zu unterbieten. wohl nicht so groß nehme ich an ^^

11.11.2007, 12:40

gast martin

Auf diesen Beitrag antworten »

hallo,
die wahrscheinlichkeit eine 3 zu haben ist

(5 über 3) x (30 über 2)
__________________________

35 über 5

jetzt hat man eine von den 324632 möglichkeiten getestet und für den nächsten schein bleiben
(35 über 5) - 1 möglichkeiten
und die formel lautet

(5 über 3) x ( (30 über 2) - 1)
_______________________________

(35 über 5) - 1

jetzt muss man die beiden addieren, den index erhöhen usw. bis man als summe >1 rauskriegt

(5 über 3) x ( (30 über 2) - 2)
_______________________________

(35 über 5) - 2

Das ganze geht mit der summenschreibweise

der index läuft von 0 bis 82, weil bei der 82 die 1 überschritten ist. dh 82 scheine ausfüllen.

das ist meine vermutung zu dem problem und
sorry für die komische schreibweise, hab keine ahnung von latex.

mfg martin

Neue Frage »

Antworten »

DDR-Lotto [5 aus 35]

Verwandte Themen