Knobelaufgabe

03.05.2008, 00:52

~111~

Knobelaufgabe

Ich sitze gerade an einer Knobelaufgabe, die wir in Lineare Algebra aufbekommen haben und hab richtig Probleme sie zu lösen, da ich noch nicht mal weiß in welche Richtung diese Aufgabe gehen soll, ob man sie z. B. mit vollständiger Induktion lösen kann oder ganz anders.

Also, hier ist sie:

n >= 3 Zwerge sitzen im Kreis um einen runden Tisch; jeder hat einen
großen Becher Milch vor sich. Der erste verteilt seine Milch zu gleichen
Teilen auf die Becher seiner Nachbarn. Danach tut dies der zweite, der
dritte usw. Nachdem der n−te seine Milch verteilt hat, hat jeder wieder
soviel Milch im Becher wie zu Anfang. Wieviel hatte jeder zuerst, wenn
im ganzen n Liter Milch verteilt waren?

Ich denke, dass der n-te Zwerg 0 Liter, der Erste 2 Liter und alle anderen 1 Liter Milch haben müssen und ich habe auch schon ein paar Formel rausgefunden:

a(i) = 0.5a(i+1) + 0.5a(i-1)
a(1) = 0.5a(2) + 0.25a(1) + a(n-1)
a(n-1) = 0.5a(n-2) + 0.25a(1)
a(n) = 0
Summe von allen a(i) = n

Wobei a(1) der erste Zwerg ist und a(i) alle Zwerge zwischen dem ersten und dem n-1-ten Zwerg sind und a(n) der letzte Zwerg ist.

Ich habe es dann hier mit der vollständigen Indukion probiert, wobei der Induktionsanfang kein Problem war, aber der Induktionsschritt will einfach nicht klappen.
Ich wäre euch sehr dankbar, wenn mir jemand weiterhelfen könnte, da ich wirklich schon am Verzweifeln bin. Wie gesagt, ich habe keine Ahnung, ob mein Ansatz so überhaupt funkrioniert, vielleicht ist die Aufgabe auch ganz anders zu lösen.
Schon mal vielen Dank im Voraus, ihr würdet mir wirklich wieterhelfen!!!

03.05.2008, 07:08

WebFritzi

Auf diesen Beitrag antworten »

Es seien $\begin{eqnarray*} a_0\in\mathbb R^n \end{eqnarray*}$ die gesuchte Anfangsverteilung und A die nxn-Matrix, welche den Übergang von der Anfangs- zur ersten Verteilung beschreibt (kein Bock, die jetzt hier reinzuschreiben). Dann ist die n-te (also die letzte) Verteilung gegeben durch

$\begin{eqnarray*} (S_{n,n-1}S_{n-1,n-2}\dots S_{2,1}A)^n a_0, \end{eqnarray*}$

wobei $\begin{eqnarray*} S_{i,j} \end{eqnarray*}$ die Vertauschung von i-ter und j-ter Zeile (bei Anwendung von links) beschreibt.

Hat mich ganz schön Zeit gekostet, das hinzubekommen. Aber ist ja auch ne Knobelaufgabe. Augenzwinkern

03.05.2008, 09:25

Auf diesen Beitrag antworten »

Man kann natürlich auch gleich $\begin{eqnarray*} P:=S_{n,n-1}S_{n-1,n-2}\dots S_{2,1} \end{eqnarray*}$ als eine einzige zyklische Permutation(smatrix) voller Ordnung n schreiben: "eins weiterrücken im Kreis" Augenzwinkern

Die von ~111~ angegebene Lösung $\begin{eqnarray*} a \end{eqnarray*}$ ist natürlich richtig, dazu genügt der Nachweis, dass sie Fixpunkt von $\begin{eqnarray*} PA \end{eqnarray*}$ ist, d.h., dass $\begin{eqnarray*} PA\cdot a = a \end{eqnarray*}$ ist - kann man sogar verbal führen:

Zwerg 1 verteilt seine 2 Liter zu gleichen Teilen von jeweils 1 Liter an seine Nachbarn. Wenn man jetzt um eine Position weiter rückt, dann hat der "neue" Zwerg 1 (= alte Zwerg 2) jetzt 2 Liter in seinem Becher, der neue Zwerg n (=alte Zwerg 1) 0 Liter und alle anderen 1 Liter Milch - das ist bis auf die Neunummerierung die Ausgangslage!

Mathematisch streng genommen müsste man noch nachweisen, dass dieses $\begin{eqnarray*} a \end{eqnarray*}$ tatsächlich auch der einzige Fixpunkt von $\begin{eqnarray*} (PA)^n \cdot a=a \end{eqnarray*}$ ist. Mit eine bissel Markovkettentheorie (hier liegt eine endliche ergodische Markovkette vor) kein Problem, andernfalls ist es vielleicht etwas komplizierter...

03.05.2008, 15:52

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Mathematisch streng genommen müsste man noch nachweisen, dass dieses $\begin{eqnarray*} a \end{eqnarray*}$ tatsächlich auch der einzige Fixpunkt von $\begin{eqnarray*} (PA)^n \cdot a=a \end{eqnarray*}$ ist. Mit eine bissel Markovkettentheorie (hier liegt eine endliche ergodische Markovkette vor) kein Problem

Ja, wenn man sowas zur Hand hat, dann ist es wohl von Vorteil. Ich hab das nicht. Augenzwinkern

Man kann aber mit etwas Aufwand das charakteristische Polynom von PA bestimmen und zeigen, dass 1 eine einfache Nullstelle davon ist. Natürlich sind auch Vielfache von (2,1,1,....,1,0) Fixpunkte. Die sind ja aber nicht zugelassen, da die Summe der Einträge ja n sein soll.

03.05.2008, 18:11

~111~

Auf diesen Beitrag antworten »

Erst mal vielen, vielen Dank für die Antworten! Jetzt weiß ich zumindest in welche Richtung dieses Aufgabe geht und dass es nicht per Induktion funktioniert!
Allerdings wäre ich euch sehr dankbar, wenn ihr mir noch einen Tipp geben könntet, wie man zu der nxn-Matrix kommt, die die Verteilung beschreibt. Ich bin mit Matrizen noch nicht so vertraut, deswegen fällt mir das nochetwas schwer!

04.05.2008, 05:09

WebFritzi

Auf diesen Beitrag antworten »

Sei a(j,k) die Menge an Milch des j-ten Zwerges nach dem k-ten Durchgang. a(j,0) ist dann natürlich die Anfangsverteilung. Man kommt nun von a(.,0) zu a(.,1) wie folgt:

a(1,1) = 0 (der hat ja seine Milch verschenkt)
a(2,1) = 1/(n-1) * a(1,0) + a(2,0)
a(3,1) = 1/(n-1) * a(1,0) + a(3,0)
usw... bis...
a(n,1) = 1/(n-1) * a(1,0) + a(n,0).

Schreibt man a(1,1), a(2,1), ... , a(n,1) und a(1,0), a(2,0), ... ,a(n,0) jeweils in einen Spaltenvektor a(0) bzw. a(1), dann lassen sich diese Gleichung als lineares Gleichungssystem in Matrixform schreiben:

a(1) = A(1) * a(0).

Dabei sieht A(1) wie folgt aus

$\begin{eqnarray*} A(1) = \begin{pmatrix}0 & 0\\\frac{1}{n-1}{\bf 1}_{n-1} & E_{n-1}\end{pmatrix}. \end{eqnarray*}$

Dabei sei $\begin{eqnarray*} {\bf 1}_{n-1} \end{eqnarray*}$ der (n-1)-zeilige Vektor, der nur Einsen als Einträge hat, und $\begin{eqnarray*} E_{n-1} \end{eqnarray*}$ die (n-1)-zeilige (und (n-1)-spaltige) Einheitsmatrix.

