Die Mathe-Redaktion - 23.06.2018 04:26 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 113 Gäste und 3 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » Geschenk im Stuhlkreis
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Geschenk im Stuhlkreis
Tobi92sr
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.12.2016
Mitteilungen: 77
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-06-12 17:30


Hi, ich habe folgendes Rätsel gefunden und denke habe die Lösung, kann sie jedoch nicht beweisen.

Zehn Personen sitzen im Kreis an einem Tisch. Person 1 hat ein Geschenk in der Hand. Sie gibt dieses Geschenk zufällig nach links oder rechts weiter, mit gleicher Wahrscheinlichkeit. Beispielsweise wirft sie eine Münze und gibt dieses Geschenk bei "Zahl" nach links und bei "Kopf" nach rechts. Die nächste Person wiederholt die Prozedur, reicht es also mit gleicher Wahrscheinlichkeit nach rechts oder links weiter. Dies wiederholt sich so lange, bis schließlich nur noch eine Person übrig ist, die das Geschenk noch nicht in der Hand hatte. Diese Person erhält das Geschenk und darf es behalten. Wo muss man sich idealerweise platzieren, um mit höchster Wahrscheinlichkeit das Geschenk zu erhalten?

Meine Vermutung ist direkt gegenüber von Person 1. Diese Lösung erscheint intuitiv richtig. Jedoch weiß ich nicht, wie man das bestätigt ohne die Wahrscheinlichkeit für jede Person separat auszurechnen. Gibt es einen einfacheren Weg oder sollte ich mich an die Rechnungen setzen. Wenn es jedoch pures Rechnen ist, fände ich dieses Rätsel eher enttäuschend. Ich bin dankbar für alle Hinweise.

Gruß Tobi



  Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26355
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-06-13 00:14


Hi Tobi92sr

Ich habe zwar auch (noch) keinen Rechenweg, aber eine Simulation zeigt doch schon mal eine Richtung an, in die es geht. Und danach liegst du mit deiner Vermutung falsch wink
Ich verrate allerdings (noch) nicht, was die Simulation gebracht hat. Aber 300000 mal das Geschenk in die Runde geben und dabei zählen, wer das Geschenk wie oft erhält liefert schon eine klare Richtung. Blöd nur für Person 1, denn die darf es ja nie behalten frown

Gruß vom ¼


-----------------
Bild



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4146
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2018-06-13 00:54


2018-06-13 00:14 - viertel in Beitrag No. 1 schreibt:
Und danach liegst du mit deiner Vermutung falsch wink

Ich habe es nicht programmiert oder berechnet ... aber alles andere als die Vermutung von Tobi92sr würde mich jetzt ziemlich irritieren ... ich lasse mich aber gerne überraschen  smile



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5376
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-06-13 09:40


@StrgAltEntf: Dann wirst Du wohl überrascht werden.

Mal überlegen, wie man das exakt rechnen könnte ...



  Profil  Quote  Link auf diesen Beitrag Link
markusv
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 24.01.2017
Mitteilungen: 94
Aus: Leipzig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-06-13 10:37


Ich würde aufgrund der gleichen Wahrscheinlichkeit der Weitergabe nach links und rechts vermuten, dass es egal ist, an welchem Platz man sitzt. Auch wenn die Vermutung, der gegenüberliegende Platz ist der "sicherste", natürlich mehr einleuchtet.



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2785
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-06-13 12:44


Hallo Tobi et al,

Wenn man den Wert 10 aus der Ausgangsproblemstellung nimmt, wäre die Anzahl der Zustände noch handhabbar:

