An einem runden Tisch sitzen N Ritter. Jeder hat zwei Nachbarn.
Wie gross ist die Wahrscheinlichkeit, dass nach einem zufaelligen
Platztausch kein einziger Ritter einen alten Nachbarn hat?
Alle Permutationen sollen gleich wahrscheinlich sein.
Viel Spass beim Knobeln.
Gruss, Marco
Hi.
Also, zuerst die einfachen Fälle:
1.) N=0 v N=1: w=100% (es gab vorher keinen Nachbarn, also hinter nicht den gleichen).
2.) N=2 v N=3: w=0%, da jeder alle anderen als Nachbarn hat.
3.) N=4: w=0%, da jeder nur eine Person hat, die vorher nicht Nachbar war, nötig sind aber mind. 2.
So, jetzt das schwerste, alle übrigen N:
Nehmen wir an, wir bezeichnen einen Ritter mit A, der rechts von sich einen alten Nachbarn hat. Wenn es keinen Ritter gibt, der einen alten rechten Nachbarn hat, ist A ein beliebiger Ritter:
Die Wahrscheinlichkeit, dass A nun rechts von sich einen Ritter hat beträgt: 2/(N-1) [Es gibt 2 von (N-1) Ritter, die vorher Nachbarn waren]
Damit beträgt die Wahrscheinlichkeit, dass es keine alten Nachbarschaften mehr gibt: 1 - (2/(N-1)) = (N-3)/(N-1).
Wie gesagt, diese Formel gilt nur für N>=5.
CU,
Sebastian.
Nehmen wir an, wir bezeichnen einen Ritter mit A, der rechts
von sich einen alten Nachbarn hat. Wenn es keinen Ritter gibt,
der einen alten rechten Nachbarn hat, ist A ein beliebiger
Ritter:
Die Wahrscheinlichkeit, dass A nun rechts von sich einen
Ritter hat beträgt: 2/(N-1) [Es gibt 2 von (N-1) Ritter, die
vorher Nachbarn waren]
Damit beträgt die Wahrscheinlichkeit, dass es keine alten
Nachbarschaften mehr gibt: 1 - (2/(N-1)) = (N-3)/(N-1).
Wie gesagt, diese Formel gilt nur für N>=5.
Ich habe gesagt, alle Permutationen sollen gleich wahrscheinlich
sein. bei fuenf Rittern gibts 10 verschiedene Permutationen,
bei denen die Ritter keinen alten Nachbarn haben, es gibt aber 5!=120 gleichwahrscheinliche Permutationen, also ist
die Wahrscheinlichkeit hier 10/120=1/12. das ist ungleich
Deiner Loesung (5-3)/(5-1)=1/2.
tja...
Gruss, Marco
OK.
Die Lösungen für N < 5 sind zumindest korrekt. Bei dem Rest habe ich wohl zu schnell gedacht :). Hier also der zweite Versuch:
Es gibt N Positionen, wo Ritter A sitzen kann. Auf dem Platz rechts neben ihm dürfen (N-3) Ritter sitzen (er selbst und seine zwei Nachbarn dürfen es ja nicht sein). Der linke Sitznachbar muss nicht mehr extra berücksichtigt werden, da dies ja dadurch abgedeckt wird, dass wir von allen N Rittern jeweils den rechten Nachbarn betrachten. Insgesamt gibt es N! Permutationen der N Ritter. Somit lautet die Lösung N*(N-3) / N!.
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hi.
Wie ist denn die richtige Lösung?
Ich bin mittlerweile soweit, dass im Nenner (N-1)! steht, da ja immer N Positionen äquivalent sind (z.B. 12345 = 23451 = 34512 = 45123 = 51234). Man kann also alles durch N kürzen. Aber wie man auf den Zähler kommt, bleibt mir schleierhaft. Für N=5 und N=6 funktioniert (N-3)!, aber für N=7 kommt das nicht mehr hin.
CU,
Sebastian.
Ich hatte die Idee, dass man rekursiv von N auf N+1
schliessen kann, weil ja immer noch ein Ritter irgendwo
dazwischen gequetscht werden kann. Das ergibt aber keine
geschlosssene Formel.
Vielleicht habe ich ein Problem gefunden, dass gar nicht
allgemein geloest werden kann. Meine Loesung stimmt,
wie ich zu meiner Schande gestehen muss, auch nicht.
Gruss, Marco