Spinne und Fliege

17.02.2020, 13:45

Huggy

Spinne und Fliege

Lehrer im Biologieunterricht Oberstufe: Im mathematischen Urwald wurde eine neue Spinnenart entdeckt. Sie wurde areana cubicorum genannt, weil ihr Netz aus den Kanten eines Würfels besteht. Wenn sie sich auf einer Ecke des Würfels befindet, bewegt sie sich rein zufällig zu einer der über eine Kante erreichbaren anderen Ecken. Dabei kehrt sie aber im nächsten Schritt nicht zu der Ecke zurück, von der sie gerade gekommen ist. Eine degenerierte Unterart hat diese Restriktion nicht.

Der auch anwesende Mathelehrer: Hausaufgabe: Die Spinne befinde sich auf einer Ecke des Würfels. Auf der auf der Raumdiagonale gegenüberliegenden Ecke befinde sich eine Fliege. Berechnet, wie viele Kanten die beiden Varianten von areana cubicorum im Mittel überqueren, bis die Spinne erreichen.

18.02.2020, 11:36

CrazyL

Auf diesen Beitrag antworten »

Klingt interessant - wegen der Rotationssymmetrie zur Raumdiagonalen sammeln wir die Eckpunkte in Klassen und nehmen an, dass die Kantenlänge gleich Eins ist:
$\begin{eqnarray*} S_0&=&\{(0;0;0)\}&\text{Startpunkt der Spinne} S_1&=&\{(1;0;0),\: (0;1;0),\: (0;0;1)\}& S_2&=&\{(1;1;0),\: (1;0;1),\: (0;1;1)\}& S_3&=&\{(1;1;1)\}&\text{Fliege im Netz} \end{eqnarray*}$

Die Aussage "Die Spinne darf nicht zweimal hintereinander über dieselbe Kante laufen" liefert einige Bedingungen:

Die ersten beiden Bewegungen sind fix: $\begin{eqnarray*} p_0:=S_0\rightarrow S_1\rightarrow S_2 \end{eqnarray*}$
Danach hat die Spinne genau drei Möglichkeiten: $\begin{eqnarray*} p_1:=S_2\rightarrow S_1\rightarrow S_2,\qquad p_2:=S_2\rightarrow S_1\rightarrow S_0\rightarrow S_1\rightarrow S_2,\qquad p_3:=S_2\rightarrow S_3\quad\text{(Fliege)} \end{eqnarray*}$

Die begehbaren Kanten sind für die Spinne bei jedem Schritt gleich wahrscheinlich, also haben die Pfade die Wahrscheinlichkeiten
$\begin{eqnarray*} P(p_0|S_0)=1\cdot 1=1,\qquad P(p_1|S_2)=\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4},\qquad P(p_2|S_2)=\frac{1}{2}\cdot\frac{1}{2}\cdot 1 \cdot 1=\frac{1}{4},\qquad P(p_3|S_2)=\frac{1}{2} \end{eqnarray*}$

Jeder Pfad der Spinne vom Start- zum Zielknoten ist von der Form
$\begin{eqnarray*} p_{n, k}:=p_0\bigl[k\times p_1,\: (n-k)\times p_2\bigr]p_3,\quad P(p_{n,k})=\binom{n}{k}\left(1\cdot\frac{1}{4^n}\cdot\frac{1}{2}\right)=\binom{n}{k}2^{-(2n+1)},\qquad n\in\mathbb{N},\quad k\in\{0;\ldots;n\} \end{eqnarray*}$

Die Reihenfolge von p1, p2 im Mittelteil ist beliebig, deshalb auch der zusätzliche Binomi in der Wahrscheinlichkeit. Zum Glück hängt die Pfadlänge nur davon ab, wie oft p1 und p2 im Mittelteil abgelaufen wurden, und nicht von der der Reihenfolge:
$\begin{eqnarray*} l(p_{n,k})=l(p_0)+kl(p_1)+(n-k)l(p_2)+l(p_3)=2+2k+4(n-k)+1=3+4n-2k \end{eqnarray*}$