Das Geschenk kann schon max_links = 0..8 Schritte weit "links herum" gelangt sein ( wobei es egal ist, ob und wie weit es zwischendurch zurück oder gar nach "rechts herum" gegangen ist,

für jeden dieser Werte kann es aber auch schon max_rechts = 0..8-max_links Schritte nach "rechts herum" gegangen sein, und

es kann sich aktuell an einer der Positionen zwischen max_links und max_rechts befinden.

Das ergibt eine Zahl von ( geschätzt ) weniger als 100 möglichen Zuständen, dafür sollte man ( per Programm ) noch die Übergangsmatrix erstellen und den Grenzwert der Iteration bestimmen können? ( wobei ich da vielleicht etwas optimistisch bin )

Für vier Personen kann man es nach dem Schema noch händisch durchspielen...

Interessierte Grüsse aus dem Harz
Gonz



-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
nullptr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 46
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2018-06-13 12:55

\(\begingroup\)
Hi,

zur Berechnung der Wahrscheinlichkeit, dass das Geschenk zuletzt an Platz $x$ ankommt: Man kann den Kreis an der Stelle aufbrechen und die übrigen Stühle in einer Kette von $1$ bis $9$ nummerieren. Jetzt basteln wir eine Markov-Kette mit Zuständen $(p, l, r)$, wobei $p \in \{ 0, 1, \dots, 9 \}$ die Position des Geschenks (0 heißt Platz $x$) angibt und $l, r \in \{ 0, 1 \}$ angeben, ob das Geschenk schon an Platz $1$ bzw. Platz $9$ war. Es gilt nämlich $l = r = 1$ und $p \neq 0$ genau dann, wenn das Geschenk alle Plätze außer Platz $x$ erreicht hat. Die Zustandsübergänge sind dann:

$(p, l, r) \rightarrow (p + 1, l, r)$ für $1 \le p \le 7$ mit 50% Wahrscheinlichkeit.  

$(p, l, r) \rightarrow (p - 1, l, r)$ für $3 \le p \le 9$ mit 50%.

$(2, l, r) \rightarrow (1, 1, r)$ mit 50%.

$(8, l, r) \rightarrow (9, l, 1)$ mit 50%.

$(1, l, r) \rightarrow (0, l, r)$ und $(9, l, r) \rightarrow (0, l, r)$ mit 50%.

$(0, l, r) \rightarrow (0, l, r)$ mit 100%.

Eine Grenzverteilung sollte es geben, weil die Wahrscheinlichkeit, in einem Zustand mit $p = 0$ zu verharren, gegen 1 strebt. Uns interessiert dann die Wahrscheinlichkeit, vom Startzustand in den Zustand $(0, 1, 1)$ zu gelangen.

Ich habe ein kleines Programm geschrieben und einfach durch Potenzieren der Übergangsmatrix ein paar Tausend Schritte simuliert. Das Ergebnis entspricht dem einer einfachen Simulation. Exakt lösen kann man es vermutlich über ein lineares Gleichungssystem, bei $40$ Zuständen sollte das noch klappen.

[Die Antwort wurde nach Beitrag No.4 begonnen.]
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2785
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-06-13 13:05

\(\begingroup\)
2018-06-13 12:55 - nullptr in Beitrag No. 6 schreibt:
Exakt lösen kann man es vermutlich über ein lineares Gleichungssystem, bei $44$ Zuständen sollte das noch klappen.



Ja, ich hatte bei meiner Betrachtung mit ca. 100 Zuständen übersehen, dass durch die rechts/links Symmetrie sich die Zahl der Zustände nochmal in etwa halbiert. Das wäre also wohl machbar...


Nachtrag: Wenn ich mich nicht vertan habe kommt im Fall von vier Stühlen eine Gleichverteilung zwischen den Plätzen rechts, links und gegenüber heraus...


-----------------
to fight! (Don Quijote de la Mancha)
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4146
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2018-06-13 22:09


Ich habe nun auch eine Simulation programmiert. Das Ergebnis ist ziemlich eindeutig, und ich habe jetzt ebenfalls eine Idee, wie die tatsächliche Verteilung aussieht. Tatsächlich ist der gegenüberliegende Platz nicht im Vorteil. Ein elegantes Argument, das meine Idee stützt, habe ich aber noch nicht.



  Profil  Quote  Link auf diesen Beitrag Link
JoeM
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.10.2015
Mitteilungen: 328
Aus: Oberpfalz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2018-06-14 01:18


Hallo,

per Computer komme ich auf folgendes Ergebnis:


Die Gewinnwahrscheinlichkeiten für die Personen 2 bis 10 sind nahezu gleich.

Wie sieht es aus, wenn auch Person 1 das Geschenk erhalten kann ( der Anfang mit >Person 1 hat ein Geschenk in der Hand< wird als >nicht in der Hand< gewertet ) ?

viele Grüße

JoeM



  Profil  Quote  Link auf diesen Beitrag Link
MontyPythagoras
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.05.2014
Mitteilungen: 1229
Aus: Hattingen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2018-06-14 09:46


Hallo zusammen,
2018-06-14 01:18 - JoeM in Beitrag No. 9 schreibt:
Die Gewinnwahrscheinlichkeiten für die Personen 2 bis 10 sind nahezu gleich.

Ja, aber nur nahezu. Ich habe eine Simulation mit 200 Millionen Spielrunden laufen lassen. Es ergibt sich eine symmetrische Verteilung, wie zu erwarten war:


Spieler 0 und 10 sind die identische Person, nämlich die zu Anfang das Geschenk in der Hand hält. In der zweiten Spalte ist die Anzahl der gewonnenen Spielrunden. Spieler 5 ist die Person, die dem Spieler 0 direkt gegenüber sitzt. Sie hat tatsächlich die schlechteste Gewinnwahrscheinlichkeit, und nicht wie vom TS vermutet die beste. Die besten Gewinnchancen haben seltsamerweise die beiden Spieler 1 und 9, also diejenigen, die direkt neben dem Startspieler sitzen. Grafisch dargestellt:


Die rote Linie zeigt die durchschnittliche Gewinnwahrscheinlichkeit.
Noch seltsamer wird es bei 20 Spielern, wo die Personen 6 und 14 die höchste Gewinnwahrscheinlichkeit haben, also quasi mittendrin in der Runde.
2018-06-14 01:18 - JoeM in Beitrag No. 9 schreibt:
Wie sieht es aus, wenn auch Person 1 das Geschenk erhalten kann ( der Anfang mit >Person 1 hat ein Geschenk in der Hand< wird als >nicht in der Hand< gewertet ) ?
Interessanterweise ändern sich fast alle Gewinnwahrscheinlichkeiten nur geringfügig, bis auf Spieler 1 und 9, deren Gewinnchancen auf die Hälfte zusammenbrechen. Die beste Gewinnchance hat nun Spieler 0!
Kann das jemand soweit bestätigen?

Ciao,

Thomas




  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2785
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2018-06-14 10:31


Ich habe folgenden Ansatz im Sinn, mit dem man ggf. die Sache doch "händisch" berechnen kann. Ich würde die Anzahl der Zustände reduzieren, indem ich erst einmal unterscheide, wie weit man nach rechts bzw. links schon gekommen ist. Da die Situation ja symmetrisch gegen vertauschen von rechts und links ist, bastele ich mir also Zustände, die ich mit
fed-Code einblenden

und das Ganze dann zusammensetzen :)

