PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Kombinatorik-Rätsel


rene
16.08.07, 17:52
Folgendes aktuelles und sehr intelligentes Wettbewerbsrätsel gefunden:

Bei einer Professorenwahl werden – fast wie im „Basler System“ anno 1727 – die 12 Wahlberechtigten durch Auslosung in zwei Gruppen zu je sechs eingeteilt. Jede der Gruppen bestimmt mit einfachem Mehr einen Kandidaten; wenn innerhalb der Gruppe mehrere Kandidaten gleich viele Stimmen bekommen, wird zwischen ihnen gelost. Falls beide Gruppen für denselben Kandidaten votieren, ist er gewählt; falls sie verschiedene Kandidaten vorschlagen, entscheidet zwischen ihnen das Los. Man weiss, dass von den zwölf Wahlberechtigten sieben für Ben, einer für Dan und vier für Leo sind. Wie gross ist Leos Chance, zum Professor gewählt zu werden.

Die Lösung könnt ihr hierher posten (eine Zahl genügt vorerst) – oder per privater Nachricht –, wie ihr wollt. Nach 14 Tagen werde ich die Lösung und den Lösungsweg veröffentlichen.

Grüsse, rene

first_g_a
16.08.07, 21:46
Die Lösung könnt ihr hierher posten (eine Zahl genügt vorerst)

Nur eine Zahl? Und was ist mit eine Ziffer?:confused:

Ist null ne Zahl??:confused:

rene
16.08.07, 23:17
Nur eine Zahl? Und was ist mit eine Ziffer?:confused:

Ist null ne Zahl??:confused:

Ist etwa 1234 (eintausendzweihundertvierunddreissig) keine aus 4 Ziffern bestehende Zahl?

Gefragt ist - um spitzfindigen Antworten entgegenzuwirken - nach der Wahrscheinlichkeit, mit der Leo zum Professor gewählt wird. Ob als Prozentangabe oder als Verhältniszahl zur Totalwahrscheinlichkeit 1 (eins) spielt keine Rolle.

Grüsse, rene

first_g_a
16.08.07, 23:39
Ist etwa 1234 (eintausendzweihundertvierunddreissig) keine aus 4 Ziffern bestehende Zahl?

Gefragt ist - um spitzfindigen Antworten entgegenzuwirken - nach der Wahrscheinlichkeit, mit der Leo zum Professor gewählt wird. Ob als Prozentangabe oder als Verhältniszahl zur Totalwahrscheinlichkeit 1 (eins) spielt keine Rolle.

Grüsse, rene
Achsorene..dankerene.

Dann schreib ich mal ->(0)<- als Zahl und Ziffer.:D

rene
16.08.07, 23:55
Achsorene..dankerene.

Dann schreib ich mal ->(0)<- als Zahl und Ziffer.:D

Danke für deinen Lösungsvorschlag. Leider falsch!

Nicht aufgeben, rene

Marco Polo
17.08.07, 00:12
Zur Info:

Es gibt 10 verschiedene Möglichkeiten der Gruppenauslosung.
Ben=B Dan=D Leo=L

1.
Gruppe A: 6xB
Gruppe B: 1xB;1xD;4xL
2.
Gruppe A: 5xB;1xD
Gruppe B: 4xL;2xB
3.
Gruppe A: 5xB;1xL
Gruppe B: 3xL;1xD;2xB
4.
Gruppe A: 4xB;1xD;1xL
Gruppe B: 3xB;3xL
5.
Gruppe A: 4xB;2xL
Gruppe B: 3xB;2xL;1xD

Für die restlichen 5 Möglichkeiten muss man nur die Gruppen A und B vertauschen. Bei Punkt 4 Gruppe B und analog dazu Punkt 8 Gruppe A muss zwischen B und L ausgelost werden.

Ausserdem wäre bei Punkt 5 und analog dazu Punkt 10 B direkt gewählt.

Soweit erst mal richtig?

Marco Polo
17.08.07, 00:25
Ich komme auf 35 Prozent Gewinnchance für Leo. Bestimmt falsch oder?

