Manfred Börgens
Mathematische Probleme  # 87
Liste aller Probleme mit Lösungen
voriges Problem      nächstes Problem
zur Leitseite


Münzwurf statt Würfeln


Die Kernfrage dieses Problems lautet:
      Wie kann man das Würfeln (mit einem gewöhnlichen 6-seitigen Würfel) durch eine Folge von Münzwürfen möglichst effizient ersetzen?

Über diese Frage kann man nachdenken, ohne die folgenden Ausführungen gelesen zu haben. Wer jedoch erst die Details kennenlernen möchte, die in der Kernfrage stecken, sollte weiterlesen.

Durch wiederholtes Werfen einer Münze kann man zufällige Folgen von  0  und  1  erzeugen. Durch Werfen eines Würfels erhält man zufällige Folgen von Zahlen aus  {1,2,3,4,5,6}. Wenn man einen Würfel braucht, aber keinen hat, kann man die Augenzahlen durch  3  Münzwürfe erzeugen, z.B. so:

000 → 1
001 → 2
010 → 3
011 → 4
100 → 5
101 → 6
110 → nochmal 3 Münzwürfe
111 → nochmal 3 Münzwürfe


Man braucht also im Durchschnitt mehr als  3  Münzwürfe, da man von den  8  möglichen Wurffolgen nur  6  verwenden kann. Das ist eine ungünstige Situation, die für bestimmte anders geformte "Würfel" nicht gilt. Hat der "Würfel" z.B.  4  Seiten (Tetraeder), benötigt man  2  Münzwürfe, bei einem  8-seitigen "Würfel" (Oktaeder) benötigt man  3  Münzwürfe, allgemein bei einem  2n-seitigen "Würfel"  n  Münzwürfe. Im Prinzip lassen sich alle  s-seitigen "Würfel" mit  s  2  herstellen ( s = 2  → Münze;  s  {4,6,8,12,20}  → platonische Körper; sonst prismenförmige Kreisel, siehe Bild).

Wuerfel
"Würfel" mit  s = 4, s = 8, s = 16  Seiten


Somit braucht man zur Erzeugung der Augenzahlen eines gewöhnlichen Würfels mehr Münzwürfe als bei einem  8-seitigen Würfel. Offenbar benötigt man das Minimum von  log2 s  Münzwürfen für  s  Würfelseiten genau dann, wenn  s  eine Zweierpotenz ist.

Ab hier wollen wir uns nur noch mit gewöhnlichen Würfeln mit  6  Seiten beschäftigen.

Aufgabe 1
Wie viele Münzwürfe braucht man im Durchschnitt, wenn man eine Münze in  3er-Folgen solange wirft, bis man eine Augenzahl zwischen  1  und  6  erzeugt hat?



Wir haben oben gesehen, dass  110  und  111  nicht brauchbar sind und zu erneutem Werfen der Münze führen. Aber das weiß man schon nach den beiden ersten Münzwürfen  11x , so dass man danach abbrechen und eine neue Serie starten kann. Also könnten z.B. die ersten drei erzeugten Augenzahlen  2, 4, 1  so zustande kommen:

11 001     → 2
011        → 4
11 11 000  → 1


Hier hätte man also für  3  Augenzahlen  15  Münzwürfe benötigt; ohne Abbruch wären es  18  gewesen.

Aufgabe 2
Wie viele Münzwürfe braucht man im Durchschnitt zur Erzeugung einer Augenzahl zwischen  1  und  6 , wenn man bei den nicht brauchbaren Würfen rechtzeitig abbricht?



Mit oder ohne Abbruch: Im Vergleich zum  8-seitigen "Würfel" (oder anderen  2n-seitigen "Würfeln") ist der Münzwurf als Ersatz zum normalen Würfeln umständlich. Für  s = 2n  sind lediglich  log2 s  Münzwürfe erforderlich; dieser Wert würde theoretisch für  s = 6  nur  log2 6  2,58496  betragen  -  tatsächlich braucht man deutlich mehr als  3  Münzwürfe, wie die Fragen 1 und 2 gezeigt haben.