Bleibt, den Erwartungswert der Pfadlänge zu bestimmen:
$\begin{eqnarray*} E[l]&=&\sum_{p_{n,k}}l(p_{n,k})P(p_{n,k})=\sum_{n=0}^\infty2^{-(2n+1)}\sum_{k=0}^n\binom{n}{k}(3+4n-2k)&\left|k\binom{n}{k}=n\binom{n-1}{k-1}\right. &=&\sum_{n=0}^\infty2^{-(2n+1)}\sum_{k=0}^n(3+4n)\binom{n}{k}-2n\binom{n-1}{k-1}&\left|\sum_{k=0}^n\binom{n}{k}=2^n\right. &=&\sum_{n=0}^\infty2^{-(2n+1)}\left((3+4n)2^n-2n\cdot 2^{n-1}\right)=\frac{3}{2}\sum_{m=0}^\infty(n+1)2^{-n}=\frac{3}{2}\cdot\frac{1}{\left(1-\frac{1}{2}\right)^2}=\fbox{6} \end{eqnarray*}$

Die Spinne muss im Mittel 6 Kanten ablaufen, um die Fliege zu fressen!

18.02.2020, 12:05

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von CrazyL
Die Spinne muss im Mittel 6 Kanten ablaufen, um die Fliege zu fressen!

Richtig und ganz tolle Rechnung!

Meine Einkleidung der Aufgabe enthält einen unsubtilen Hinweis. Würde ein Mathelehrer erwarten, dass seine Schüler eine Rechnung wie die deine stemmen können? Es können sich daher noch weitere Interessenten an der Aufgabe versuchen.

18.02.2020, 13:04

CrazyL

Auf diesen Beitrag antworten »

Nope, deshalb war ich auch etwas verwundert, dass das Problem so kompliziert wurde smile

Aber es gibt ja auch (Mathe-)Lehrer, die bewusst Knobelaufgaben hineinstreuen - zumindest in der Oberstufe^^

Und gerade die Reihe $\begin{eqnarray*} \sum_{k=0}^\infty kq^k \end{eqnarray*}$ war so ein Kandidat, der den Mathe-LK so richtig zum Rauchen gebracht hat! Mal schaun, ob ein komplett anderer Blick eine einfachere Lösung entdecken lässt...

18.02.2020, 13:13

Huggy

Auf diesen Beitrag antworten »

Etwas Knobelei steckt schon in der Aufgabe.

Bei der Spinne, die eine gerade durchlaufene Kante auch unmittelbar danach eventuell wieder durchläuft, gibt es eine für Schüler zugängliche Lösung. Bei der Spinne, die das nicht tut, ist etwas Knobelei (keine Rechnerei) erforderlich, wie man diese Lösungsmethode anwenden kann.

18.02.2020, 14:06

Nils Hoppenstedt

Auf diesen Beitrag antworten »

Zitat:

Bei der Spinne, die eine gerade durchlaufene Kante auch unmittelbar danach eventuell wieder durchläuft, gibt es eine für Schüler zugängliche Lösung.

8 Schritte wäre wohl zu einfach, oder?

18.02.2020, 14:13

Huggy

Auf diesen Beitrag antworten »

Zu einfach wäre das sicher nicht. Aber ist es richtig? Dazu möchte ich im Moment nichts sagen.

18.02.2020, 14:20

Nils Hoppenstedt

Auf diesen Beitrag antworten »

Ok, also meine Denke war die Folgende: in dem Falle, dass jede Kante auch wieder zurück gelaufen werden kann, haben wir eine total symmetrische Wanderstrecke: an jeder Ecke gibt es 3 mögliche Kanten, die alle mit der gleichen Wahrscheinlichkeit gewählt werden können. Nach sehr vielen Schritten wird die Spinne also jeden der 8 Ecken im Mittel gleich häufig besucht haben. Mit anderen Worten: egal, wo die Spinne startet sie erreicht jede Ecke im Mittel nach 8 Schritten.

18.02.2020, 14:29

Huggy

Auf diesen Beitrag antworten »

Das ist eine Plausibilitätsbetrachtung und sie ist nicht überzeugend. Die möglichen Konfigurationen von Startpunkt und Zielpunkt sind nicht alle symmetrisch zueinander. Nimm als Alternative zu der Aufgabe mal einen Zielpunkt, der dem Startpunkt benachbart ist.

Die vom Lehrer angedachte Lösung erfordert schon eine Rechnung, aber eine recht einfache.

18.02.2020, 14:35

Nils Hoppenstedt

Auf diesen Beitrag antworten »

Ist die Lösung denn richtig? Oder bin ich total auf dem falschen Dampfer??

Wie gesagt: damit alle Punkte gleich häufig besucht werden, muss von jedem Startpunkt aus jede beliebige Ecke (also insbesondere auch die benachbarten, sowie der Startpunkt selbst) im Mittel nach 8 Schritten erreicht werden.

