1. Aufgabe
Du bist bei einem exzentrischen Mathematiker angestellt, der dir aufträgt, seine Sockenschublade so mit roten und schwarzen Socken zu füllen, dass er, wenn er blind zwei Socken herausfischt, im Schnitt jeden zweiten Tag zwei rote Socken zieht. Wie stellst du es an?
2. Eine intuitive Idee
Ich lege einfach doppelt so viele rote wie schwarze Socken in die Schublade und dann passt das schon.
Wie aber kann ich das überprüfen? Wir erinneren uns daran, wie man stochastisch argumentier: Wahrscheinlichkeiten beziehen sich immer auf ein Modell, und dieses können wir verifizieren. Wir haben zum Beispiel drei Socken, eine schwarze und zwei rote. Unser Modell sieht so aus:
Die Spalten sind die Ereignisse, in denen wir zuerst eine schwarze Socke (S) bzw. eine der beiden roten Socken (R1, R2) ziehen. Da dies mit gleicher Wahrscheinlichkeit geschieht, sind die Spalten gleich breit. Entsprechend bezeichnen die Zeilen diejenigen Ereignisse, in denen wir als zweites eine schwarze Socke oder eine der roten Socken ziehen. Die grauen Ereignisse sind nicht möglich, da wir die Socken nicht zurücklegen, die beiden anderen Ereignisse in einer Spalte müssen jedoch gleichwahrscheinlich sein.
Grün sind alle Ereignisse, in denen zwei rote Socken gezogen werden, es sind 2 von insgesamt 6 möglichen Ereignissen, also ziehen wir mit einer Wahrscheinlichkeit von gerade einmal 2/6 = 1/3 zwei rote Socken.
Bei sechs Socken, zwei schwarzen und vier roten, sieht unser Modell so aus:
Das Auszählen der Kästchen ist etwas aufwändiger, aber es gelingt schnell: die Wahrscheinlichkeit für zwei rote Socken beträgt 12/30 = 6/15 = 2/5, also auch nicht 1/2.
Wir sehen sogar, dass wir mit diesem Ansatz - doppelt so viele rote wie schwarze Socken - nie auf eine Wahrscheinlichkeit von 1/2 kommen werden, denn schon die Anzahl der Kästchen, die zu einem gemischt-farbigen Sockenpaar gehören, ist sichtlich größer als die Anzahl der Kästchen, die zu einem gleichfarbigen Sockenpaar gehören.
Lässt man die Anzahl der Socken gen unendlich streben, werden die grauen Kästchen also kleiner und kleiner, bis man sie nicht mehr sehen kann, so erhalten wir das folgende Bild:
Selbst in diesem Grenzfall beträgt die Wahrscheinlichkeit für zwei rote Socken lediglich 4/9, nicht aber 1/2. Diese Aufteilung kann also die Aufgabe nicht lösen, ganz gleich, wie viele Socken es insgesamt gibt.
3. Die kleinste Lösung und die zweitkleinste
Probiert man ein wenig aus, was passiert, gelangt man schnell zu einer Lösung: eine schwarze Socke und drei rote. Schaut selbst:
Offensichtlich beträgt die Wahrscheinlichkeit von zwei roten Socken genau 6/12 = 1/2. Es ist allerdings nicht so, dass wir einfach doppelt so viele Socken in die Schublade stecken können, ohne die Wahrscheinlichkeit zu ändern. Man sieht dies mit zwei Methoden:
Einerseits können wir einfach mal die Socken verdoppeln und schauen, was passiert:
Offenbar liegt nun die Wahrscheinlichkeit für zwei rote Socken bei 30/56 = 15/28, als bei mehr als 1/2. Andererseits könnten wir wieder betrachten, wie die Grafik ausschaut, wenn wir eine riesige Anzahl von Socken haben, wenn die grauen Flächen also verschwindend klein sind. (Denn wir verdoppeln können, ohne die Wahrscheinlichkeit zu ändern, dann auch sehr, sehr oft.)
Wir zählen ab: die Wahrscheinlichkeit nähert sich bei sehr vielen Socken dem Wert 9/16 an, der ebenfalls ungleich 1/2 ist. Ihr habt es sicherlich gemerkt: Das Modell für sehr viele Socken entspricht dem Modell für nur 4 Socken, mit der Ausnahme, dass es keine grauen Felder mehr gibt. Da allerdings nicht im gleichen Maße graue Vierecke grün gefärbt werden, wie graue Vierecke irgendwie gefärbt werden, kann das Verhältnis von grünen zu farbigen Vierecken nicht gleich bleiben.
Man muss also ein wenig schauen und probieren, wenn man eine andere Lösung erhalten möchte. Die nächstkleinste ist die folgende: 6 schwarze Socken und 15 rote. Ihr könnt gerne nachzählen:
Wie man schnell sieht: Der Anteil der grünen Kästchen an allen farbigen beträgt$$\frac{14\cdot 15}{20\cdot 21}= \frac{2\cdot 7\cdot 3\cdot 5}{2\cdot 2\cdot 5\cdot 3\cdot 7} = \frac 12.$$
4. Keine Lösung, wirklich?
Wir haben gerade gesehen, dass es langsam unübersichtlich wird mit all den Kästchen. Mittlerweile scheint also die Zeit gekommen zu sein, auf Formeln umzusteigen und die Grafik nur noch im Kopf ablaufen zu lassen. Was haben wir bisher erkannt? Wenn in der Schublade $s$ schwarze Socken und $r$ rote Socken liegen, so ist die Wahrscheinlichkeit $p$ dafür, zwei rote Socken zu ziehen, durch die Formel $$p = \frac{(r-1)\cdot r}{(s+r-1)\cdot (s+r)}$$gegeben. Diese Formel überlegen wir uns leicht graphisch, indem wir die grünen und farbigen Kästchen abzählen. Demnach haben wir eine Lösung des Problems gefunden, wenn $p=1/2$ gilt, wenn also, etwas umgestellt, $$\frac{(r-1)\cdot r}2 = \frac 12\cdot \frac{(s+r-1)\cdot (s+r)}2.$$ Wir erinnern uns: die $k$-te Dreieckszahl $d(k)$, also die Summe der ersten $k$ natürlichen Zahlen, ist gegeben durch $$d(k) = \frac{k\cdot(k+1)}2.$$ Die Formel zu unseren Socken sagt also aus: Genau dann, wenn die $(r-1)$-te Dreieckszahl halb so groß wie die $(r+s-1)$-te, sind $r$ rote Socken und $s$ schwarze eine Lösung unserer Aufgabe. Damit ist die Aufgabe völlig auf eine bekannte Zahlenklasse zurückgeführt und ein kleines Computerprogramm berechnet uns die ersten Lösungen für $s$ und $r$:
| 1 | 3 |
| 6 | 15 |
| 35 | 85 |
| 204 | 493 |
| 1189 | 2871 |
| 6930 | 16731 |
| 40391 | 97513 |
| 235416 | 568345 |
Na, wer sieht einen Zusammenhang? Es gibt einige, einen davon entdeckt man, wenn man vom sechsfachen einer s-Zahl die vorhergehende s-Zahl abzieht. Die Aufgabe wäre nun, diesen Zusammenhang zu beweisen, nicht wahr? Viel Erfolg ;)
Wir sehen aber noch etwas anderes: Alle Zahlen, die wir für $r$ finden, sind ungerade und enden auf die Ziffern 3, 5, 5, 3, 1, 1, bevor die Folge wieder von vorne anfängt. Was ist das denn für eine Sockenschublade, in der ungerade viele rote Socken liegen? Der Mathematiker, unser Chef, wird sicherlich fordern, dass zu jedem Zeitpunkt gerade viele rote Socken in der Schublade liegen! Wir müssten also größere Lösungen berechnen, wie etwa
| $s$ = 361786555939836 | $r$ = 873430010034205, |
und hoffen, dass diese vielleicht doch einen geraden r-Wert enthält, oder aber, wir beweisen ein für alle mal, dass es keine Lösung mit gerade vielen Socken geben kann. Das ist auch gar nicht so schwer, wenn man sich auf bekannte Ergebnisse zurückzieht. Wir können nämlich einfach mal die Gleichung, die $s$ und $r$ verbindet, nach $r$ umstellen, dann erhalten wir, nachdem wir eine quadratische Gleichung gelöst haben: $$r= 0{,}5 + s + \sqrt{2s^2 + 0{,}25}.$$Da $r$ und $s$ natürliche Zahlen sind, wissen wir, dass die Wurzel eine Zahl der Form $k+0{,}5$ sein muss, wobei $k$ eine natürliche Zahl ist. Quadrieren wir diese Zahl, so sehen wir: $$s^2 = d(k),\quad r = s + k + 1.$$Das ist hilfreich! Kennen wir $s$ und $k$, so kennen wir auch $r$, und $s$ und $k$ sind durch eine erstaunliche Gleichung miteinander verbunden: $s^2 = d(k)=x$, das heißt, $x$ ist eine natürliche Zahl, die sowohl eine Quadratzahl als auch eine Dreieckszahl ist, also eine Quadrat-Dreieckszahl. Der Link verrät es schon: Es ist genau bekannt, welche Zahlen $x$ Quadrat-Dreieckszahlen sind, und für die $n$-te solche Zahl gibt es auch verschiedene Formeln für die Kantenlänge $s_n$ des zugehörigen Quadrates und die Basislänge $k_n$ des zugehörigen Dreiecks, zum Beispiel diese hier: $$s_n = \frac{P_{2n}}2,\quad k_n = \frac{P_{2n}+P_{2n-1}-1}2.$$Dabei bezeichnet $P_n$ die $n$-te Pell-Zahl, die bei der Lösung quadratischer Gleichungen mit ganzen Zahlen auftaucht (daher auch der Zusammenhang zu den Quadrat-Dreieckszahlen) und wiederum einer einfachen Regel gehorcht:$$P_0 = 0,\quad P_1 =1,\quad P_n = 2P_{n-1} + P_{n-2}.$$Was bringt uns das? Ganz klar: Betrachten wir die Pell-Zahlen bei Division durch $4$, so lässt $P_0$ den Rest $0$, $P_1$ den Rest $1$, $P_2$ den Rest $2$ und $P_3$ den Rest $1$. Danach wiederholt sich das Muster (was man leicht mithilfe der Rekursionsgleichung überprüft). Dies können wir auf die $n$-te Lösung $r_n$ der Rote-Socken-Zahl anwenden: $$r_n = s_n + k_n + 1 = P_{2n} + \frac{P_{2n-1}-1}2 + 1.$$Der erste Summand ist stets durch $2$ teilbar, der zweite ebenso (da der Zähler sogar durch $4$ teilbar ist), und der letzte Summand ist die $1$, die sichtlich ungerade ist. Dies bedeutet, dass $r_n$ selbst ungerade ist, und wir sind fertig.
Erkenntnis: Es gibt keine Möglichkeit, schwarze und rote Socken in eine Schublade zu legen, bei der die Wahrscheinlichkeit, blind zwei rote Socken zu ziehen, genau 1/2 ist und bei der gerade viele rote Socken in der Schublade liegen.
Na, hab ich zu viel versprochen? Sobald die Realität ins Spiel kommt mit ihrer seltsamen Anforderung, gerade viele rote Socken zu nutzen, wird das Problem erheblich schwieriger, gar (beweisbar) unlösbar, und dennoch ist das Ergebnis für unseren Alltag völlig irrelevant.
5. Die trivialen Lösungen
Bei umgangssprachlichen Aufgaben gibt es meist ein Schlupfloch, das man ausnutzen kann. Dem mathematisch vorgebildeten Lesern fällt es selten auf, da sie den Text automatisch in ein statistisches Modell übersetzen, so wie oben gesehen. Zur Intelligenz gehört es jedoch auch, unbewusste Annahmen zu hinterfragen. So gibt es hier zwei einfache Möglichkeiten, das Problem zu lösen, selbst mit gerade vielen Socken.
Zum Vergleich nochmals die Aufgabe: Du bist bei einem exzentrischen Mathematiker angestellt, der dir aufträgt, seine Sockenschublade so mit roten und schwarzen Socken zu füllen, dass er, wenn er blind zwei Socken herausfischt, im Schnitt jeden zweiten Tag zwei rote Socken zieht. Wie stellst du es an?
Lösung 1: Ich lege abwechselnd einen Tag nur rote Socken und einen Tag nur schwarze Socken in die Schublade.
Lösung 2: Falls es den Mathematiker stört, dass er niemals eine rote und eine schwarze Socke zieht, lege ich am zweiten Tag zu den schwarzen Socken immer auch genau eine rote Socke. Mal sehen, ob er herausfindet, was ich getan habe :)
Lösung 3: Schonmal eine Sockenschublade gesehen? In so einer sind (in der Regel) jeweils zwei gleichfarbige Socken miteinander verknotet. Ich lege also gleich viele rote und schwarze Sockenpaare in die Schublade und bin fertig.
Die Moral von der Geschichte: Wenn wir es uns nicht so schwer gemacht und von Anfang an Socken verknotet hätten, hätten wir zwar viel Mühe gespart (und hätten so mehr Zeit gehabt, uns mit anderen Matheaufgaben zu beschäftigen), wüssten aber auch nichts über Pell-Zahlen, die gewiss eines Tages nützlich sein werden. Denken macht Spaß, also denken wir weiterhin :)
Keine Kommentare:
Kommentar veröffentlichen