rene
17.08.07, 00:34
Ich komme auf 35 Prozent Gewinnchance für Leo. Bestimmt falsch oder?

Ja, leider auch falsch. Die Gruppeneinteilungen sind richtig. Es gibt insgesamt bloss 5 verschiedene Kombinationen der 2 Gruppen. Jedoch unterscheiden sich ihre Häufigkeiten und somit die Wahrscheinlichkeiten dieser 5 Kombinationen.

Wenn du willst kann ich dir die Lösung per privater Nachricht zukommen lassen - oder du willst noch ein bisschen weiter daran knobeln...

Danke dass ihr euch dessen annehmt!, rene

Marco Polo
17.08.07, 00:48
Ja, leider auch falsch.

Grmbl...

Es gibt insgesamt bloss 5 verschiedene Kombinationen der 2 Gruppen.

Genau. Ich hatte zwar 10 angegeben, die weiteren 5 sind aber sysmmetrisch zu den ersten 5 und daher kann man von 5 ausgehen.

Leider habe ich mich noch nie mit Wahrscheinlichkeitsrechnung befasst. Ich war davon ausgegangen, dass alle 5 Kombinationen gleich wahrscheinlich sind. Ein Trugschluss.

Grüssle,

Marco Polo

richy
17.08.07, 02:57
Hi
Marco Polos Vorarbeit ist ja schon sehr viel Wert.
Fuer die waere ich zu faul gewesen, aber da knuepfe ich mal an.
Muss man tatsaechlich beruecksichtigen, dass jede Gruppierung durch verschiedene Individuen repraesetiert wird ?
Dann wuerde ich vermuten, dass dies nur Bedeutung hat, wenn ein Kandidat
in beiden Wahlgruppen A,B vorkommt.
Beispiel:

1.
***
Gruppe A: B2,B3,B4,B5,B6,B7
Gruppe B: B1;1xD;4xL

Gruppe A: B1,B3,B4,B5,B6,B7
Gruppe B: B2;1xD;4xL

Gruppe A: B1,B2,B4,B5,B6,B7
Gruppe B: B3;1xD;4xL
e.t.c
Hier gaebe es dann also 7 Moeglichkeiten
M=7

2.
***
Gruppe A: 5xB;1xD
Gruppe B: 4xL;2xB,
Anhand Gruppe B:
(B1,B2),(B1,B3) .... 6 Moeglichkeiten
(B2,B3),(B2,B4) .... 5 Moeglichkeiten ... etc

6+5+4+3+2+1=21 Moeglichkeiten
oder kuerzer 7 ueber 2 = 7!/5!/2! = 6*7/2=3*7=21
M=21

3.
***
Gruppe A: 5xB;1xL
Gruppe B: 3xL;1xD;2xB
B und L ueberlappen sich
An der Stelle koennte ich falsch liegen (grad zu faul zum Nachdenken) :
B: 7 ueber 2 = 21
L: Anhand Gruppe A koennen das nur 4 L Moeglichkeiten sein
Man kann 4 aber auch vornehm als 4 ueber 1 bezeichnen :-).
Und das muss ich wohl multiplizieren: 84 Moeglichkeiten ? Huch so viel ?
M=84

4.
Gruppe A: 4xB;1xD;1xL
Gruppe B: 3xB;3xL
Auch hier wieder Denkfaul :
7 ueber 3 = 7!/4!/3! = 5*6*7/(2*3)=5*7=35
Das wieder mal 4, 4*35=140
M=140


5.
Gruppe A: 4xB;2xL
Gruppe B: 3xB;2xL;1xD
Puh ....
(7 ueber 3) mal (4 ueber 2) ? Das waere ja irre viel :-)
35* 4!/2!/2! = 35*3*4/2=35*6=210
M=210

Nun fleissig addieren :-)
7+21+84+140+210=462 (addieren ist net meine Staerke)
Die jeweilige Gruppierungswahrscheinlichkeit waere dann M/462

Nun guggen wo Leo gewinnt