Es gibt aber eine Möglichkeit, näher an den theoretischen Wert  log2 6  heranzukommen  -  sogar beliebig nahe. In der Regel wird man ja mehrere (oder viele) Augenzahlen erzeugen wollen, etwa für ein Gesellschaftsspiel. Dann möchte man also eine lange Folge von Augenzahlen zwischen  1  und  6  durch eine Folge von  0  und  1  darstellen. Nun kommt die gute Idee, wie man dies möglichst effektiv durchführt: Man erzeugt die Augenzahlen nicht einzeln (also durch jeweils  3  Münzwürfe), sondern man verkettet die Folge der Münzwürfe zu einer langen Binärzahl. Diese wird dann insgesamt (d.h. nicht abschnittsweise) transformiert in ebenfalls verkettete Augenzahlen. Also liegt es nahe, statt der Augenzahlen  1  bis  6  die Zahlen  0  bis  5  zu nehmen, um in der Basis  6  rechnen zu können, also in Hexalzahlen. Um es kurz zusammenzufassen:

Man rechnet eine Zahl zur Basis  2  in eine Zahl zur Basis  6  um. Die erste entspricht einer Folge von Münzwürfen, die zweite einer Folge von Augenzahlen beim Würfel.

Beispiel: Wir werfen  13-mal die Münze und erhalten damit die Binärzahl  00001011001102 . Transformation in die Hexalzahl ergibt:  00001011001102 = 013546  (entspricht den Augenzahlen  1, 2, 4, 6, 5 ). Die führende  0  in der Hexalzahl ist wichtig, denn wir erhalten mit diesem Verfahren immer genau  5  Augenzahlen: Mit  13  Münzwürfen kann man  213 = 8192  Zufallszahlen im Bereich  00000000000002  bis  11111111111112  erzeugen. Wegen  11111111111112 = 1015316  decken also die binären Zufallszahlen alle  5-stelligen Hexalzahlen  000006  bis  555556  ab. Die Binärzahlen  11110011000002  bis  11111111111112  können nicht verwertet werden, sie entsprechen nämlich den (sechsstelligen) Hexalzahlen von  1000006  bis  1015316 . Wir werden noch sehen, dass wir damit dem theoretischen Minimalwert für das Verhältnis Münzwürfe/Augenzahlen schon erheblich nähergekommen sind.

Im Folgenden soll  m  die Anzahl der Augenzahlen beim Würfeln sein, die man erzeugen möchte;  n = n(m)  sei die dafür erforderliche Anzahl von Münzwürfen.

Aufgabe 3
Berechnen Sie  n  aus  m .
Setzen Sie  am = n/m . Berechnen Sie das theoretische Minimum  a  der  am .


Aufgabe 4
Es sind nicht alle erzeugten binären Zufallszahlen verwertbar. Analog zu Aufgabe 1 stellt sich also die Frage:
Wie viele Münzwürfe  d1  braucht man im Durchschnitt, wenn man eine Münze in Folgen der Länge  n  solange wirft, bis man eine Hexalzahl der Länge  m  erzeugt hat?
Dafür ist es wie bei den Aufgaben 1 und 2 hilfreich, die Wahrscheinlichkeit  p  für die zufällige Erzeugung einer  n-stelligen Binärzahl zu berechnen, die einer  m-stelligen Hexalzahl entspricht.


Auch hier kann man bei den nicht verwendeten binären Zufallszahlen vorzeitig abbrechen. Man berechnet die größte verwertbare Binärzahl  v  (diese entspricht  55...56 ). Dann wirft man wiederholt die Münze für die binäre Zufallszahl, beginnend bei der vordersten Stelle (also bei der höchsten  2er- Potenz). Abbruch erfolgt, sobald eine Ziffer der Zufallszahl größer als die entsprechende Ziffer in  v  ist.