18.02.2020, 14:38

Huggy

Auf diesen Beitrag antworten »

Diese Frage wollte ich eigentlich jetzt noch nicht beantworten, weil ja andere vielleicht noch knobeln Aber seis drum: 8 ist nicht richtig!

Nachtrag: Mal angenommen, deine Hypothese sei richtig und die Zielecke sei der Startecke benachbart. Dann wird die Zielecke mit Wahrscheinlichkeit 1/3 in einem Zug erreicht. Mit Wahrscheinlichkeit 2/3 wird im ersten Zug eine andere Ecke erreicht. Von dieser braucht man laut deiner Hypothese im Mittel 8 Züge bis zur Zielecke. Dann errechnet sich die mittlere Zugzahl von der Startecke zur Zielecke zu:

$\begin{eqnarray*} \frac 1 3 \cdot 1 + \frac 2 3 \cdot (1+8) \neq 8 \end{eqnarray*}$

Widerspruch!

18.02.2020, 15:03

Nils Hoppenstedt

Auf diesen Beitrag antworten »

Hmmm ok, stimmt. Das war dann wohl doch zu einfach gedacht. Schade...

Nachtrag: mein Ansatz gilt wohl erst im Langzeitmittel, wenn also die Spinne schon sehr lange unterwegs ist und die Startecke keine Rolle mehr spielt.

18.02.2020, 15:51

HAL 9000

Auf diesen Beitrag antworten »

Ich würde das ganze so angehen:

a) Erstmal die degenerierte Spinne. Für die sei $\begin{eqnarray*} m_k \end{eqnarray*}$ die mittlere Anzahl benötigter Schritte bis zur Fliege, wenn sie noch $\begin{eqnarray*} k \end{eqnarray*}$ Kanten von ihr entfernt ist. Dann kann man das Gleichungssystem

$\begin{eqnarray*} m_3 = 1+m_2 \end{eqnarray*}$
$\begin{eqnarray*} m_2 = 1 + \frac{1}{3}m_3 + \frac{2}{3}m_1 \end{eqnarray*}$
$\begin{eqnarray*} m_1 = 1 + \frac{2}{3}m_2 \end{eqnarray*}$

aufstellen, mit der Lösung $\begin{eqnarray*} m_1=7,m_2=9,m_3=10 \end{eqnarray*}$ , d.h., die Antwort auf deine Frage wäre 10.

b) Bei der nichtdegenerierten Spinne ist es etwas komplizierter: Da reicht ein $\begin{eqnarray*} m_2 \end{eqnarray*}$ nicht, man muss auch wissen, ob der letzte Schritt von 1 oder von 3 kam. Das hängen wir mal als zweiten Index an und erhalten

$\begin{eqnarray*} m_3 = 1 + m_{2,3} \end{eqnarray*}$
$\begin{eqnarray*} m_{2,3} = 1 + m_1 \end{eqnarray*}$
$\begin{eqnarray*} m_{2,1} = 1 + \frac{1}{2}m_3 + \frac{1}{2}m_1 \end{eqnarray*}$
$\begin{eqnarray*} m_1 = 1 + \frac{1}{2}m_{2,1} \end{eqnarray*}$

Das ergibt Lösung $\begin{eqnarray*} m_1 = 4,m_{2,3}=5,m_{2,1}=6,m_3=6 \end{eqnarray*}$ , d.h., als gesuchten Wert den schon von CrazyL anderweitig ausgerechneten Wert 6.

Zitat:

Original von Huggy
Bei der Spinne, die das nicht tut, ist etwas Knobelei (keine Rechnerei) erforderlich, wie man diese Lösungsmethode anwenden kann.

Tja, das ist mir auch nicht geglückt. Allerdings hält sich die "Rechnerei" ja bei mir in überschaubaren Grenzen, so dass sich mein Gram darob in Grenzen hält. Big Laugh

18.02.2020, 17:07

Huggy

Auf diesen Beitrag antworten »

Das ist der Weg, den sich der Lehrer für die degenerierte Spinne vorgestellt hat.

Zitat:

Original von HAL 9000

Zitat:

Original von Huggy
Bei der Spinne, die das nicht tut, ist etwas Knobelei (keine Rechnerei) erforderlich, wie man diese Lösungsmethode anwenden kann.