Grüsse aus dem Harz

Gerhard/Gonz




-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4146
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2018-06-14 12:10


2018-06-14 09:46 - MontyPythagoras in Beitrag No. 10 schreibt:
Ich habe eine Simulation mit 200 Millionen Spielrunden laufen lassen.

Ich komme bei 200.000.000 Versuchen auf eine andere Verteilung:
0   0,000
1  11,107
2  11,113
3  11,113
4  11,115
5  11,112
6  11,111
7  11,109
8  11,111
9  11,109



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2785
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2018-06-14 12:20


Wie gross ist denn die erwartete Streuung der Werte beim 2 Mio-maligen Ziehen aus 9 gleich wahrscheinlichen Ereignissen ? Bzw könnte man eine Test angeben, ob diese Ergebnisse signifikant gegen die Annahme einer Gleichverteilung verstossen.


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4043
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2018-06-14 13:30


Wie schon gesagt wurde, muss die Verteilung der Gewinnwahrscheinlichkeiten symmetrisch in dem Sinne sein, als bei der Nummerierung der Spieler 0-9 mit Start bei 0 je zwei Spieler, deren Nummern sich auf 10 ergänzen, wie z.B. 1 und 9, 2 und 8 usw. die gleiche Gewinnwahrscheinlichkeit haben müssen. Daraus folgt schon mal, dass in der Tabelle von MontyPythagoras die letzten 2 Stellen, in der Tabelle von StrgAltEnf aber die letzte Stelle in Hinblick auf die theoretisch exakten Werte nicht stimmen können. Lässt man diese Stellen aber weg bzw. rundet auf die verbleibenden Stellen, so ergibt sich dann mehr oder weniger dann eine Gleichverteilung (edit: Ok, im Falle von MontyPythagoras doch nicht ganz).



  Profil  Quote  Link auf diesen Beitrag Link