Aufgabe 5
Analog zu Aufgabe 2 stellt sich also die Frage: Wie viele Münzwürfe  d2  braucht man im Durchschnitt zur Erzeugung einer Hexalzahl der Länge  m , wenn man bei den nicht brauchbaren Würfen rechtzeitig abbricht?


Welche Werte von  m  sind besonders günstig? Das sind offenbar diejenigen, bei denen von den  2n  möglichen Wurffolgen nur wenige unbrauchbar sind. Also sucht man  m  mit  6m  2n  (dabei ist  6m  2n  wegen der Wahl von  n  gewährleistet).

Aufgabe 6
Machen Sie eine Tabelle für   1  m  50 , die folgende Werte enthält:
-    m 
-    n   (siehe Aufgabe 3)
-    p   (Anteil der brauchbaren binären Zufallszahlen)
-    d1   (durchschnittliche Anzahl insgesamt benötigter Münzwürfe bei nicht-abbrechendem Verfahren, siehe Aufgabe 4)
-    v1 = (d1/m)/a   (Verhältnis der durchschnittlichen Anzahl benötigter Münzwürfe für einzelne Augenzahlen zum theoretischen Minimum bei nicht-abbrechendem Verfahren)
-    d2   (durchschnittliche Anzahl insgesamt benötigter Münzwürfe bei abbrechendem Verfahren, siehe Aufgabe 5)
-    v2 = (d2/m)/a   (Verhältnis der durchschnittlichen Anzahl benötigter Münzwürfe für einzelne Augenzahlen zum theoretischen Minimum bei abbrechendem Verfahren)

Berechnen Sie überschlägig (d.h. in ungefährer Näherung) für große  n , was sich für die  di  und die  vi  in den extremen Fällen  p  1  bzw.  p  0,5  ergibt. Insbesondere ist dabei das folgende Ergebnis interessant:

p  0,5  ⇒  d2  n + 3


Die Tabelle zeigt große Unterschiede in der Effizienz der Münzwürfe für die Erzeugung von Würfel-Augenzahlen. Einen einzigen Würfelwurf oder zwei solche Würfe durch Münzwürfe zu ersetzen, erfordert einen unverhältnismäßig großen Aufwand. Aber  m = 5  oder  m = 41  erbringen sehr gute Ergebnisse mit  d1/m  und  d2/m  nahe bei  a . Ist das Zufall oder gibt es eine Gesetzmäßigkeit für die "guten"  m ? Dafür gibt es einen Ansatz:

Es gilt  n  a·m  ( a  kommt in der Lösung von Aufgabe 3 vor). Aussichtsreiche Kandidaten für  m , die ein effizientes Verfahren erlauben, kann man also durch Näherungsbrüche  b/c  a  finden; dann kann man  m = c  wählen und somit  n = b .

Damit kommen wir zur abschließenden Aufgabe. Der Faktor  a  aus Aufgabe 3 soll in hoher Genauigkeit als Bruch approximiert werden. Dafür gibt es das Verfahren der Kettenbrüche. Man benutzt am besten ein Programm, das die Kettenbruch-Folge  bi/ci  a  berechnet. Die Theorie der Kettenbrüche stellt sicher, dass  lim i→ bi/ci = a . Dabei sind die  bi/ci  abwechselnd  > a  und  < a .

Aufgabe 7
Bestimmen Sie mit Hilfe der Kettenbruchentwicklung, welche  m  sich besonders gut für eine effiziente Ersetzung von Hexalzahlen durch Binärzahlen eignen.



Lösung



Aufgabe 1
Wie viele Münzwürfe braucht man im Durchschnitt, wenn man eine Münze in  3er-Folgen solange wirft, bis man eine Augenzahl zwischen  1  und  6  erzeugt hat?


p  sei die Wahrscheinlichkeit, mit einem dreifachen Münzwurf eine der sechs Augenzahlen zu erzeugen. Nur  110  und  111  sind "Fehlversuche", also ist  p = 6/8 = 0,75 .

