12: Wichtelturnier / Tournament

  • Hierfür habe ich zwei Lösungswege. Der erste ist durch die mMn ungeschickte Aufgabenstellung möglich. Und zwar wird in dieser nicht erklärt, wie jeder Schritt genau abläuft. Das heißt aber doch, dass das Endergebnis unabhängig hiervon sein muss, und damit kommt nur Antwort 10 infrage – „es ist völlig egal, welchen Wichtel welches Team wann wählt“.

    Neben dieser Lösung mittels vollständiger Intuition funktioniert hier aber auch der kleine Bruder davon, die vollständige Induktion – und zwar gewissermaßen in 2D, weshalb ich diese Aufgabe eigentlich extrem schön finde.


    Nomenklatur: Die Teams heißen der Einfachheit halber 1 und 2. Den Zustand, dass Team 1 noch x Wichtel hat und Team 2 noch y nenne ich (x,y), die Wahrscheinlichkeit für den Gesamtsieg von Team 1 in diesem Zustand p(x,y) und die Wahrscheinlichkeit für einen Sieg des von Team 1 nominierten Wichtels in einer Runde p(Runde).


    Behauptung: Team 1 hat zu einem bestimmten Zeitpunkt M Lose insgesamt und Team 2 N Lose. Dann sei p(x,y)=M/(M+N), unabhängig von jeder Taktik, x und y.


    Induktionsanfang: Jedes Team hat noch genau einen Wichtel, die folglich M bzw N Lose haben. Dies ist also Zustand (1,1). Der Sieg des 1. Teams ist offensichtlich mit der Wahrscheinlichkeit p(1,1) = p(Runde) = M/(M+N) zu erwarten, entspricht also der Behauptung.


    Induktionsschritt 1-D: Team 1 hat noch einen Wichtel mit M Losen, und Team 2 hat y Wichtel mit insgesamt N Losen, also Zustand (1,y). Team 2 wählt den Wichtel j mit n_j Losen aus, Team 1 hat keine Wahl. In dieser ersten Runde hat Team 1 eine Gewinnchance von p(Runde)=M/(M+n_j). Mit 1-p(Runde) hat Team 1 direkt verloren, mit p(Runde) hätte Team 1 danach M+n_j Lose, Team 2 stünde bei N-n_j Losen und das Spiel ginge in die nächste Runde im Zustand (1,y-1). Wenn die Behauptung für diesen gilt, dann hätte Team1 danach eine Chance auf den Gesamtsieg von p(1,y-1) = (M+n_j)/(M+n_j+N-n_j) = (M+n_j)/(M+N). Die Wahrscheinlichkeit für den Gesamtsieg von Team 1 beträgt folglich p(1,y)= (1-p(Runde))*0+p(Runde)* p(1,y-1) = M/(M+n_j) * (M+n_j)/(M+N) = M/(M*N), was wiederum der Behauptung entspricht.

    Da die Nomenklatur beliebig ist, gilt dasselbe für vertausche Teams, also falls Team 1 noch x Wichtel hat und Team 2 noch einen. (Zustand (x,1)).


    Induktionsschritt 2-D: Team 1 hat noch x>1 Wichtel mit insgesamt M Losen und Team 2 noch y>1 Wichtel mit insgesamt N Losen – Zustand (x,y). Als gegeben dürfen in der zweidimensionalen Induktion die beiden Zustände (x,y-1) und (y,x-1) gelten. Team 1 wählt nun einen Wichtel i mit m_i Losen, 2 wieder einen mit n_j Losen. Es folgt p(Runde) = m_i/(m_i+n_j). Egal wer gewinnt, geht das Spiel in die nächste Runde, da x und y >1 sind. Falls Team 1 diese Runde gewinnt, hat es danach M+n_j Lose und Team 2 N-n_j Lose, und der Zustand ist (x,y-1). Falls Team 2 diese Runde gewinnt, hat Team 1 M-m_i Lose, Team 2 N+m_i Lose und der Zustand ist (x-1,y). Insgesamt folgt mit ein bisschen Ausklammern und Kürzen p(x,y) = (1-p(Runde)*p(x-1,y) + p(Runde)*p(x,y-1) = n_j/(m_i+n_j)*(M-m_i)/(M+N) + m_i/(m_i+n_j)*(M+n_j)/(M+N) = M/(M+N) qed.

  • Hierfür habe ich zwei Lösungswege. Der erste ist durch die mMn ungeschickte Aufgabenstellung möglich. Und zwar wird in dieser nicht erklärt, wie jeder Schritt genau abläuft. Das heißt aber doch, dass das Endergebnis unabhängig hiervon sein muss, und damit kommt nur Antwort 10 infrage – „es ist völlig egal, welchen Wichtel welches Team wann wählt“.


    Diese Schlussfolgerung ist aber logisch nicht zu rechtfertigen: Die genaue Abfolge des Schrittes ist nicht erklärt. Daraus kann man vielleicht folgern, dass die Wahl der besten eigenen Entscheidung nicht von der Wahl des Gegners abhängt, aber sonst nichts. Zum Beispiel könnte die beste Wahl immer der Wichtel mit den meisten Losen sein. Dann nominieren halt beide Manschaften immer den Wichtel mit den meisten Losen, ohne sich darum zu kümmern, wen der Gegner nominiert. Das ist mit der Angabe völlig kompatibel. Aber mehr kann man daraus auf keinen Fall folgern.

  • Kurzer Induktionsbeweis, dass die Nominierung für die Gewinnchance grundsätzlich egal ist: https://imgur.com/m4nhBIp.png

    Schöner kurzer schlüssiger Beweis. Prima, gefällt! Da braucht man keine Induktion in 2D...

    Allerdings sollte man den Induktionsanfang für k=2 führen: da ist dann die "Laplace-Gewinnwahrscheinlichkeit" natürlich offensichtlich: für Mannschaft M: M/M+N für Mannschaft N: N/M+N (bei k=1 gibt es ja nur noch eine Mannschaft, das Spiel ist also vorbei!)

  • Allgemein: Ist N die Anzahl der Lose von Team Blau, und setze Team Blau n Lose und Team Gelb m Lose in die nächste Paarung...

    Dann ist doch Erwartungswert der Anzahl der Lose von Team Blau nach dieser beliebigen Paarungsbesetzung:


    N + n/(n+m) * m - m/(n+m) * n = N


    Es hat also keine Auswirkung wie n und m von den Teams gewählt werden.

  • Im Grunde liegt hier das gleiche Problem vor, wie bei folgender "realitätsnahen" ;) Geschichte. Ein Mathestudent lebt mit drei Nicht- Mathematikern in einer WG. Nach dem Abendessen schlägt der Mathematiker vor, per Los zu bestimmen, wer abspülen muss.

    Der Mathematiker nimmt vier Spielkarten (drei Asse und die Pik sieben).

    Wer die Pik 7 zieht, der muss abspülen.

    Plötzlich entsteht ein Streit unter den Nichtmathematikern, jeder will als Erster ziehen. Der Mathematiker fragt verwundert: "wieso denn?".

    Da antwortet einer der drei anderen:" Ja, das ist doch klar, wenn ich als Erster ziehe, dann ist die Chance, dass ich Abspülen muss 1:4 und wenn ich als Zweiter ziehe schon 1:3 usw."

    Der Mathematiker versucht den Streit zu schlichten (was ihm aber leider nicht gelingt). Aber er sagt letztendlich: Na gut, ich ziehe freiwillig als Letzter". ;)

  • Ob sich der mathestudent auch wundert wenn er eine Ziege und kein Auto gewinnt? Ganz so intuitiv schien mir die Aufgabe dann doch nicht.

    Nein, denn er weiß, dass selbst wenn er das Tor wechselt nur mit der Wahrscheinlichkeit (n-1)/n (falls es n-1 Tore mit Ziegen und ein Tor mit Auto gibt) das Auto gewinnt (und das sind keine 100%).

    ;) Vorausgesetzt er will überhaupt das Auto (denn vielleicht ist es ja ein Euro 4 Diesel und wenn er in Stuttgart studiert, dann hat er ein Problem).