1.
Gruppe A: 6xB
Gruppe B: 1xB;1xD;4xL LOS 1/2
M=7
2.
Gruppe A: 5xB;1xD LOS 1/2
Gruppe B: 4xL;2xB
M=21
3.
Gruppe A: 5xB;1xL LOS 1/2
Gruppe B: 3xL;1xD;2xB
M=84
4.
Gruppe a: 4xB;1xD;1xL
Gruppe b: 3xB;3xL
Falls das LOS innerhalb Gruppe b=B dann ist B direkt gewaehlt
Falls das LOS innerhalb Gruppe b=L enstscheidet das LOS beider Gruppen a,b
Die Chance fuer B direkt gewaehlt zu werden ist somit 1/2
Dazu nochmal die Chance 1/2 von der Nicht Direktwahl 1/2
also (1/2*1/2) macht zusammen 1/2+1/4=3/4
Bleiben fuer den armen Leo 1/4
M=140
5.
Gruppe A: 4xB;2xL
Gruppe B: 3xB;2xL;1xD B direkt
M=210

Summe aller Moeglichkeiten war 462

Sodele
Leo hat die Chance
(1/2*7+1/2*21+1/2*84+1/4*140)/462=13/66=0.1969

Kann um die Uhrzeit ja nur falsch sein :-)
Sorry das ich es angepinselt habe, aber ich hatte kein Blatt Papier zur Hand.

Ich bin mir aber recht sicher, dass Dan nicht Professor wird.
Frage mich dazu : Warum mag den keiner und welche Rolle spielt der in der Rechnung ?

rene
17.08.07, 22:57
Hi richy

Leider auch nicht richtig.

Kleine Hilfe: Wie berechnest du die Totalwahrscheinlichkeit, in max. drei Versuchen mit einem Würfel eine "Sechs" zu würfeln?

Grüsse, rene

richy
18.08.07, 01:27
Hi rene

Wie berechnest du die Totalwahrscheinlichkeit, in max. drei Versuchen mit einem Würfel eine "Sechs" zu würfeln?


1-drei mal keine sechs zu wuerfeln ?
drei mal keine sechs waere
5/6*5/6*5/6=125/216
1-125/216=91/216=0.421

Der Ansatz mit den Kombinationen war also falsch ?
Haette ich zunaechst fragen sollen und nicht gleich losrechnen.
Aber rein intuitiv, also wenn ich den Kandidaten b1,b2,b3 ...aufs Hemd male
schien mir das naehliegen.
Meine Wahrscheinlichkeiten der Gruppierungen sind also alle falsch ?

Im Moment stehe ich auch auf dem Schlauch mit der Hilfsfrage.
Na gut dann knoble ich mal weiter :-)
ciao

rene
18.08.07, 01:45
Hi rene


1-drei mal keine sechs zu wuerfeln ?
drei mal keine sechs waere
5/6*5/6*5/6=125/216
1-125/216=91/216=0.421

Genau.

Der Ansatz mit den Kombinationen war also falsch ?

Der Ansatz ist richtig. Wenn du nun die aus der hypergeometrischen Verteilung gewonnenen Einzelwahrscheinlichkeiten aus jeder Kombination für Leos Wahl wie oben im Würfelbeispiel berechnest, sollte das richtige Resultat herauskommen!

Ich war sehr überrascht, dass du den vergleichsweise schwierigen Teil meisterste, jedoch den leichteren Teil nicht.

Grüsse, rene

richy
18.08.07, 03:10
Hi rene
Ah, ich glaube mir daemmert es.
Leo wird nicht Prof wenn der oder der oder der Fall eintritt, sondern
der und der und der Fall nicht eintritt.
Addition von Wahrscheinlichkeiten ist meist verhaengnisvoll.
Manno dabei weiss ich das doch.

Ich finde den Raetselteil nicht wesentlich einfacher als die anderen Teile.
Man tappt hier doch schon leicht in die Falle.
Und die Berechnung der Kombinationen ist ja eher eine Fleissarbeit.

Die endgueltige Loesung ueberlasse ich mal den anderen Knoblern hier.
Dann haetten wir das gesamte Raetsel im dreier Team geloest.
Und Teamarbeit ist ja angesagt.