Bei  k  Fehlversuchen benötigt man  3  Münzwürfe für den erfolgreichen letzten Versuch und  3·k  Münzwürfe für die Fehlversuche. Die Wahrscheinlichkeit für genau  k  Fehlversuche, gefolgt vom ersten Erfolg, ist  (1-p)k·p (k  No) . Also ist der Erwartungswert  d1  für die Gesamtanzahl der Münzwürfe:

d1 = 3 + Σk≥0 k·(1-p)k·p

Bei der Berechnung der letzten Summe könnten wir es uns einfach machen: Das ist nämlich der Erwartungswert der geometrischen Verteilung und lässt sich leicht einer Formelsammlung entnehmen. Es sollen aber hier zwei mögliche Rechenwege angegeben werden. Wir setzen  q = 1 - p :

Σk≥0 k·qk = Σk≥0 (k+1)·qk - Σk≥0 qk = Σk≥1 k·qk-1 - 1/(1-q) = (1/q)·Σk≥0 k·qk - 1/(1-q)

    ⇒    Σk≥0
 k·qk = q/(1-q)2

Das kann man auch mit der Ableitung der geometrischen Reihe beweisen:

Σk≥0 qk = 1/(1-q)   (|q| < 1)      (ableiten) ⇒    Σk≥1 k·qk-1 = 1/(1-q)2   ⇒    Σk≥0 k·qk = q/(1-q)2

(1)   Also ist der Erwartungswert für die Anzahl der Fehlversuche  Σk≥0 k·(1-p)k·p = (1-p)/p

Es folgt:  d1 = 3 + 3·(1-p)/p = 4

Das bedeutet: Man benötigt genauso viele Münzwürfe wie beim 16-seitigen Würfel !


Aufgabe 2
Wie viele Münzwürfe braucht man im Durchschnitt zur Erzeugung einer Augenzahl zwischen  1  und  6 , wenn man bei den nicht brauchbaren Würfen rechtzeitig abbricht?


Alle notwendigen Rechnungen sind schon bei Aufgabe 1 erfolgt. Die einzige Änderung betrifft die Anzahl der Münzwürfe bei den Fehlversuchen ( 2  statt  3 ). Die durchschnittliche Anzahl von Münzwürfen nennen wir  d2 :

d2 = 3 + 2·(1-p)/p = 32/3 ≈ 3,66667


Im Folgenden soll  m  die Anzahl der Augenzahlen beim Würfeln sein, die man erzeugen möchte;  n = n(m) sei die dafür erforderliche Anzahl von Münzwürfen.

Aufgabe 3
Berechnen Sie  n  aus  m .
Setzen Sie  am = n/m . Berechnen Sie das theoretische Minimum  a  der  am .


Damit man mit  n  Münzwürfen alle  6m  möglichen Folgen von Augenzahlen erzeugen kann, muss  6m  2n  gelten. Um nicht unnötig viele Münzwürfe durchzuführen, wählt man  n  als kleinste natürliche Zahl mit  6m  2n . Somit gilt:

2n-1 < 6m  2n   ⇒   n-1 < m log2 6  n   ⇒   n = ⌈m log2 6⌉     ⌈·⌉  steht für ganzzahlige Aufrundung)

n = ⌈m log2 6⌉  bedeutet  m log2 6  n < m log2 6 + 1   ⇒   log2 6  am < log2 6 + 1/m 

Also ist  a = log2 6  2,58496 .  a  ist uns schon aus der Problemstellung (hinter Aufgabe 2) bekannt, und wie eben bewiesen wurde, ist  n = ⌈a·m⌉  a·m  (ganzzahlige Aufrundung).


Aufgabe 4
Wie viele Münzwürfe  d1  braucht man im Durchschnitt, wenn man eine Münze in Folgen der Länge  n  solange wirft, bis man eine Hexalzahl der Länge  m  erzeugt hat?