MontyPythagoras
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.05.2014
Mitteilungen: 1229
Aus: Hattingen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2018-06-14 13:42


Hi StrgAltEntf,

2018-06-14 12:10 - StrgAltEntf in Beitrag No. 12 schreibt:
Ich komme bei 200.000.000 Versuchen auf eine andere Verteilung:
0   0,000
1  11,107
2  11,113
3  11,113
4  11,115
5  11,112
6  11,111
7  11,109
8  11,111
9  11,109


Gleiche Chancen für alle finde ich ja grundsätzlich auch plausibler. Zumindest sagt mir das mein mathematisches Gefühl, und ich habe durchaus Zweifel an meiner eigenen Simulation. Ich bin jetzt bei einer Milliarde Durchläufe und die Verteilung ist immer noch exakt gleich. Ich muss den Algorithmus wohl noch einmal einer kritischen Prüfung unterziehen...  smile

Ciao,

Thomas

[Die Antwort wurde nach Beitrag No.13 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
MontyPythagoras
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.05.2014
Mitteilungen: 1229
Aus: Hattingen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2018-06-14 14:14


Hallo zusammen,
2018-06-14 13:30 - weird in Beitrag No. 14 schreibt:
Wie schon gesagt wurde, muss die Verteilung der Gewinnwahrscheinlichkeiten symmetrisch in dem Sinne sein, (...) Lässt man diese Stellen aber weg bzw. rundet auf die verbleibenden Stellen, so ergibt sich dann mehr oder weniger dann eine Gleichverteilung (edit: Ok, im Falle von MontyPythagoras doch nicht ganz).

Das sehe ich zwar nicht so, denn eine geringfügige Abweichung von der genauen Wahrscheinlichkeit ist völlig normal (bei 6 Millionen Würfen mit einem Würfel wird ja auch nicht zwangsläufig jede Zahl genau 1 Million mal fallen), und in dem Rahmen ist die Verteilung bei mir auch symmetrisch.
Aber ich habe den Fehler bei mir gefunden (der keiner war). Offenbar ist der Zufallsgenerator in meiner Simulation nicht sauber. Nachdem ich jetzt die Zufälligkeit erhöht habe, komme ich nach ein paar Millionen Spielrunden zumindest auf Anhieb auch auf eine annähernd gleiche Verteilung.

Ciao,

Thomas



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4146
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2018-06-14 14:27


Hallo Monty,

2018-06-14 13:42 - MontyPythagoras in Beitrag No. 15 schreibt:
Ich muss den Algorithmus wohl noch einmal einer kritischen Prüfung unterziehen...  smile

Oder den RNG? Bei 1 Mrd. Versuchen komme ich auf folgende Verteilung
0   0,000
1  11,1109
2  11,1103
3  11,1111
4  11,1110
5  11,1116
6  11,1117
7  11,1110
8  11,1103
9  11,1123

Gruß
StrgAltEntf

[Die Antwort wurde nach Beitrag No.15 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26355
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2018-06-14 15:13


Diese (annähernde) Gleichverteilung auf die Personen 1…9 hatte auch mit meiner Simulation.

Irrerweise ändert sich das Ergebnis völlig (oder ich habe einen Denkfehler im Programm), wenn Person 0 nicht gleich raus ist, weil sie das Paket zuerst in der Hand hält (also es wird erst die erste Weitergabe gewertet):
Anzahl Durchläufe : 300000
0 :  4389 ( 1.463%)
1 : 22106 ( 7.369%)
2 : 21864 ( 7.288%)
3 : 40683 (13.56 %)
4 : 40877 (13.63 %)
5 : 44577 (14.86 %)
6 : 40837 (13.61 %)
7 : 40690 (13.56 %)
8 : 21857 ( 7.286%)
9 : 22120 ( 7.373%)
C++
   cout << "Start\n";
   srand (time(NULL));
   const int   nP = 10;             // wie viele Personen sitzen am Tisch
   int         iPcount[nP] = {0};   // Zähler, wer das Geschenk wie oft behalten durfte
 
   const int   maxIterationen = 300000;
   cout << "Anzahl Durchläufe : " << maxIterationen << endl;
 
   for (int iterationen=0; iterationen<maxIterationen; iterationen++) {
      int   P[nP] = {0};   // wer hatte das Geschenk wie oft in den Händen
      int   belegt = 0;    // wie viele Personen hatten das Geschenk in der Hand
      int   iP = 0;        // Index der Person, die das Geschenk hat
   //	P[iP] = 1;				// P[0] macht den Anfang
   //	belegt++;
      while (belegt < nP-1) {                   // solange noch nicht alle das Geschenk hatten ...
         iP = (iP + (rand()%2)*2-1+nP) % nP;    // nächste Person: iP ±1
         if (0 == P[iP]++) {                    // wenn sie es noch nicht hatte ...
            belegt++;                           // ... zählen
            }
         }
      iPcount[iP]++;                            // der hatte es zuletzt
      }
 
   cout << "\n\n";
   for (int i=0; i<nP; i++)
      cout << i << " : " << iPcount[i] << " (" << setprecision(4) << (100.0*float(iPcount[i])/maxIterationen) << "%)" << "\n";
   cout << "\n";



  Profil  Quote  Link auf diesen Beitrag Link
Tobi92sr
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.12.2016
Mitteilungen: 77
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, vom Themenstarter, eingetragen 2018-06-14 15:13


Vielen Dank für die vielen Antworten und die Mühe die hineingesteckt wurde, auch wenn ich nicht alle Lösungswege verstanden habe. ^^

Ich bin auch auf eine Gleichverteilung gekommen, durch folgende Überlegung:

Für jede Position(außer die von Person 1) gibt es zu einem Zeitpunkt den Fall, dass eine Person links oder rechts davon das Geschenk hält, die andere Person jedoch noch nicht gehalten hat. Wir nennen dies Zustand 1. Also für jede Person tritt irgendwann Zustand 1 ein. Ab diesem Zustand muss das Paket einmal den Kreis in entgegen gesetzter Richtung durchlaufen, damit die jeweilige Person das Geschenk erhält. Es spielt also für Person k keine Rolle, was mit dem Geschenk passiert, solange Zustand 1 für Person k noch nicht eingetreten ist. Da die Wahrscheinlichkeiten für das Durchlaufen in eine Richtung unabhängig von der Position des Geschenks ist, sollte es also für alle Personen gleich wahrscheinlich sein, das Geschenk zu erhalten(bis auf Person 1).

Könnte man so argumentieren?


[Die Antwort wurde nach Beitrag No.17 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
TomTom314
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.05.2017
Mitteilungen: 764
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2018-06-14 15:32

\(\begingroup\)
Hallo zusammen,

ich versuche mich Mal an einem (nicht so schönen) Beweis. Zunächst läßt sich das Problem etwas umformulieren, indem man von einer Reihe von 21 Personen ausgeht und die Wahrscheinlichkeit bestimmt, dass genau 9 Personen das Geschenk erhalten, z.B.

G X X O X X X X X

wobei G die Position des Geschenks und O der Ausgangspunkt ist. Die Wahrscheinlichkeit, dass eine Person dann das Geschenk erhält, ist die Summer der Wahrscheinlichkeiten der Zustände

G X X O X X X X X
X X X O X X X X G

Hier betrachte ich nur die Zustände, wo das Geschenk an eine weitere Person nach außen gegeben wurde.

Lemma. Für n Personen ist die Wahrscheinlichkeit, dass der Zustand X ... X G
in den Zustand X ... X(G) G übergeht \(\frac{n}{n+1}\). Entsprechend ist die Wahrscheinlichkeit, dass die Person am anderen Ende der Kette das Geschenk erhält \(\frac{1}{n+1}\)

Beweisskizze. \(w_k\) ist die Wahrscheinlichkeit, dass das Geschenk von der k-ten Person (nach mehrfacher Weitergabe) an die (n+1)-te Person übergeben wird. Hier erhält man ein Gleichungssystem
\[w_1=\frac{1}{2} w_2\\
w_k=\frac{1}{2} w_{k-1}+\frac{1}{2} w_{k+1}\\
w_n=\frac{1}{2} w_{n-1}+\frac{1}{2}
\] und Lösung \(w_k=\frac{k}{n+1}\)

Zur allgemeinen Situtaion Die Zustände
\(Z^-(-3,5)\): G X X O X X X X X
\(Z^+(-3,5)\): X X X O X X X X G
bezeichne ich mit \(Z^-(k,l),Z^+(k,l)\), bzw. deren Wahrscheinlichkeit mit \(W^-(k,l),W^+(k,l)\), wobei \(Z^-(0,l),Z^+(k,0)\) nicht auftreten können.

Damit erhält man eine Rekursions Formeln
\[W^+(0,n+1) = \frac{n}{n+1} W^+(0,n) \\
W^+(k,l) = \frac{n}{n+1} W^+(k,l-1) + \frac{1}{n+1} W^-(k,l-1)\] und entsprechende für \(W^-(\ldots)\). Diese ergeben dann
\[W^+(0,n) = W^-(-n,0)= \frac{1}{n+1} \\
W^+(k,l) = W^-(k,l) = \frac{1}{2(k+l+1)} \] was dann eine Gleichverteilung zeigt.

Wie gesagt: Schön ist es nicht und die meisten Rechnungen habe ich auch nicht weiter ausgeführt.

[Die Antwort wurde nach Beitrag No.17 begonnen.]
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
MontyPythagoras
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.05.2014
Mitteilungen: 1229
Aus: Hattingen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2018-06-14 15:36


Hi StrgAltEntf,
2018-06-14 14:27 - StrgAltEntf in Beitrag No. 17 schreibt:
Hallo Monty,
2018-06-14 13:42 - MontyPythagoras in Beitrag No. 15 schreibt:
Ich muss den Algorithmus wohl noch einmal einer kritischen Prüfung unterziehen...  smile
Oder den RNG?
Sag ich ja, es war bei mir der Zufallsgenerator...
Trotzdem seltsam, dass er so reproduzierbare und symmetrische Abweichungen erzeugte. Wenn er mehr "rechts" als "links" erzeugt hätte, wäre mir das ja sofort aufgefallen. Tückisch.

Ciao,

Thomas

[Die Antwort wurde nach Beitrag No.19 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4146
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2018-06-14 19:15


2018-06-14 15:13 - Tobi92sr in Beitrag No. 19 schreibt:
Könnte man so argumentieren?

Das ist sogar eine ausgezeichnete Argumentation! Auf einmal lichtet sich das Mysterium  smile

Tolles Rätsel und tolle Lösung!

@Monty #21: Ich hatte deinen Beitrag noch nicht gelesen, als ich meinen schrieb. Ein ähnliches Phänomen hatte ich mal hier thematisiert.



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4146
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, eingetragen 2018-06-14 22:20

\(\begingroup\)
2018-06-14 01:18 - JoeM in Beitrag No. 9 schreibt:
Wie sieht es aus, wenn auch Person 1 das Geschenk erhalten kann ( der Anfang mit >Person 1 hat ein Geschenk in der Hand< wird als >nicht in der Hand< gewertet ) ?

Dies lässt sich nun leicht beantworten. n sei die Anzahl der Personen. Im ersten Schritt gibt Person 1 das Geschenk an Person 2 oder n weiter. Person 2 bzw. n wird dann zum Startspieler im ursprüglichen Spiel und gewinnt mit W'keit 0. Falls Person 2 oder n das Geschenk nicht im ersten Schritt erhält, gewinnt sie mit W'keit 1/(n-1).

Folglich gewinnen Person 2 und n je mit W'keit \(\frac12\cdot0+\frac12\cdot\frac1{n-1}=\frac1{2(n-1)}\).

Für alle anderen Personen (einschließlich Person 1) ist die Gewinnw'keit wie beim ursprünglichn Spiel, nämlich \(\frac1{(n-1)}\).

@viertel: Ich glaube, bei iPcount[iP]++; zählst du die falsche Person hoch, nämlich die, die das Geschenk als letztes hatte, und nicht die, die das Geschenk noch gar nicht hatte und damit Gewinnerin ist.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
JoeM
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.10.2015
Mitteilungen: 328
Aus: Oberpfalz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, eingetragen 2018-06-14 22:53


Hallo StrgAltEntf,

Deine Berechnung im Beitrag vorher für den Fall...
Wie sieht es aus, wenn auch Person 1 das Geschenk erhalten kann ( der Anfang mit >Person 1 hat ein Geschenk in der Hand< wird als >nicht in der Hand< gewertet ) ?
... ist völlig richtig.

In diesem Fall ist die Gewinn-W'keit für die beiden Personen, die links, und rechts von Person 1 sitzen, jeweils halb so groß, wie für alle anderen Personen.


viele Grüße

JoeM



  Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26355
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, eingetragen 2018-06-14 23:16


2018-06-14 22:20 - StrgAltEntf in Beitrag No. 23 schreibt:
@viertel: Ich glaube, bei iPcount[iP]++; zählst du die falsche Person hoch, nämlich die, die das Geschenk als letztes hatte, und nicht die, die das Geschenk noch gar nicht hatte und damit Gewinnerin ist.
Die while-Schleife wird beendet, wenn alle das Geschenk in Händen hatten. Und das ist genau dann der Fall, wenn der letzte, der es noch nicht hatte, es gerade bekommen hat, nämlich iP. Dann wird belegt um 1 hochgezählt und hat dann den Wert nP-1.
Ich denke, das müßte passen.



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4146
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.26, eingetragen 2018-06-14 23:39


2018-06-14 23:16 - viertel in Beitrag No. 25 schreibt:
Die while-Schleife wird beendet, wenn alle das Geschenk in Händen hatten.

Echt jetzt? Müsste es dann nicht heißen while (belegt < nP) statt while (belegt < nP-1)?

Außerdem stimmen deine Ergebnisse ja auch nicht mit JoeMs (und übrigens auch meiner) Simulation überein.




  Profil  Quote  Link auf diesen Beitrag Link
JoeM
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.10.2015
Mitteilungen: 328
Aus: Oberpfalz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.27, eingetragen 2018-06-15 00:22


Hallo,

Anmerkung zu Beitrag Nr. 23 bis Nr. 26:

Ich habe gerade gesehen.... MontyPythagoras schreibt in Beitrag Nr. 10:

>2018-06-14 01:18 - JoeM in Beitrag No. 9 schreibt:
Wie sieht es aus, wenn auch Person 1 das Geschenk erhalten kann ( der Anfang mit >Person 1 hat ein Geschenk in der Hand< wird als >nicht in der Hand< gewertet ) ?
Interessanterweise ändern sich fast alle Gewinnwahrscheinlichkeiten nur geringfügig, bis auf Spieler 1 und 9, deren Gewinnchancen auf die Hälfte zusammenbrechen.<

(Anmerkung: Bei MontyPythagoras sitzen Person 1 und 9 direkt neben der Startperson)

Das bedeutet :
In diesem Fall ist die Gewinn-W'keit für die beiden Personen, die direkt links, und rechts neben der Startperson sitzen, jeweils halb so groß, wie für alle anderen Personen.

viele Grüße

JoeM
 




  Profil  Quote  Link auf diesen Beitrag Link
JoeM
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.10.2015
Mitteilungen: 328
Aus: Oberpfalz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.28, eingetragen 2018-06-15 02:05


Hallo,

Zusatzfrage :

Die Aufgabe beginnt mit ... > 10 Personen sitzen im Kreis .... <.

Daher vermutlich die Bezeichnung der Aufgabe mit ...> Geschenk im Stuhlkreis <.

Angenommen :

Die gleichen Personen sitzen gegenüber auf einem Gang; sonst alles gleich .

Wie könnte dann die Aufgabenstellung lauten ?  smile

viele Grüße

JoeM



  Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26355
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.29, eingetragen 2018-06-15 11:07


2018-06-14 23:39 - StrgAltEntf in Beitrag No. 26 schreibt:
2018-06-14 23:16 - viertel in Beitrag No. 25 schreibt:
Die while-Schleife wird beendet, wenn alle das Geschenk in Händen hatten.

Echt jetzt? Müsste es dann nicht heißen while (belegt < nP) statt while (belegt < nP-1)?
Da gebe ich mich geschlagen frown
Nicht gegen den letzten Index im Feld abprüfen, sondern die echte Anzahl.

StrgAltEntf schreibt:
Außerdem stimmen deine Ergebnisse ja auch nicht mit JoeMs (und übrigens auch meiner) Simulation überein.
Jetzt schon biggrin

Danke für die Korrektur.

[Die Antwort wurde nach Beitrag No.26 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 2740
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.30, eingetragen 2018-06-15 13:05


2018-06-14 12:10 - StrgAltEntf in Beitrag No. 12 schreibt:
2018-06-14 09:46 - MontyPythagoras in Beitrag No. 10 schreibt:
Ich habe eine Simulation mit 200 Millionen Spielrunden laufen lassen.

Ich komme bei 200.000.000 Versuchen auf eine andere Verteilung:
0   0,000
1  11,107
2  11,113
3  11,113
4  11,115
5  11,112
6  11,111
7  11,109
8  11,111
9  11,109


Dies Tabelle geht doch klar nach dem Gesetz der grossen Zahlen nach
0   0,000
1  11,1111... %
2  11,1111... %
3  11,1111... %
4  11,1111... %
5  11,1111... %
6  11,1111... %
7  11,1111... %
8  11,1111... %
9  11,1111... %
also summiert 9*100/9 =100 %.

Alles andere  würde mich arg wundern.



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5376
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.31, eingetragen 2018-06-15 13:38


@juergen007: Diese Vermutung wurde explizit schon in Beitrag #4 ausgesprochen und in Beitrag #20 bewiesen.

EDIT: Gemeint ist Beitrag #19.



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 2740
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.32, eingetragen 2018-06-15 18:02


2018-06-15 13:38 - Kitaktus in Beitrag No. 31 schreibt:
@juergen007: Diese Vermutung wurde explizit schon in Beitrag #4 ausgesprochen und in Beitrag #20 bewiesen.
OK, also die Lösung des Rätsels ist: es gibt keine ideale Position?



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4146
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.33, eingetragen 2018-06-15 18:07


@viertel #29: ich wollte dich gar nicht schlagen wink

@Kitaktus #31: Der Beweis wurde schon in #19 erbracht. Oder siehst du daran etwas auszusetzen?

@juergen #32: Jede Position ist gleich ideal.



  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 4146
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.34, eingetragen 2018-06-21 19:38

\(\begingroup\)
Ich habe meinen Rechner noch einmal angeworfen, weil mich interessiert hat, wie lange das Spiel durchschnittlich dauert.

Meine Vermutung lautet nun:

Der Erwartungswert \(E_n\) für die Spieldauer ist ganzzahlig, und zwar gilt \(E_n=\frac{(n-1)(n-2)}2\), wobei n die Anzahl der am Tisch sitzenden Personen ist.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]