Hier nochmal das Zwischenresultat :

1)
Wahrscheinlichkeit der Gruppierung 7/462
Gewinnchance Ben :1/2
Gewinnchance Leo :1/2

2)
Wahrscheinlichkeit der Gruppierung 21/462
Gewinnchance Ben :1/2
Gewinnchance Leo :1/2

3)
Wahrscheinlichkeit der Gruppierung 84/462
Gewinnchance Ben :1/2
Gewinnchance Leo :1/2

4)
Wahrscheinlichkeit der Gruppierung 140/462
Gewinnchance Ben :3/4
Gewinnchance Leo :1/4

5)
Wahrscheinlichkeit der Gruppierung 210/462
Gewinnchance Ben : 1
Gewinnchance Leo : 0

Viele Gruesse
richy

Marco Polo
20.08.07, 23:55
Hi rene,

da ich mit hypergeometrischen Verteilungen bisher keine Bekanntschaft gemacht habe, wäre ich dir dankbar, mir die Lösung als PN zukommen zu lassen. Bin gespannt, ob Dan dabei eine Rolle spielt. Eigentlich müsste seine Chance bei Null liegen, oder?

Grüssle,

Marco Polo

richy
21.08.07, 17:32
@Marco Polo

Dan spielt keine Rolle.
Die Hypergeometrische Verteilung ist nichts weiter als der Binominalkoeffizient.
Findest du auch im Pascalschen Dreieck. Hier schlummert sicherlich noch ein Puzzelstueck :-)
Die Zwischenloesung habe ich bischen schlampig angeschrieben. Eine ordentliche Darstellung waere in der Tat sinnvoll.
Das Raetsel solltest du jetzt mit der Zwischenloesung und renes Hilfskommentar loesen koennen.
p=1-na ?
ciao

rene
21.08.07, 20:21
Genau, richy. Die Hypergeometrische Verteilung ist nichts anderes als eine Verkettung von Binominalkoeffizienten mit n über k Parameter, deren Kombinationen jeder Teilmenge aus der Grundmenge multipliziert und ins Verhältnis zur Anzahl aller Kombinationen der Grundmenge gesetzt werden. Ich bringe das Erläuterungsbeispiel, das ich heute Morgen an Marco Polo per PN geschickt habe:

Aus einer Urne mit 5 roten, 3 blauen und 2 weissen Kugeln sollen 5 Kugeln zufällig ohne zurücklegen gezogen werden.
Es werden 3 rote, 1 blaue und 1 weisse Kugel gezogen:

p = (5 über 3) * (3 über 1) * (2 über 1) / (10 über 5)
p = 10 * 3 * 2 / 252 = 0.238

mit den Binominalkoeffizienten (n über k) = n! / (k! * (n-k)!)

Grüsse, rene

richy
21.08.07, 21:58
Hi rene MP
Die Kombinatorik ist ueberhaupt wichtigster Teil der Wahrscheinlichkeitstheorie.
Eine Wahrscheinlichkeit berechnet sich ja immer ueber der Anzahl der "guenstigen" Falle / allen Faellen. Und die Anzahl der Faelle ergibt sich eben aus Ueberlegungen der Kombinatorik. In meiner Studienzeit fiel mir dieses Thema immer schwer, denn es ist eine Thematik die nicht zu unserem evolutionaeren Erfahrungsraum gehoert. Man verschaetzt sich hier nur allzuleicht.

Dementsprechend hatte ich auch einen Merkzettel mit Beispielen zur Kombinatorik.
Eine gute Morglichkeit ist es auch zunaechst experimentell (Blatt Papier) das Prinzip der Moeglichkeiten zu erkennen. Aber statt alle Faelle durchzuspielen, geht man dann ueber in die allgemeine Formulierung. Das spart Unmengen von Papier, bedarf aber etwas Erfahrung.

Ein schoenes einfachstes Beispiel ist die Frage nach der Wahrscheinlichkeit eines Sechsers im Lotto.
(Eine natueliche Herleitung des Binominalkoeffizienten)
****************************************
Ausgangspunkt :
Ich habe sechs Kugeln (Chancen) auf meinem Lottoschein getippt, im Ziehungsgeraet liegen 49 Kugeln.