Lösung analog Aufgabe 1; (1) ist die zentrale Formel für die weiteren Rechnungen.
p  sei die Wahrscheinlichkeit für die zufällige Erzeugung einer  n-stelligen Binärzahl, die einer  m-stelligen Hexalzahl entspricht.

p = 6m/2n    ⇒    d1 = n + n·(1-p)/p


Aufgabe 5
Wie viele Münzwürfe  d2  braucht man im Durchschnitt zur Erzeugung einer Hexalzahl der Länge  m , wenn man bei den nicht brauchbaren Würfen rechtzeitig abbricht?


n1  sei die durchschnittliche Anzahl von Münzwürfen für diejenigen Binärzahlen, die nicht benötigt werden, also (in Dezimaldarstellung) von  6m  bis  2n-1 . Bei Aufgabe 2 war  n1 = 2 . Hat man  n1  berechnet, ergibt sich  d2  analog zu den Aufgaben 1, 2 und 4:

d2 = n + n1·(1-p)/p

In der Berechnung von  n1  liegt die eigentliche Herausforderung.  n1  kommt nur zum Tragen, wenn die Münzwürfe eine größere Zahl als  6m - 1  ergeben. Schreibt man beide Zahlen als Binärzahlen  u > v , so gilt diese Ungleichung genau dann, falls von links einige Ziffern übereinstimmen und in der nächsten Ziffer bei  u  eine  1 , bei  v  eine  0  steht. (Man beachte, dass dies nur funktioniert, wenn man die Binärzahl durch Münzwürfe von vorn aufbaut, also beginnend bei der höchsten Potenz.)

Das soll zunächst am Beispiel  m = 2 ( ⇒ n = 6)  verdeutlicht werden. In der folgenden Tabelle stehen links die Binär- und rechts die Hexalzahlen:

000000  00
000001  01
000010  02
000011  03
000100  04
000101  05
000110  10
000111  11
001000  12
001001  13
001010  14
001011  15
001100  20
001101  21
001110  22
001111  23
010000  24
010001  25
010010  30
010011  31
010100  32
010101  33
010110  34
010111  35
011000  40
011001  41
011010  42
011011  43
011100  44
011101  45
011110  50
011111  51
100000  52
100001  53
100010  54
100011  55  v
100100  Abbruch an 4. Stelle   hier fangen die u an
100101  Abbruch an 4. Stelle
100110  Abbruch an 4. Stelle
100111  Abbruch an 4. Stelle
101000  Abbruch an 3. Stelle
101001  Abbruch an 3. Stelle
101010  Abbruch an 3. Stelle
101011  Abbruch an 3. Stelle
101100  Abbruch an 3. Stelle
101101  Abbruch an 3. Stelle
101110  Abbruch an 3. Stelle
101111  Abbruch an 3. Stelle
110000  Abbruch an 2. Stelle
110001  Abbruch an 2. Stelle
110010  Abbruch an 2. Stelle
110011  Abbruch an 2. Stelle
110100  Abbruch an 2. Stelle
110101  Abbruch an 2. Stelle
110110  Abbruch an 2. Stelle
110111  Abbruch an 2. Stelle
111000  Abbruch an 2. Stelle
111001  Abbruch an 2. Stelle
111010  Abbruch an 2. Stelle
111011  Abbruch an 2. Stelle
111100  Abbruch an 2. Stelle
111101  Abbruch an 2. Stelle
111110  Abbruch an 2. Stelle
111111  Abbruch an 2. Stelle


28  der Binärzahlen führen auf einen Abbruch, davon  4  an der  4. Stelle,  8  an der  3. Stelle und  16  an der  2. Stelle. Damit können wir  n1  berechnen:

n1 = (4·4 + 3·8 + 2·16)/28 = 18/7 ≈ 2,57143

Für die "erfolgreichen" Folgen von Münzwürfen benötigt man also  n = 6  Würfe, für die "nicht-erfolgreichen" im Schnitt lediglich ca.  2,57  Würfe.