Wenn du nun noch die Matrix A(2) erstellst, die dir das Gleichungssystem

a(2) = A(2) * a(1)

gibt, dann wirst du sehen, dass sich A(2) durch Vertauschen von 1. und 2. Zeile und danach nochmal Vertauschen von 1. und 2. Spalte von A(1) entsteht. Das kann man auch so schreiben:

$\begin{eqnarray*} A(2) = S_{1,2}A(1)S_{1,2}. \end{eqnarray*}$

Allgemein gilt

$\begin{eqnarray*} A(k) = S_{k-1,k}A(k-1)A_{k-1,k}. \end{eqnarray*}$

04.05.2008, 05:16

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Zwerg 1 verteilt seine 2 Liter zu gleichen Teilen von jeweils 1 Liter an seine Nachbarn.

Das geht doch nur bei n=3. Augenzwinkern

04.05.2008, 09:20

Auf diesen Beitrag antworten »

"Nachbarn" sind nur die beiden, die direkt einen Platz links und rechts neben ihm sitzen - so habe ich die Aufgabe verstanden.

04.05.2008, 16:41

WebFritzi

Auf diesen Beitrag antworten »

Oh weh. Ich hab mal wieder die Aufgabe falsch verstanden. traurig

Das lustige ist aber, dass dasselbe rauskommt. smile

@~111~: Es geht auch viel einfacher als ich es dir gesagt hatte. Ohne groß zu rechnen kann man einsehen, dass

$\begin{eqnarray*} A(2) = P^{-1}A(1)P \end{eqnarray*}$

gilt, und allgemein

$\begin{eqnarray*} A(k) = P^{1-k}A(1)P^{k-1}. \end{eqnarray*}$

Man kann jetzt mit vollständiger Induktion zeigen, dass

$\begin{eqnarray*} A(k)A(k-1)\dots A(2)A(1) = P^{-k}(PA(1))^k. \end{eqnarray*}$

Da aber $\begin{eqnarray*} P^{-n} = E \end{eqnarray*}$ gilt (Einheitsmatrix), hat man

$\begin{eqnarray*} A(n)A(n-1)\dots A(2)A(1) = (PA(1))^n. \end{eqnarray*}$

Und das ist die Matrix, die die Endverteilung beschreibt (erstmal ganz unabhängig davon wie A(1) aussieht).

04.05.2008, 16:49

Auf diesen Beitrag antworten »

Du hast es also so verstanden, dass der Zwerg seine Milch gleichmäßig an die anderen $\begin{eqnarray*} n-1 \end{eqnarray*}$ verteilt? Geht natürlich auch - ist natürlich etwas umständlich, wenn man sich die Milchschütterei bildlich vorstellt. Big Laugh

Zitat:

Original von WebFritzi
Das lustige ist aber, dass dasselbe rauskommt.

Aber nicht die Fixpunktverteilung im Fall $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ - die wäre dann eine andere! verwirrt

04.05.2008, 18:01

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Zitat:

Original von WebFritzi
Das lustige ist aber, dass dasselbe rauskommt.

Aber nicht die Fixpunktverteilung im Fall $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ - die wäre dann eine andere! verwirrt

Ja, OK. Ich meinte auch eher, dass 1 auch ein Eigenwert ist. Oder ist das vielleicht immer so bei solchen Matrizen (deren Spaltensumme stets 1 ist)?

04.05.2008, 18:03

Auf diesen Beitrag antworten »

Ja, das ist bei stochastischen Matrizen immer so. Lässt sich leicht nachweisen, da ja $\begin{eqnarray*} (1,1,\ldots,1) \end{eqnarray*}$ ein dazu passender Linkseigenvektor ist.

04.05.2008, 18:35

WebFritzi

Auf diesen Beitrag antworten »

Öhem, jo.

Neue Frage »

Antworten »

Knobelaufgabe

Verwandte Themen