Tja, das ist mir auch nicht geglückt. Allerdings hält sich die "Rechnerei" ja bei mir in überschaubaren Grenzen, so dass sich mein Gram darob in Grenzen hält. Big Laugh

Das ist auch ein einfacher Weg.

Alternativ kann man hier immer zwei Züge zu einem Zug zusammenfassen, den ich mal Zweizug nenne. Von der Startecke gelangt in einem Zweizug zu 3 möglichen. Ecken. Von diesen gelangt man in einem Zweizug wieder zur Startecke oder zu einer anderen dieser 3 Ecken oder in einem Einzug zur Zielecke. Damit kann man ein ähnliches, sogar etwas einfacheres Gleichungssystem aufstellen, wie bei der degenerierten Spinne. Wenn man will, kann man die Einzüge zur Zielecke auch als Zweizüge ansehen. Dann muss man zum Schluss von dem berechneten Erwartungswert wieder 1 abziehen.

18.02.2020, 17:39

HAL 9000

Auf diesen Beitrag antworten »

Mit dem Gedanken an die Zweizüger habe ich auch kurz gespielt, aber verworfen: Denn in meinem reinen Einzug-System fallen auch die mittleren Wege von allen anderen Ecken quasi als Nebenprodukte mit ab, ist ja vielleicht auch interessant. Augenzwinkern

18.02.2020, 17:55

Huggy

Auf diesen Beitrag antworten »

Stimmt. Bei der Zweizugmethodik hat man 3 Ecken, deren Erwartungswert nicht bestimmt wird, weil sie nur in der Mitte eines Zweizugs erreicht werden. Deren Erwartungswert ergibt sich dann aber aus den Wahrscheinlichkeiten, mit der man von ihnen in einem Einzug auf Ecken kommt, deren Erwartungswert man jetzt schon kennt.

19.02.2020, 03:16

CrazyL

Auf diesen Beitrag antworten »

Die Idee, die Punkte in Klassen einzuteilen, war also doch richtig - aber das Ordnen der Pfade nach Zyklen hat die Rechnung unnötig kompliziert gemacht. Mit Gleichungssystemen / Matrizen wird das viel eleganter. Vielleicht kommt man ja auch an die W.-Verteilung von Position und Länge? Also noch mal, Klappe die zweite:

Modellierung: Das Netz der Spinne ist der Einheitswürfel, die Fliege hängt im Ursprung und die Spinne startet auf der Ecke gegenüber der Fliege. Das Netz ist rotationssysmmetrisch zur Raumdiagonalen, also ordnen wir die Eckpunkte in Klassen:
$\begin{eqnarray*} Q&:=&\{0;1\}^3,&\text{// Eckpunkte des Würfels mit Kantenlänge 1} S_k&:=&\{x\in Q|\:\|x\|_1=k\},\quad k\in\{0;\ldots;3\}&\text{// Menge aller Eckpunkte mit Abstand $k$ zur Fliege in $S_0$, die Spinne startet in $S_{3}$} \end{eqnarray*}$

Solange die Spinne die Fliege noch nicht gefangen hat, springt sie zwischen geraden und ungeraden Klassen hin- und her. Das sieht man besonders gut im Baumdiagramm - lies dort ab, mit welcher W.-keit sich die Spinne nach Schritt $\begin{eqnarray*} n \end{eqnarray*}$ in Klasse $\begin{eqnarray*} S_k \end{eqnarray*}$ befindet:
$\begin{eqnarray*} p_{k,n}&:=&P(\text{$S_k$ nach $n$ Schritten}),\quad&\vec{x}_n:=(p_{1,n},\:p_{3,n})^T,\quad x_0=(0;\:1)^T \vec{x}_{n+2} &=& \begin{pmatrix}\frac{4}{9} & \frac{2}{3} \frac{2}{9} & \frac{1}{3} \end{pmatrix}\vec{x}_n=:P_a\vec{x}_n&\text{// degenerierte Spinne (Typ a)} \vec{x}_{n+2} &=& \begin{pmatrix}\frac{1}{4} & 1 \frac{1}{4} & 0 \end{pmatrix}\vec{x}_n=:P_b\vec{x}_n,&\text{// nicht-degenerierte Spinne (Typ b)} \end{eqnarray*}$

Lösung: Sei $\begin{eqnarray*} m_k \end{eqnarray*}$ der Erwartungswert des Wegs, den die Spinne zurücklegt, wenn sie in Klasse $\begin{eqnarray*} S_k \end{eqnarray*}$ mit Abstand $\begin{eqnarray*} k \end{eqnarray*}$ zur Fliege startet. Mit $\begin{eqnarray*} \vec{m}:=(m_1,\:m_3) \end{eqnarray*}$ , dem Baumdiagramm und den beiden Matrizen bekommen wir zwei Gleichungssysteme
$\begin{eqnarray*} \vec{m}&=&P_a^T(\vec{m}+2\cdot\vec{1})+1\cdot\begin{pmatrix}\frac{1}{3} 0 \end{pmatrix}\quad&\Rightarrow\quad\vec{m}&=&\begin{pmatrix}7 \fbox{10} \end{pmatrix}&\text{//degenerierte Spinne (Typ a)} \vec{m}&=&P_b^T(\vec{m}+2\cdot \vec{1})+1\cdot\begin{pmatrix}\frac{1}{2} 0 \end{pmatrix}\quad&\Rightarrow\quad\vec{m}&=&\begin{pmatrix}4 \fbox{6} \end{pmatrix}&\text{//nicht-degenerierte Spinne (Typ b)} \end{eqnarray*}$

Die degenerierte Spinne läuft im Mittel über 10 Kanten, bevor sie die Fliege frisst - die nicht-degenerierte Spinne im Mittel nur über 6! $\begin{eqnarray*} \blacksquare \end{eqnarray*}$

Anm.: Jeder Pfad von einem Punkt in $\begin{eqnarray*} S_1,\:S_3 \end{eqnarray*}$ zur Fliege enthält entweder einen um zwei Kanten kürzeren Teilpfad von $\begin{eqnarray*} S_1,\:S_3 \end{eqnarray*}$ zur Fliege (mit entsprechend reduzierter W.-keit), oder er hat Länge Eins und geht mit entsprechender W.-keit direkt zur Fliege.

Diese Eigenschaft überträgt sich auf den Erwartungswert - das sollte genau der Trick sein, den HAL 9000 schon vorher beim Einschrittsystem verwendet hat. Das LGS fürs Zweizugsystem ist tatsächlich kleiner!

19.02.2020, 10:07

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von CrazyL
Die Idee, die Punkte in Klassen einzuteilen, war also doch richtig

Das reduziert jedenfalls den Aufwand deutlich. Man kann auch jede Ecke individuell eingehen lassen. Dann hat man aber ein deutlich größeres lineares Gleichungssystem.

Zitat:

Das Netz ist rotationssysmmetrisch zur Raumdiagonalen

Bei den Symmetrien des Würfels denkt man meistens an Drehungen um Vielfache von 90° und an Spiegelungen. Bei den Drehungen um die Raumdiagonale sind es aber inteessanterweise Drehungen um Vielfache von 120°, die den Würfel in sich überführen.

19.02.2020, 10:10

HAL 9000

Auf diesen Beitrag antworten »

Unterhaltsamer als das bis ins letzte formelmäßig auszuwalzen wäre es vielleicht, die Spinne auf die anderen vier platonischen Körper loszulassen. Big Laugh

EDIT: Hab das mal für das Dodekaeder durchgerechnet. Da kommt es bei der "normalen" (d.h. nicht degenerierten) Spinne zu einem überraschenden Resultat (hoffentlich nicht, weil ich mich verrechnet habe):

Man kann ja auch hier die 20 Eckpunke nach ihrer Kanten-Entfernung zur Fliege in 6 Schichten einteilen:

0 die Fliege selbst
1 Kante (3 Punkte)
2 Kanten (6 Punkte)
3 Kanten (6 Punkte)
4 Kanten (3 Punkte)
5 Kanten (1 Punkt)

Die längste mittlere Schrittzahl bis zur Fliege hat man nun weder in Schicht 5 noch Schicht 4, sondern in Schicht 3 unter der Bedingung, dass der letzte Schritt aus Schicht 2 erfolgte!!! Und zwar im Mittel $\begin{eqnarray*} \frac{56}{3}\approx 18.7 \end{eqnarray*}$ Schritte. Die beiden nächstschlechteren waren Schicht 5 sowie Schicht 4 unter der Bedingung, dass der letzte Schritt aus Schicht 3 erfolgte, beide jeweils mit im Mittel $\begin{eqnarray*} \frac{55}{3}\approx 18.3 \end{eqnarray*}$ Schritten.

Neue Frage »

Antworten »

Spinne und Fliege

Verwandte Themen