Hier ist dann wegen  p = 36/64 :
d2
 = 6 + (18/7)·(7/9) = 8 

Das kann man nun verallgemeinern. Wir bezeichnen die  k-te Stelle (von vorn) von  v  mit  vk . Ist  vk = 0 , so gibt es unter den  2n - 6m  Binärzahlen  u , die größer als  v  sind, genau  2n-k , die an den ersten  k-1  Stellen mit  v  übereinstimmen und an der  k-ten Stelle gleich  1  sind  -  diese Binärzahlen  u  stehen für einen Abbruch nach  k  Münzwürfen. Damit erhalten wir:

(2)   n1 = (Σvk=0 k·2n-k)/(2n-6m) = (Σvk=0 k/2k)/(1-6m/2n) = (Σvk=0 k/2k)/(1-p)


Aufgabe 6
Legende zur Tabelle:
m  Anzahl Würfe mit Würfel
n  Anzahl Würfe mit Münze
p  Anteil der brauchbaren binären Zufallszahlen
d1  durchschnittliche Anzahl insgesamt benötigter Münzwürfe bei nicht-abbrechendem Verfahren
v1  Verhältnis der durchschnittlichen Anzahl benötigter Münzwürfe für einzelne Augenzahlen zum theoretischen Minimum bei nicht-abbrechendem Verfahren
d2  durchschnittliche Anzahl insgesamt benötigter Münzwürfe bei abbrechendem Verfahren
v2  Verhältnis der durchschnittlichen Anzahl benötigter Münzwürfe für einzelne Augenzahlen zum theoretischen Minimum bei abbrechendem Verfahren

Die Tabelle wird der Übersichtlichkeit halber nur in Auszügen dargestellt.

 m    n    p     d1     v1       d2     v2
 1    3  .750    4.00  1.547    3.67  1.418
 2    6  .563   10.67  2.063    8.00  1.547
 3    8  .844    9.48  1.223    8.63  1.113
 4   11  .633   17.38  1.681   12.67  1.225
 5   13  .949   13.70  1.060   13.30  1.029
 6   16  .712   22.47  1.449   17.00  1.096
··
11   29  .676   42.91  1.509   30.24  1.063
12   32  .507   63.14  2.035   34.84  1.123
13   34  .760   44.72  1.331   35.21  1.048
··
40  104  .659  157.80  1.526  105.43  1.020
41  106  .989  107.22  1.012  106.09  1.001
42  109  .741  147.01  1.354  109.76  1.011
··
50  130  .594  218.92  1.694  131.84  1.020


Man erkennt, dass die Wahl von  m  die Effizienz des Verfahrens erheblich beeinflusst. So ist z.B.  m = 2  besonders ungünstig, aber auch z.B.  m = 4  und  m = 12  schneiden ziemlich schlecht ab.

Interessant sind die großen Unterschiede zwischen  d1  und  d2  (bzw. zwischen  v1  und  v2 ), wenn  p  nahe  0,5  liegt. Das wird plausibel werden, wenn wir die Fälle  p  1  und  p  0,5  genauer betrachten. Wir erhalten überschlägig für große  n  (da die  n  schnell wachsen, ist das keine bedeutende Einschränkung):

p  1     ⇒   6m  2n       n  a·m     d1  d2  n   v1  v2  1      (siehe in der Tabelle z.B.  m = 41 )

p  0,5   ⇒   6m  2n-1   n - 1  a·m   d1  2·n   v1  2   d2  n + 3   v2  1      (siehe in der Tabelle z.B.  m = 12 )

Diese Näherungswerte folgen aus den Definitionen, die in den Aufgaben 3 bis 5 gegeben wurden. Nur  d2  n + 3  für  p  0,5  bedarf einer Erklärung:
p  0,5  bedeutet  v = 10000...2  mit vielen Nullen hinter der führenden 1  ( n  groß). Daraus folgt  n1  (Σk≥2 k/2k)/(1-p) = (2 - 1/2)·2 = 3  nach (2) und der Herleitung von (1).