1.Ziehung
*******
49 Moeglichkeiten gibt es. 6 sind fuer mich guenstig :
p1=6/49

2.Ziehung.
********
Es verbleiben noch 48 Kugeln im Geraet. Also 48 Moeglichkeiten.
Da ich einen 6-er tippen will, wurde auch eine meiner Tippzahlen bereits
in der ersten Ziehung "verbraucht". 5 stehen mir noch zur Verfuegung.
Die Wahrscheinlichkeit in der zweiten Ziehung ist somit :
p2=5/48

Und jetzt sollte man das Prinzip schon erkannt haben:
p1=6/49
p2=5/48
pn=(6-n+1)/(49-n+1)

Damit ich einen 6 er getippt habe muessen diese Wahrscheinlichkeiten sequenziell a priori erfuellt werden. Man merke sich einfach, dass die Wahrscheinlichkeiten dann miteinander multipliziert werden:

Einschub:
Die Wahrscheinlichkeit zweimal hintereinander a priorio eine 3 zu wuerfeln ist auch 1/6*1/6. Man sieht schoen. Habe ich bereits eine 3 gewuerfelt ist die Wahrscheinlichkeit 1/6. Das nennt man a posterio.
Und erklaert, warum es zwecklos ist beim Roulette zu warten bis oftmals rot gefallen ist und dann schwarz zu setzen :-)

a) p(sechser) = p1*p2..p6 = 6/49*5/48*4/47*3/46*2/45*1/44
b) p(sechser) = 1/13983816 etwa eins zu 14 Millionen

Wie kann man Ausdruck b noch beschreiben ?
Im Zaehler steht Z= 1*2*3*4*5*6 = 6! (sechs Fakultaet, gebongt :-)
Im Nenner steht N= 49*48*47*46*45*44
Das sind 6 Elemente, Zahlen.
49 ! waere 49*48*47*46*45*44*(43*42*41 ....2*1)
Wenn ich 49 ! mit 43 ! kuerze erhielte ich genau N
Warum 43 ! ? Weil 6 Elemente vorkommen. Es ist somit klar :
N=49 ! / (49-6) !

Die Chance einen Sechser zu Tippen ist somit Z / N = 6!*(49-6)! / 49!
( Ein 3 er ist weitaus schwieriger zu berechnen, aber )

Dieser Ausdruck sollte einem bekannt vorkommen. Es ist der Kehrwert des
Binominalkoeffizienten (6 ueber 49) (6|49) also (49 ueber 6) (49|6)
http://de.wikipedia.org/wiki/Binomialkoeffizient
Das Pascalsche Dreieck laesst also auch beim Lotto Gruessen :-)

JGC reduziert seine Weltanschauung meist auf eine longitudinale Welle :-)
Wie kann ich jetzt also meine belaechelten Parallelwelten, G4 Hintergrundraum,
informatorische, organistaorische Kanaele,morphologische Felder und Burkhard Heims
sechsdimensionalen Hyperraum (meine Welt) hier noch einbringen ?
Zum Beispiel in der Form :
( Tatsaechlich eine gute Uebung zur Kombinatorik )
**************************************
Lassen wir Herrn Heim beiseite und betrachten "einfach" mal einen sechsdimensionalen Hyperwuerfel. Was ein Wuerfel ist solte bekannt sein. Der hat 6 Seitenflaechen.
god does not play dice !
Naja lassen wir ihn mal mit einem 6-D Hyperwuerfel das Spiel spielen.
Nennen wir die Seitenflaechen dieses Wuerfels METRON !

Aufgabe :
*******
Wieviele Seitenflaechen (METRONEN) hat ein sechdimensionaler Hyperwuerfel ?

Loesungsvorschlag : (ueber Bitcodierung der Seitenflaechen)
***************
( Topic kann man zu (i) springen.)

