Hutproblem "Rätsel" < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Ein Zauberer hat eine ganze Menge von Zwergen gefangen. Zum Spaß spielt er bevor er sie einsperren
will ein Spiel mit ihnen. Eine Runde läuft folgendermaßen ab:
Der Zauberer setzt jedem der Zwerge eine rote oder blaue Mütze auf, was er jeweils durch Münzwurf entscheidet. Die Zwerge können selbst nicht sehen, welche Mütze sie auf dem Kopf haben, jedoch die Mützen aller anderen Zwerge. Natürlich ist es ihnen verboten, den anderen in irgendeiner Art und Weise (Reden, Gesten, Bewegungen, etc.) mitzuteilen, was sie für eine Mütze auf dem Kopf haben und es gibt auch keine Hilfsmittel wie Spiegel, in denen sie sich sehen könnten. So bleibt ihnen wohl nur zu raten was für eine Farbe auf ihrem Kopf ist. Nun schreiben sie auf ihren Zettel verdeckt einen Tipp für die Farbe ihrer eigenen Mütze. Wenn alle fertig sind, decken sie gleichzeitig die Zettel auf und nur wenn alle Zwerge zusammen die richtige Lösung haben, gewinnen sie eine Runde, anderenfalls der Zauberer.
Das scheint ein ganz unfaires Spiel zu sein, da sind sich auch die Zwerge nach kurzer Besprechung sicher. Dennoch fällt ihnen eine Strategie ein, wie sie möglichst oft gewinnen können. Und tatsächlich schaffen sie es im Schnitt in jeder zweiten Runde zu gewinnen. Der Zauberer ist verblüfft und überzeugt, dass es sich um eine Art von Magie handelt und lässt die Zwerge deshalb nach einigen Runden frei.
Ist Ihnen klar, wie die Zwerge das gemacht haben? |
Hallo,
wir haben dieses nette "Rätsel" als Bonusaufgabe bekommen.
Leider habe ich absolut keine Idee wie ich das Anfange. Ich habe zwar eine Idee zur Lösung, aber ich weiß nicht wie ich die Korrektheit/Nicht-Korrektheit zeigen kann.
Ich dachte mir als mögliche Lösung, dass jeder Zwerg sich ansieht welche Farbe bei den anderen Zwergen insgesamt am häufigsten vorkommt, und dann die jeweils andere Farbe als Tip für sich selbst abgibt.
Mal ganz davon abgesehen, dass das auch irgendwie nicht so richtig klingt für mich, habe ich keinen anderen Vorschlag und weiß auch nicht wie ich den jetzigen überprüfen kann.
Ich habe natürlich nach dem Problem gesucht, bin aber nur auf andere Varianten davon getroffen (in denen es Reicht, wenn nur ein Ratender richtig liegt).
Würde mich sehr über etwas Hilfe/Tips/Anregungen freuen :)
Vielen Dank schon Mal.
Grüße
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:30 Di 21.12.2010 | | Autor: | statler |
Hi und ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Vielleicht so: Die Zwerge stellen sich in einer Reihe auf. Jeder schreibt die Farbe seines Vorgängers auf, dreht den Zettel um und schiebt ihn seinem Vordermann zu. Der letzte Zwerg rät einfach seine Farbe. Ist das erlaubt? Aber dann könnten sie sich natürlich auch gleich im Kreis aufstellen.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
Hallo,
so wie die Aufgabe gestellt ist, kann es m.E. nur eine Lösung geben.
Nicht genannt ist die Zahl der Zwerge, allerdings spricht die Angabe "eine ganze Menge" nicht für die folgende Lösung.
In der Tat ist die Idee, die Farben der anderen zu zählen und die etwa unterrepräsentierte für sich selbst zu raten, die einzig erfolgversprechende Strategie. Allerdings ist die Wahrscheinlichkeit ihres Erfolgs ja genau zu bestimmen und beträgt bei 4 Zwergen z.B. [mm] \bruch{6}{16}. [/mm] Diese Wahrscheinlichkeit sinkt mit wachsender Zahl von Zwergen.
Bei einer geraden Zahl von Zwergen kann jeder Zwerg eine klare Entscheidung nach der Regel treffen, weil die Zahl der Mützen, die er sieht, ja eine ungerade ist. So ist die genannte Wahrscheinlichkeit gerade die für eine gleiche Zahl roter und blauer Mützen, denn nur dann werden alle Zwerge richtig entscheiden.
Betrachten wir nun eine Runde von 3 Zwergen.
Fall 1) drei blaue Mützen: jeder Zwerg entscheidet falsch.
Fall 2) zwei blaue, eine rote Mütze: der mit der roten Mütze entscheidet richtig, die beiden mit den blauen können nur zufällig eine Farbe wählen, weil sie eine rote und eine blaue Mütze sehen. Die Wahrscheinlichkeit, dass beide richtig raten, liegt bei [mm] \tfrac{1}{4}.
[/mm]
Analog gehen auch die beiden noch fehlenden Fälle, eben nur mit vertauschten Farben. Die Gewinnquote liegt bei [mm] \bruch{3}{16}.
[/mm]
Bei nur 2 am Spiel beteiligten Zwergen wird die geforderte Wahrscheinlichkeit aber erreicht, wenn beide Zwerge eine der beiden folgenden Regeln stur verfolgen; allerdings müssen beide sich an die gleiche Regel halten:
a) Wenn der andere eine blaue Mütze hat, schreibe ich rot. Und umgekehrt.
b) Ich schreibe die gleiche Farbe auf, die mein Gegenüber aufhat.
Bei beiden Regeln gilt: die Erfolgswahrscheinlichkeit beträgt [mm] \bruch{1}{2}.
[/mm]
Womit auch die Zahl der Zwerge geklärt wäre...
Grüße
reverend
|
|
|
| |
|
Erstmal Danke für die bisherigen Antworten :)
Zu der Lösung mit dem Zuschieben: Nein, das ist natürlich nicht erlaubt ^^.
Zu reverend:
Das Problem ist genau das was du erwähnt hast. Mit "einer ganzen Menge" von Zwergen funktioniert es nicht mehr in der gewollten Wahrscheinlichkeit.
Außerdem habe ich mir vorhin von einem Kommilitonen sagen lassen, dass einer der Tutoren meinte, der "naive" Ansatz einfach die Farbe zu wählen, die insgesamt weniger vorkommt, würde nicht zur Lösung führen.
Also ich bin da jetzt absolut Ahnungslos :D
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:22 Di 21.12.2010 | | Autor: | reverend |
Hallo nochmal,
dann poste doch bitte die Lösung, wenn Ihr die Aufgabe besprochen habt.
Ich finde in der Formulierung der Aufgabe keinen eingebauten "Haken", den man für eine kreative Regeldeutung nutzen könnte. Fraglich ist ja schon, wie sich denn die Zwerge überhaupt auf eine Strategie einigen sollen.
Und "naiver Ansatz" ist ja auch 'ne coole Formulierung.
Insgesamt geht es natürlich um bedingte Wahrscheinlichkeiten. Wie man aber eine 50%ige Gewinnchance begründen soll, ist auch mir absolut schleierhaft.
Grüße
reverend
|
|
|
| |
|
Lösung werde ich posten sobald ich sie habe (falls nicht jemand anderes hier aus dem Forum noch eine Idee hat).
Wenn unsere Tutoren "naiver Ansatz" sagen, meinen sie damit die offensichtlichste der möglichen Ansätze. Ist also nicht abwertend gemeint (hoffe ich doch, sonst muss ich mich da Mal beschweren) ;)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:08 Di 21.12.2010 | | Autor: | statler |
Hallo,
ist es denn den Zwergen möglich, ihre Anzahl zu bestimmen? Dann schlage ich folgende Vorgehensweise vor: Bei einer geraden Anzahl wird die Anzahl der roten Mützen auf 'gerade' gebracht und damit natürlich die der blauen auch.
Falls wirklich #rot = #blau = gerade, machen es alle Zwerge richtig, falls nicht, machen es alle falsch.
Bei einer ungeraden Anzahl wird die Anzahl der roten Mützen auf 'ungerade' gebracht - mit ähnlichem Ergebnis. Oder?
Ich danke dem reverend für den Hinweis auf die Parität.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:26 Di 21.12.2010 | | Autor: | reverend |
Hallo Dieter,
ja, das ist es. Sehr gute Idee!
Das klappt aber nur bei einer geraden Anzahl von Zwergen, dafür da zuverlässig.
Bei einer ungeraden Anzahl von Zwergen sieht jeder Zwerg eine gerade Zahl von Mützen, also entweder blau und rot gerade, oder beide ungerade. In beiden Fällen kann er nicht entscheiden.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:36 Di 21.12.2010 | | Autor: | statler |
Hallo!
> ja, das ist es. Sehr gute Idee!
> Das klappt aber nur bei einer geraden Anzahl von Zwergen,
> dafür da zuverlässig.
>
> Bei einer ungeraden Anzahl von Zwergen sieht jeder Zwerg
> eine gerade Zahl von Mützen, also entweder blau und rot
> gerade, oder beide ungerade. In beiden Fällen kann er
> nicht entscheiden.
Doch kann er. Die Strategie ist doch, rot auf ungerade zu bringen bzw. wenn es das schon ist, es zu lassen wie es ist.
11 Zwerge, 6 x blau 5 x rot: Die roten Zwerge sehen 4 x rot, schreiben also rot auf. Die blauen sehen 5 x rot, schreiben also blau auf.
Gruß
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:40 Di 21.12.2010 | | Autor: | reverend |
> Doch kann er. Die Strategie ist doch, rot auf ungerade zu
> bringen bzw. wenn es das schon ist, es zu lassen wie es
> ist.
> 11 Zwerge, 6 x blau 5 x rot: Die roten Zwerge sehen 4 x
> rot, schreiben also rot auf. Die blauen sehen 5 x rot,
> schreiben also blau auf.
Ach so. Stimmt. Auch dann haben entweder alle zugleich recht, oder alle liegen falsch. Mehr wollten wir ja nicht.
Wie gesagt: schöne Idee!
|
|
|
| |
|
Das ganze funktioniert aber nicht mit Erfolgswahrscheinlichkeit 1/2.
Denn wenn es zb. eine gerade Anzahl Zwerge ist, ist die W'keit dass #blau = #rot eben nicht 1/2, wie reverend selbst ja schon oben angemerkt hatte (bei 4 zwergen nur wahrscheinlichkeit 6/16).
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:07 Di 21.12.2010 | | Autor: | statler |
Hallo!
> Das ganze funktioniert aber nicht mit
> Erfolgswahrscheinlichkeit 1/2.
Doch, das funzt!
> Denn wenn es zb. eine gerade Anzahl Zwerge ist, ist die
> W'keit dass #blau = #rot eben nicht 1/2, wie reverend
> selbst ja schon oben angemerkt hatte (bei 4 zwergen nur
> wahrscheinlichkeit 6/16).
Die wirkliche Verteilung der blauen und roten Mützen spielt überhaupt keine Rolle. Geh mal ein konkretes Beispiel durch. Nach der Regel von der totalen Wahrscheinlichkeit ist bei dieser Strategie
P(alle richtig) = 1 x P(gerade, gerade) + 0 x P(ungerade, ungerade). Es geht nicht um P(rot = blau).
Gruß
Dieter
|
|
|
| |
|
Ok, sorry.
Jetzt hab ich es doch tatsächlich auch verstanden.
Vielen Dank :)
|
|
|
| |
|
Hallo dasmussaberstimmen,
man sollte zuerst immer passenden Wahrscheinlichkeitsräme [mm] $\{\Omega, \mathcal{P}(\Omega), P\}$ [/mm] modellieren, um falscher Intuition vorzubeugen. Falls also folgende Modellierung nicht der Intention des Aufgabenstellers entspricht, ist natürlich das Modell entsprechend zu verändern.
Folgendes Modell für die Mützenvergabe scheint mir sinnvoll:
[mm] $\Omega [/mm] = [mm] \{0,1\}^{N}$, [/mm] $N = [mm] \{1,\ldots,n\},\; [/mm] n [mm] \geq [/mm] 1$
$N$ ist die Menge der Zwerge, $0$ ist eine rote, $1$ eine blaue Mütze.
$P$ ist das Wahrscheinlichkeitsmaß auf [mm] $\{0,1\}^N$ [/mm] mit
$P(A) = [mm] \frac{|A|}{|\Omega |}$ [/mm] für $A [mm] \subseteq \{0,1\}^N$
[/mm]
Wir nehmen jetzt an, dass durch die Mützenvergabe das Ereignis $E [mm] \subseteq \{0,1\}^{N}$ [/mm] eingetreten ist.
Jetzt müssen wir noch das Raten der Zwerge modellieren:
Die dem Zwerg $i$ zugängliche Information, bevor er den Zettel beschreibt, ist die Einschränkung
[mm] $e|_{N\backslash \{i\}}: {N\backslash \{i\}} \rightarrow \{0,1\}$ [/mm]
des Elementes des eingetretenen Ereignisses $E = [mm] \{e\}$ [/mm] auf [mm] $N\backslash \{i\}$
[/mm]
Jetzt wird gemeinsam ein Ergebnis $E' = [mm] \{e'\}$ [/mm] geraten.
Rät jeder Zwerg ohne Strategie (Münzwurfmodell), so ist die Wahrscheinlichkeit dafür, dass $E = E'$ gilt, gleich $P(E) = P(E') = [mm] 2^{-n}$.
[/mm]
Setzen wir aber
$e'(i) = [mm] g_i(e|_{N\backslash \{i\}})$ [/mm] für alle $i [mm] \in [/mm] N$,
wobei [mm] $g_i: \{0,1\}^{N\backslash \{i\}}\rightarrow \{0,1\}$ [/mm] eine geeignete Abbildung (Eigenschaft von [mm] $e|_{N\backslash \{i\}}$) [/mm] darstellt, so gilt:
$P(E' = E) = [mm] \frac{1}{2}$.
[/mm]
Die Zwerge haben solche Abbildungen [mm] $g_i$ [/mm] gefunden!
Ich verrate aber noch nichts, da ich Dir den Spaß nicht verderben will!
LG mathfunnel
|
|
|
| |
|
Wow, vielen Dank für die ausführliche Modellierung.
Dann schau ich mir das doch Mal an :)
|
|
|
| |
|
| Aufgabe | | die gleiche wie die Erste. |
Ich hab' leider nicht herausgefunden wie man den Status auf offen/teilweise beantwortet setzt, deswegen hab ich es so gemacht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:06 Di 21.12.2010 | | Autor: | mathfunnel |
Hallo dasmussaberstimmen,
heißt das, dass ich Dir das Ergebnis verraten soll?
LG mathfunnel
|
|
|
| |
|
Also die Lösung ist wohl klar (siehe meine erste Antwort und auch statler und reverend).
Hier etwas formaler:
[mm] $g_i(e|_{N\backslash \{i\}}) [/mm] = [mm] (\sum\limits_{j \in N\backslash \{i\}} e(j))\; \text{mod}\; [/mm] 2 $
Ist die Anzahl sämtlicher blauen Mützen gerade, so ist [mm] $g_i(e|_{N\backslash \{i\}}) [/mm] = 1$ für $e(i) = 1$, sonst $0$. Für das Ereignis
$S = [mm] \{\omega \in \Omega | (\sum\limits_{j \in N} \omega(j))\; \text{mod}\; 2 = 0\}$ [/mm] gilt
$P(S) = [mm] \frac{1}{2}$ [/mm] und $e' = e$, falls $e [mm] \in [/mm] S$.
LG mathfunnel
|
|
|
| |
|
Hab es nun dank eurer Erläuterungen verstanden :)
Großes Danke für die detaillierte formale Beschreibung.
|
|
|
|