Aufgabe 7
Bestimmen Sie mit Hilfe der Kettenbruchentwicklung, welche  m  sich besonders gut für eine effiziente Ersetzung von Hexalzahlen durch Binärzahlen eignen.

In der Tabelle zu Aufgabe 6 sind zwei Zeilen grün markiert worden, weil sie besonders effiziente Ergebnisse erzielen ( m = 5, m = 41 ). Diese Zahlen kommen als Nenner  c  in der Folge der Näherungsbrüche vor, die man mit Hilfe der Kettenbrüche ( a  b/c ) erhält:

log2 6 ≈   2/1
      ≈   3/1
      ≈   5/2
      ≈  13/5
      ≈  31/12
      ≈ 106/41
      ≈ 137/53
      ...


Die Theorie der Kettenbrüche stellt die Konvergenz der Brüche gegen  a  sicher:

(3)   |b/c - a| < c-2  (da die Folge der Nenner  c  streng monoton wächst, folgt die Konvergenz)

In der Aufgabenstellung wurde schon festgestellt, dass  m = c  und  n = b  als Kandidaten für effiziente Approximationen in Frage kommen.

Man beachte, dass der  1., 3., 5.  usw. Näherungsbruch kleiner als  log2 6  ist, der  2., 4., 6.  usw. dagegen größer. Wir werden zeigen, dass für unser Problem nur die größeren Näherungsbrüche in Frage kommen:

1. Fall   a  b/c  und  a < b/c

a = b/c - ε  mit  ε < c-2  nach (3). Aus  m = c, n = b  folgt  a·m = n - ε·m > n - 1/m ≥ n-1  ⇒  n = ⌈a·m⌉

Also erfüllt diese Wahl von  n, m  die Anforderung aus Aufgabe 3.

Wir erhalten damit zwei Folgen  mi = 1, 5, 41, ...  und  ni = 3, 13, 106, ...  mit  lim i→ ni/mi = a = log2 6  und wegen (3)  ni < a·mi + 1/mi . Daraus folgt, dass die zugehörigen  pi = 6mi/2ni  den Grenzwert  1  haben:

p = 6m/2n = 6m/6n/a = 6m-n/a   ⇒   pi > 6-1/mi → 1
   ⇒   d1/n → 1
  und  d2/n → 1

Also ist auch die Effizienz gezeigt.

2. Fall   a  b/c  und  a > b/c

Dann gilt:  a = b/c + ε  ⇒  a·m > n  ⇒  ⌈a·m⌉  n

Also erfüllen die Brüche aus der Kettenbruchentwicklung, die kleiner als  log2 6  sind, nicht die Anforderung aus Aufgabe 3. Wegen  d2  n + 3  und  v2  1  sind die zugehörigen  m  aber beim abbrechenden Verfahren durchaus geeignet (dann ist  n = b + 1 ).

Die folgenden beiden Tabellen für die beiden Fälle (aufgebaut wie in Aufgabe 6) machen die Ergebnisse deutlich. Es werden nur die  m = c  aus der Kettenbruchentwicklung aufgeführt:

  m    n    p     d1     v1       d2     v2
  1    3  .750    4.00  1.547    3.67  1.418
  5   13  .949   13.70  1.060   13.30  1.029
 41  106  .989  107.22  1.012  106.09  1.001
306  791  .999  791.81  1.001  791.01  1.00002

  m    n    p     d1     v1       d2     v2
  1    3  .750    4.00  1.547    3.67  1.418
  2    6  .563   10.67  2.063    8.00  1.547
 12   32  .507   63.14  2.035   34.84  1.123
 53  138  .501  275.42  2.010  140.97  1.029



Kategorie: Zahlen und Zahlsysteme, Berechnung von π


Publiziert 2014-06-15          Stand 2013-08-29


voriges Problem   |   Liste aller Probleme mit Lösungen   |    nächstes Problem


Manfred Börgens   |    zur Leitseite