Ein D Dimensionaler Einheits Wuerfel besteht aus 2 hoch D Eckpunkten
Bsp: 3 Dimensional

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Enstpricht also genau der binaeren Codierung von 2 hoch D Zahlen
Dementsprechend besitzt ein Quadrat auch 2 ** 2 Ecken

Bsp: Flaechen eines 3 D Wuerfels
000 100 001 000 000 010
010 101 101 010 100 011
110 110 111 011 001 111
100 111 011 001 101 110

Man sieht: Bei der Flaeche eines 3 D Wuerfels definiert ueber dessen Ecken,
nimmt eine Dimension einen festen Wert 0/1 an. Dies kennzeichnet die Lage
der Flaeche. Waehrend die anderen Werte "variieren" 00 01 10 11
Das sind die Ecken des Quadrats
Jedes Variationspaar liefert 2**D/2**d =2**(D-d) Objekte.

************************************************** *****
JETZT KOMMT DER BINOMINALKOEFFIZIENT WIE BEI RENES RAETSEL INS SPIEL :
************************************************** ****
(i)
Wieviel Variationspaare gibt es ?
Beispiel D=4 d=2, v kennzeichnet die variierte Dimension
vv__
v_v_
v__v
_vv_
_v_v
__vv
Das ist die Kombination von d Elementen in D. Somit gibt es D ueber d
Variationspaare.
Ein D-dimensionaler Koerper besitzt also n,gemaess folgender Formel, d-dimensionale Raender:
*********************
n=D!/d!/(D-d)!*2^(D-d)
*********************
Damit besitzt ein 6 D Hyperwuerfel 240 Seitenflaechen !
*****************************************

Interessant ist hier die Variation, die auch in renes Raetsel auftritt :

2.
***
Gruppe A: 5xB;1xD
Gruppe B: 4xL;2xB,
Anhand Gruppe B:
(B1,B2),(B1,B3) .... 6 Moeglichkeiten
(B2,B3),(B2,B4) .... 5 Moeglichkeiten ... etc

6+5+4+3+2+1=21 Moeglichkeiten
oder kuerzer 7 ueber 2 = 7!/5!/2! = 6*7/2=3*7=21
M=21


Das ist die Struktur die zur Variation fuehrt.
Fuer Coder,Informatiker :

Schleife 1, a1 festhalten :
(a1,a2) (a1,a3) ... (a1,an)
Schleife 2, a2 festhalten :
(a2,a3) (a2,a4) ... (a2,an)
etc, weiter innere Scheife :
(a3,a4) (a3,a4) ... (a3,an)
....
(a(n-1),a(n))

Erkennt man diese Struktur, kann man sofort den Binominalkoeffizienten anschreiben.


@Marco
renes Raetsel ist noch nicht geloest ! :-)

Marco Polo
21.08.07, 23:36
@Marco
renes Raetsel ist noch nicht geloest ! :-)

Äh, :o , leider habe ich mir die Lösung schon von rene schicken lassen.

Das Beispiel mit der Urne war besonders einleuchtend. Hatte das mit n über k nicht kapiert. In einem Mathebuch stand: n über k = n!/(k!(n-k)!

dabei muss es doch für n über k heissen:

(n*(n-1)*(n-2)*...*(n-k+1))/k!

übrigens: toll erklärt mit dem Lotto

Grüssle,

Marco Polo

rene
22.08.07, 00:03
Hi

Lotto 6 aus 49:
Anzahl Komb: (49,6) = 13'983'816

Anzahl Komb. für 6 Richtige: (6,6)*(43,0) = 1
Anzahl Komb. für 5+ Richtige: (6,5)*(42,0) = 6
Anzahl Komb. für 5 Richtige: (6,5)*(42,1) = 252
Anzahl Komb. für 4+ Richtige: (6,4)*(42,1) = 630
Anzahl Komb. für 4 Richtige: (6,4)*(42,2) = 12'915
Anzahl Komb. für 3 Richtige: (6,3)*(42,3) = 229'600
Anzahl Komb. für 2 Richtige: (6,2)*(42,4) = 1'678'950
Anzahl Komb. für 1 Richtige: (6,1)*(42,5) = 5'775'588

Grüsse, rene