|
Karls Spielkiste #8
Zurück
Umfüllaufgabe
Das Bertrandsche Paradoxon
Stammbrüche
Was ist wahrscheinlicher?
Kettenbrüche
Wolf, Ziege und Kohl
Die halbe Wahrheit
Russische Multiplikation
Die Türme von Hanoi
--- Antworten ---
Umfüllaufgabe:
Gegeben sind 3 Gefäße mit 3l, 5l und 8l Inhalt, wobei das 8l Gefäß voll mit Wasser und die
beiden anderen Gefäße leer sind. Wie müssen die Gefäße umgeschüttet werden, um zu
erreichen, daß zwei Gefäße jeweils genau 4l Wasser enthalten? An den Gefäßen gibt es keine
Markierungen, so daß die Gefäße immer entweder ganz gefüllt oder vollständig geleert werden
müssen, um zu wissen, wieviel Wasser in ihnen ist.
Das Bertrandsche Paradoxon:
Wie groß ist die Wahrscheinlichkeit, daß eine in einem Kreis zufällig eingezeichnete Sehne
länger ist als die Seite eines in diesem Kreis einbeschriebenen gleichseitigen Dreiecks?
Hierfür gibt es 3 verschiedene Lösungsansätze:
Abb. 1: Alle Punkte auf dem Kreis sind als Schnittpunkte der Sehne gleich wahrscheinlich.
Hält man einen Schnittpunkt (schwarz) fest, so ist die Sehne nur dann länger, wenn der
zweite Schnittpunkt (rot) auf einem Kreisbogen (rot) von 60° liegt -> p = 60°/180° = 1/3.
Abb 2: Alle Mittelpunkte der Sehnen im Umkreis (blau) sind gleich wahrscheinlich. Die Sehne
ist genau dann länger, wenn der Mittelpunkt (rot) der Sehne im Innkreis (rot; = 0.5*RUmkreis)
des Dreiecks liegt -> p = (R/2)2/R2 = 1/4.
Abb 3: Alle Richtungen der Sehnen sind gleich wahrscheinlich. Die Sehne ist genau dann länger,
wenn der Abstand der Sehne vom Mittelpunkt des Umkreises kleiner als der halbe Radius R
des Umkreises ist -> p = (R/2)/R = 1/2.
Welcher Lösungsansatz ist nun der richtige?
Stammbrüche:
Wie läßt sich der Bruch 5/7 durch eine Summe aus Brüchen der Form 1/n (Stammbrüche)
darstellen?
Was ist wahrscheinlicher?
a) bei 4 mal Werfen mit einem Würfel mindestens eine Sechs zu würfeln, oder
b) bei 24 mal Werfen mit zwei Würfeln mindestens eine Doppelsechs zu würfeln?
Bei a) stehen den 4 Würfen 6 Möglichkeiten gegenüber = 4/6;
bei b) stehen den 24 Würfen 36 Möglichkeiten gegenüber = 24/36 = 4/6 !
Kettenbrüche:
Wie läßt sich der Bruch 5/7 durch einen Kettenbruch der Form n0 + 1/(n1 + 1/(n2 +1/( ...)))
darstellen?
Wolf, Ziege und Kohl:
Ein Bauer möchte seinen Wolf, seine Ziege und seinen Kohl mit einem Boot über einen Fluß
transportieren. Da das Boot sehr klein ist, kann der Bauer immer nur ein Tier oder nur den
Kohl auf einmal transportieren. Wie muß der Bauer vorgehen, wenn er vermeiden möchte, daß
der Wolf die Ziege oder die Ziege den Kohl frißt, sobald sie alleine gelassen werden?
Die halbe Wahrheit:
Auf einer Karte steht auf der Vorderseite: “Der Satz auf der Rückseite dieser Karte ist wahr”
und auf der Rückseite: “Der Satz auf der Vorderseite dieser Karte ist falsch”. Welcher Satz
ist nun wahr? Läßt man nur die Aussaggen “wahr” und “falsch” zu, so ergibt sich immer ein
Widerspruch. Wie sieht es aus, wenn man für die Wahrheit Werte von 0% - 100% zuläßt
(0% bedeutet z.B. falsch, 90% fast wahr, 100% wahr, usw.?)
Russische Multiplikation:
Die russische Multiplikation geht so: Links wird eine Tabelle erstellt, die beginnend mit dem
1. Faktor in der nächsten Zeile immer die Hälfte (nach unten abgerundet) der darüberliegenden
Zeile enthält. Rechts wird eine Tabelle beginnend mit dem 2. Faktor und dem jeweils Doppel-
tem der darüberliegenden Zeile in der nächsten Zeile erzeugt, bis diese gleich viele Einträge
wie die linke Spalte hat. Nun werden in der rechten Spalte alle Zahlen gestrichen, die auf
gleicher Höhe in der linken Spalte eine gerade Zahl enthalten. Die Summe aller nicht
gestrichenen Zahlen ergibt den Produkt der beiden oben stehenden Faktoren. Wieso
funktioniert das?
Beispiel: 73 * 111
73 111
36 222 (gestr,)
18 444 (gestr.)
9 888
4 1776 (gestr.)
2 3552 (gestr.)
1 7104
= 8103
Die Türme von Hanoi:
Gegeben sind 3 Scheiben von unterschiedlichem Durchmesser. Für diese 3 Scheiben stehen 3
Ablageplätze zur Verfügung, auf denen die Scheiben gestapelt werden können. Beim Ablegen
der Scheiben muß eine Regel strikt eingehalten werden: Es darf nie eine größere Scheibe auf
eine kleinere Scheibe gelegt werden! Wie muß man vorgehen, um alle 3 Scheiben, die nach
der Größe sortiert auf einem Ablageplatz liegen, auf einen anderen Ablageplatz umzulegen?
--- Antworten ---
Umfüllaufgabe
(008)
1o
(017)7o o6(107)
+ . +
(035)3o . . o2(305)
(044)9o . . o8 .
(314)
+ . . + . .
. 5o . o4 . . .
(152) (332)
. . + + . . . .
. . . + . . . . .
(350)
Obiges Diagramm zeigt eine geometrische Lösung des Problems. Der Zustand (008) ist der
Anfangszustand mit 8l Wasser im größten Gefäß. Der nächste Zug ist (305), d.h. das größte
Gefäß wird in das 3l Gefäß umgeschüttet, bis dieses voll ist. Danach wird immer entlang der
Nummern vorgegangen, bis man die Lösung (Nr. 9) mit (044) erhält.
Die Zahlen in (...) sind die Füllstände des 3l, 5l und 8l Gefäßes. Der Rand (aus + und o gebildet)
des Diagramms stellt die vollen bzw. leeren Gefäße dar; jeder Zug muß also diesen Rand
erreichen. Oben (008) ist das 8l Gefäß voll und unten (350) leer, am linken Rand (017), (035),
(044) ist das 3l Gefäß leer und am rechten Rand (107),(305) ist das 5l Gefäß leer. Das Umfüllen
der Gefäße wird durch die Bewegung in den 3 Richtungen: waagrecht, nach links unten
(bzw. rechts oben) und nach rechts unten (bzw. links oben) dargestellt; so bedeutet z.B. eine
waagrechte Bewegung nach links (314)-(044) ein Umfüllen des 3l in das 5l Gefäß und eine
Bewegung von links unten nach rechts oben (152)-(107) ein Umfüllen des 5l Gefäßes in das
8l Gefäß usw. Zweckmäßig beginnt man bei dieser Aufgabe bei der Lösung (044) und zieht
solange bis an die Ränder, bis der Ausgangszustand (008) erreicht wird.
Das Bertrandsche Paradoxon
Die Wahrscheinlichkeit hängt von der Konstruktionsvorschrift der Sehne ab!
Alle obigen Lösungsansätze sind damit also richtig!
Stammbrüche
5/7 = 1/2 + 1/5 + 1/70
So sieht der Algorithmus dazu aus:
a=Zähler, b=Nenner, i=1
1. ni = ceil (b/a) (ceil (n): nach oben aufgerundete ganze Zahl von n, z.B. ceil(1.01)=2, ceil(1)=1)
2. a = a*n - b
3. b = b*x
4. Wenn a>0: i=i+1, gehe zu 1.
5. Stop
a/b = 1/n1 + 1/n2 + ... (Summe aller Kehrwerte von ni)
Was ist wahrscheinlicher?
a) p = 1 - (5/6)4 = ~0.52
b) p = 1 - (35/36)4 = ~0.49; also ist a) wahrscheinlicher!
Kettenbrüche
5/7 = 0 + 1/(1 + 1/(2 + 1/2))
allgemeiner Algorithmus:
n0 = int(a/b); r2 = a mod b (int(n): nach unten abgerundete Zahl von n; a mod b: Rest bei a/b)
n1 = (b/r2); r3 = b mod r2
i = 2
1. ni = int(ri/ri+1); ri+2 = ri mod ri+1
2. Wenn ri+2 <> 0: i=i+1, gehe zu 1.
3. Stop
a/b = n0 + 1/(n1 + 1(n2 + 1/(...))); wird auch geschrieben als: a/b = [n0;n1;n2;...]
Wolf, Ziege und Kohl
001 011
o-----------o
\ |
\ 111 |
101 o-----o |
| |
| 110 |
100 o-----o |
\ |
\|
o----------o
000 010
Obiges Diagramm zeigt eine geometrische Lösung des Problems. Die Zahlen geben an, auf
welcher Seite sich Wolf, Ziege und Kohl (WZK) befinden; dabei bedeutet 0: Start-Ufer und
1: Ziel-Ufer. Ein Transport entspricht einer Bewegung zwischen 2 benachbarten Punkten
(wenn man sich das Modell als plattgedrückten Würfel vorstellt); erlaubt sind aber nur solche
Transporte, welche im Modell durch eine Linie miteinander nerbunden sind. Jetzt ist es nicht
mehr schwierig, vom Ausgangspunkt 000 zum Zielpunkt 111 einen Weg zu finden:
000 - 010 - 011 - 001 - 101 - 111 oder
000 - 010 - 110 - 100 - 101 - 111.
Die halbe Wahrheit
Mit v = Wahrheitsgehalt des Satzes auf der Vorderseite und r = Wahrheitsgehalt des Satzes
auf der Rückseite ergibt sich folgendes Gleichungssystem:
v = r (1)
r = 100% - v (2)
=> v = 100% - v (2) in (1) eingesetzt
=> v = 50% d.h. Der Satz auf der Vorderseite ist nur die halbe Wahrheit!
Russische Multiplikation
Stichwort: Multiplikation im Binärsystem!
Die Türme von Hanoi
Auch hier gibt es eine geometrische Lösung: Bezeichnet man die Ablageplätze mit 1,2 und 3
und die Scheiben in der Reihenfolge ihrer Größe mit A,B und C, so kann man jede mögliche
Stellung der Scheiben durch drei Zahlen beschreiben: die erste Zahl steht für den Ablage-
platz von Scheibe A, die zweite Zahl für B und die dritte Zahl für C. So bedeutet z.B. 112:
Scheibe A auf Platz 1, Scheibe B auch auf Platz 1 und Scheibe C aud Platz 2.
Modell:
111
211 311
231 321
331 131 121 221
332 223
132 232 323 123
122 121 313 133
222 322 312 112 113 213 233 333
Stehen z.B. alle 3 Scheiben auf Platz A und sollen auf Platz C kommen, so sind die folgenden
Züge nötig: 111 - 311 - 321 - 221 - 223 - 123 - 133 - 333. Das Modell ist selbstähnlich, d.h.
es treten immer wieder die gleichen Strukturen auf. So sieht z.B. das Modell für 2 Scheiben
so aus:
11
21 31
23 32
33 13 12 22
Es ist die obere Ecke des 3-Scheiben-Modells ohne die letzte “1”. Analog läßt sich das Modell
auch für 4 und mehr Scheiben aufbauen.
|
