mathpoint.ch    
 

Denksport - Zahlrätsel: Lösungshinweise

   
 
   
Zu Denksport Zahlrätsel

Zum Mathpoint-Index

 

 

 

 1. Die Lösung ist selbst-korrigierend.

 2. Vorstufe: Welche vierstellige Zahl ergibt durch 68 und durch 90 geteilt Rest 0?

 3. 45
  Wenig interessanter Lösungsweg: Alle Zahlen notieren und einzeln auswerten.
  Besser: Venn-Diagramm:

        venn

Anzahl Dreierreihenzahlen: 99 : 3 = 33
Anzahl Fünferreihenzahlen: 100:5 = 20
Anzahl Siebnerreihenzahlen: 98:7 = 14
Anzahl Fünfzehnerreihenzahlen: 6
Anzahl Einundzwanzigerreihenzahlen: 4
Anzahl Fünfunddreissigerreihenzahlen: 2
Anzahl 105er-Reihenzahlen: 0.
Mit diesen Angaben das Venndiagramm wie oben ausfüllen. Die eingefüllten Zahlen bedeuten die Anzahl der entsprechenden Zahlen von 1 bis 100.

 4. Die Lösung ist selbst-korrigierend.

 5. Vorstufe: Welche Zahl gibt jeweils Rest 0?

 6. a) 192 Ziffern, b) 2893 Ziffern, c) 10'000

 

 7. Zu den Stockwerken 0, 1, 2, ... gehören die Kartenzahlen
0, 3, 9, 18, 30, 45, 63, ... Aufschlussreicher sind jedoch die durch 3 dividierten Kartenzahlen : 0, 1, 3, 6, 10, 15, 21. Formel: n (n + 1) / 2. => Formel für die Kartenzahlen: 3n (n + 1) / 2. Für n = 47 ergibt sich 3384. Dies unter der Voraussetzung, dass auch zuunterst auf dem Tisch noch horizontale Karten liegen. Andernfalls wäre noch 47 zu subtrahieren.

kartenhaus

 

 8. Selbstkorrigierend.

 9. Selbstkorrigierend.

10. Palindrom-Zahlen
Vgl. http://www.mathematische-basteleien.de.

11. 21 Zahlen

12. 364 Tage Abstand. 364 : 7 gibt Rest 0, folglich gleicher Wochentag.

13. In jedem Jahr gibt es mindestens einen Freitag, den Dreizehnten. In gewissen Jahren kommt dies bis dreimal vor.

14. s. Hinweise bei der Aufgabenstellung.

15. s. Lösungshinweise nach der Aufgabenstellung.

 
 
 
 
  16. Wer unbedingt fertige Lösungen sehen will, findet solche unter dem angegebenen Buch-Link: Béla Bollobás: The Art of Mathematics : Buch-Bild anklicken, Inhaltsverzeichnis suchen, S. 48: Integer Sequences, (i), ferner S. 53: Triangles and Squares, sowie S. 60: Polygons and Rectangles.
Reizvoller ist jedoch die Entwicklung einer eigenen "pictouresquen" Lösung. Tipp zum Problem a) : Man arbeite mit der Eigenschaft der Parität ("gerade" / "ungerade"). Ferner kann man das berühmte Schubfachprinzip (pigeon-hole principle) verwenden: Wenn man aus {1, ... , 2n} n+1 Zahlen, also mehr als die Hälfte, auswählt, ist sicher eine gerade und sicher eine ungerade Zahl dabei...
Zum Taubenschlagprinzip siehe auch Beispiele unter diesem Link.
 

17. Pro 1 (roter) Diagonalschritt entsteht sowohl in horizontaler wie auch in vertikaler Richtung eine Verschiebung um 1 Quadrateinheit. Wo befindet man sich im angegebenen Beispiel (x = 8, y = 5) jeweils nach 5 bzw. 8 Schritten? - Man entwickle zuerst eine Formel für a(x,y)+c(x,y) und für b(x,y)+d(x,y). Daraus entstehen dann Formeln für a(x,y), b(x,y), c(x,y), d(x,y) einzeln.

Zur Angabe von auf-, bzw. abgerundeten Ganzzahlen verwende man die Terminologie von "floor" bzw. "ceiling":
floor(3.5) = 3, ceiling(3.5) = 4, floor(4) = 4, ceiling(4) = 4.

 
 
 
 
  18. a) Die Stadt Zürich hat mehr als 300'000 Einwohner (knapp 400'000). Sortiert man die knapp 400'000 Personen nach "Anzahl Haare" in "Schubladen" (0 bis 300'000 Haare), so wird klar, dass mindestens eine Schublade mehr als eine Person "enthält".
Das Spezielle an diesem Problem ist, dass wir von der Existenz mindestens zweier Personen mit gleich vielen Kopfhaaren wissen, ohne diese Personen jedoch konkret zu kennen. (Zudem gilt ein bestimmter Zustand nur für den Bruchteil einer Sekunde, da die Personen infolge Haarausfalls ja immer wieder die Schubladen wechseln.)
Wir erhalten ein Existenz-Resultat, ohne jedoch zu wissen, wie dieses Resultat konkret aussieht.
 

b) Tipp: Die 11 Zahlen seien n1, ... , n11 . Wir notieren folgende Summe:
a1n1+ ... + a11n11 . Dabei wählen wir die ai aus der Menge {0, 1}. Wir haben 211 = 2048 Möglichkeiten, eine solche Summe zu bilden. Division durch 2011 ergibt der Möglichkeit nach 2011 verschiedene Reste. Teilen wir die 2048 Kombinationen in die 2011 Rest-Schubladen ein, wird mindestens eine Schublade zwei Kombinationen mit gleichem Rest enthalten.
Seien b1n1+ ... + b11n11 und c1n1+ ... + c11n11 zwei solche Kombinationen mit gleichem Rest bei Division durch 2011. Dann hat die Differenz-Kombination
(b1-c1)n1+ ... + (b11-c11)n11 den Rest 0. (bi-ci) ist aber entweder 1, 0 oder -1. Somit ist eine Kombination wie in der Aufgabe verlangt gefunden.
Auch hier erhalten wir als Resultat nur die Gewissheit, dass eine solche Kombination existiert, ohne aber bereits zu wissen, wie sie konkret aussieht.

Das IMO-Beispiel 1972:

Eine zehnelementige Menge hat 210 = 1024 Teilmengen. Jede Teilmenge erzeugt eine Summe zwischen 10+11+...+19=145 und 90+91+...+99=945.

Wir stellen uns Schubladen mit den Nummern 145 bis 945 vor, also 800 Schubladen. Die 1024 Teilmengen versorgen wir nun je nach Summe in die richtige der 800 Schubladen. Nach dem Schubladenprinzip gibt es mindestens eine Schublade mit mehr als einer Teilmenge. Seien zwei solche Teilmengen in der gleichen Schublade, also mit gleicher Summe, mit A und B bezeichnet.

In der Regel werden A und B eine Schnittmenge haben. Wir bilden nun A \ B und B \ A, d.h. entfernen von beiden Mengen die Schnittmenge. Diese neuen Mengen haben ebenfalls gleiche Summe und sind zudem disjunkt: Die Behauptung ist bewiesen: Man findet stets zwei solche Mengen. Der Beweis ist allerdings nicht konstruktiv.

Beispiel: {10, 12, 18, 19, 20, 24, 26, 70, 90, 98}. A = {10, 12, 18, 20}, B = {10, 24, 26}, beide in der Schublade mit Summenbeschriftung 60. Wir entfernen die Schnittmenge {10}:

{12, 18, 20} und {24, 26} sind disjunkt mit je Summe 50.

 
 
 
 
 

19. Hinweis: Was haben die Brüche a/b einer Zeile gemeinsam? Dies ergibt bereits die Pyramidenzeile...

 

Eine Lösung findet sich auf dieser Seite.

 

20. a) 2(x+10)-2x = 20;    b) n2 - 1 = (n-1)(n+1), d.h. faktorisierbar für n>2
c) (n+1)(n-1) + 1 = n2 <=> n2 - 1 + 1 = n2: richtig.

d) x2 + y2 = 4k + 3. Rechte Seite ungerade => x und y haben unterschiedliche Parität. Sei x gerade und y ungerade. Dann ist x2 durch 4 teilbar. Es folgt y2 = 4k - x2 + 3. Die rechte Seite dieser Gleichung ergibt bei Division durch 4 Rest 3. Die linke Seite ergibt als Quadrat einer ungeraden Zahl bei Division durch 4 jedoch Rest 1; sei nämlich y = 2r + 1 => y2 = (2r + 1)2 = 4r2 + 4r + 1, ergibt bei Division durch 4 Rest 1.
Die Gleichung y2 = 4k - x2 + 3 kann somit nicht bestehen, da sie links und rechts unterschiedliche Viererreste gibt.

e) (x - 5)(x + 5) + 25 = x2 - 25 + 25 = x2 .

 
 
 
 
 

21. b) rekursiv: f(n) = f(n-1) + n. Man suche dafür eine anschauliche geometrische Erklärung. Was passiert beim Zeichnen einer neuen Geraden?
Es gibt auch eine Beziehung zwischen der g- und der f-Spalte:
f(n) = f(n-1) + g(n-1). Auch dafür lässt sich eine geometrische Erklärung finden.
Die rekursive Formel f(n) = f(n-1) + n stellt eine Arithmetische Folge 2. Ordnung dar. Die direkte Formel für f(n) aus n lässt sich über den Ansatz f(n) = an2 + bn + c durch Einsetzen der ersten drei Wertepaare (0 | 1), (1 | 2), (2 | 4) finden (Gleichungssystem).
Man erhält f(n) = n(n+1)/2 + 1. Gleichwertig ist: f(n) = n(n-1)/2 + n + 1. Auch diese Formel lässt sich geometrisch-anschaulich begründen.

n g(n) f(n) r(n)
0 1   1   1
1 2   2   2
2 3   4   4
3 4   7   8
4 5 11 15
5 6 16 26

c), d), e)
r(n) = r(n-1) + f(n-1): Diese rekursive Formel lässt sich ebenfalls geometrisch-anschaulich begründen. Wie könnte eine solche Begründung aussehen? *)

Die Werte der r-Spalte bilden eine arithmetische Folge 3. Ordnung, die durch einen kubischen Ansatz beschrieben werden kann: r(n) = an3+bn2+cn+d. Einsetzen der ersten 4 Wertepaare und Auflösen des entsprechenden Gleichungssystems liefert:
r(n) = (1/6)n3 + (5/6)n + 1. Auch diese Formel geometrisch zu "verstehen", ist sehr schwierig (wenngleich wohl nicht unmöglich). Eine bessere Ausgangslage bietet die Darstellung mittels Binomialkoeffizienten (s. Hinweis unten).

 

Die Zahlen der f-Spalte heissen auch "Lazy caterer's numbers": Sie stellen die maximale Anzahl Stücke eines (zweidimensional gedachten) Fladenkuchens (pancakes) dar, welche mit n Schnitten erreicht werden kann.
Die Zahlen der r-Spalte sind die "Cake numbers": Maximale Anzahl Stücke eines Cakes mit n Schnitten.

 

*) Z.B. so: Man stelle sich 4 farbige Plexiglas-Ebenen im Raum in zufälliger Lage vor. Eine fünfte Ebene in zufälliger Lage sei aus gewöhnlichem Schaufensterglas. Wir orientieren nun dieses Gebilde (oder uns selber) so, dass die Schaufensterglas-Ebene senkrecht vor uns steht. Dort, wo das Schaufenster die Plexiglasebenen durchschneidet, denken wir uns die Schnittkanten fluoreszierend-leuchtend.
Was sehen wir nun, wenn wir die Augen etwas zukneifen im Schaufenster? Wir sehen 4 Leuchtgeraden in allgemeiner Lage (in der Schaufenster-Ebene liegend). Diese bilden f(4) = 11 Felder. Indem wir die Glasscheibe eingefügt haben, sind also auf unserer Seite der Glasscheibe f(4) = 11 neue Raumabteilungen entstanden. Das heisst, wir finden: f(5) = r(4) + f(4) = 15 + 11 = 26.

schaufenster


Link zur Erklärung von Pólya selber im Buch "Mathematik und plausibles Schliessen".
Weitere Hinweise in der Online-Enzyklopädie der Zahlfolgen ,
dort auch der Hinweis auf

g(n) = (n tief 0) + (n tief 1)                                       (Natürliche Zahlen)
f(n)  = (n tief 0) + (n tief 1) + (n tief 2)                      ("lazy caterer numbers")
r(n)  = (n tief 0) + (n tief 1) + (n tief 2) + (n tief 3)     ("cake numbers").

Damit ist der Weg zur Verallgemeinerung auf höhere Dimensionen offen.
Vgl. Aufgabe 14:
1, 2, 4, 8, 16, 31, 57, 99, 163, 256, 386, ...:
Numbers of regions in 4-space formed by n-1 hyperplanes.

 
 
 
 
  Bemerkungen zu den Formeln von Problem Nr. 21  

 

 
  nr21   Die Formeln ganz links lassen keine besondere Struktur erkennen. Eine solche tritt aber glasklar in Erscheinung, sobald man diese Formeln mit Hilfe der Binomialkoeffizienten (rechte Seite) ausdrückt. Nun webt sich plötzlich ein roter Faden durch die zunächst so verschieden anmutenden Formeln. Dank der Erfindung (oder Entdeckung?) der Binomialkoeffizienten, die ja überhaupt nicht in Zusammenhang mit diesem Problem ersonnen wurden, sondern Zahlen im Pascalschen Dreieck waren, welche beim Potenzieren von Binomen auftraten, wird in diesem geometrischen Problem plötzlich eine Struktur sichtbar, die äusserst klar und verallgemeinerungsfähig ist. Die kluge Abkürzung (n tief k) für diese Binomialkoeffizienten trägt das ihrige zu einer transparenten Darstellung bei.
Dies ist charakteristisch für die Mathematik: Begriffe, die in völlig anderem Kontext eingeführt wurden, wirken plötzlich klärend in Gebieten, für die sie ursprünglich gar nicht gedacht waren. Eine klug gewählte Terminologie und Symbolik ist dabei sehr wichtig. - Ähnliches gilt wohl nicht nur in der Mathematik, sondern etwa auch in der Philosophie.
 
 
 
 
 

22.

Diophantes' Alter: 84.

ggT(851, 444) = d = ?

  • 851 - 444 = 407
  • 444 - 407 = 37
  • 407 - 11⋅37 = 0. => d = 37.

37 = 444 - 407 = 444 - (851 - 444) = 2⋅444 - 1⋅851 =>

37 = (-1)⋅851 + 2⋅444.

a) -x + 2y = 3. Partikularlösung (z.B. erraten): (1 | 2).
Homogene Lösung: -x + 2y = 0 oder x = 2y, das heisst: x-Wert = Doppeltes des y-Wertes => Homogene Lösungen sind von der Form (2t | t).
Allgemeine Lösung = Partikularlösung + Homogene Lösungen:
(1 + 2t | 2 + t).

b) Wir stellen den ggT d=37 als Linearkombination von 851 und 444 dar:
(-1)⋅851 + 2⋅444 = 37     |⋅3. Wir erweitern die Gleichung passend:
(-3)⋅851 + 6⋅444 = 111 => Partikularlösung: (-3 | 6)

Wie unterscheiden sich 2 Lösungen voneinander?
Seien

ax + by = c            und
dx + ey = c            zwei Partikularlösungen. Wir bilden die Differenz =>
------------------------
(a-d)x + (b-e)y = 0.

(a-d), (b-e) sind also die Lösungen der homogenen Gleichung (der Gleichung mit c=0). Falls wir die homogenen Lösungen haben, erhalten wir alle Lösungen durch "Partikularlösung + homogene Lösungen = allgemeine Lösungen".

Homogene Gleichung: 851x + 444y = 0. Wir kürzen diese Gleichung maximal mit dem ggT und erhalten:

23x + 12y = 0 (beide Versionen haben dieselben Lösungen)
=> 23x = -12y =>
12 ist Teiler von x und 23 ist Teiler von y (warum?)
=> x = 12t und y = 23s.
Eingesetzt: 23(12t) = -12(23s) oder gekürzt mit (23⋅12):
t = -s oder s = -t.

Wir finden als homogene Lösungen: x = 12t und y = -23t.

Allgemein: Homogene Lösungen: x = b't, y = -a't ; b' = b/d, a' = a/d.

Allgemeine Lösungen = Partikularlösung + homogene Lösungen:
(-3 + 12t | 6 - 23t).

Allgemeine Lösungsformel für ax + by = c:

x = x0 + t⋅b' und y = y0 - t⋅a'


mit b' = b/d, a' = a/d, d = ggT(a,b). x0 und y0 sind Partikularlösungen.

Siehe: Lösungsverfahren für diophantische Gleichungen ax + by = c.

IMO 1959, Nr. 1: Zeige: d = ggT von Zähler und Nenner ist 1.
d teilt (21n + 4) und (14n + 3) => d teilt die Differenz (7n + 1). d teilt auch das Doppelte davon, nämlich (14n + 2). d teilt auch die Differenz von (14n + 3) und
(14n + 2), also d teilt 1 => d = 1, der Bruch ist gekürzt.

 

23.
a)
Teilbarkeit durch 4:
2mn ist stets durch 4 teilbar (Faktor 2 und entweder m oder n ist gerade).

Teilbarkeit durch 3:
Falls m oder n durch 3 teilbar sind, sind wir fertig. Seien nun weder m noch n durch 3 teilbar, also von der Form m = 3x+1 oder m = 3x+2 und n = 3y+1 oder n = 3y+2.
Wir quadrieren:
m2 = 9x2 +6x+1 bzw. 9x2 +12x+4 und
n2 = 9y2 +6y+1 bzw. 9y2 +12y+4.
Alle möglichen Kombinationen von m2 - n2 sind durch 3 teilbar.

Teilbarkeit durch 5:
Betrachtung der Endziffern:
m oder n durch 5 teilbar: Wir sind fertig.
Weder m noch n durch 5 teilbar: Endziffern 1, 2, 3, oder 4. Die Quadrate haben dann die Endziffern 1, 4, 9 oder 6. Bei jeder Kombination ergibt entweder die Summe oder die Differenz der Quadrate eine Zahl mit Endziffer 5 oder 0, also eine durch 5 teilbare Zahl.

d) Primzahlen p als Hypotenuse: p = 4n+1, n eine natürliche Zahl ist Hypotenuse genau eines ganzzahligen Dreiecks, p = 4n+3 jedoch nie. Beweis?

24.Wiederum gilt: Das Nachschlagen einer Lösung ohne Eigenversuche ist relativ witzlos. Trotzdem für Verzweifelte:

Interaktives Applet zum Erzeugen von Gitterpolygonen
Ein möglicher Beweis (D.E.Varberg)
Satz von Pick.
Umfassende Abhandlung hier:
http://www.m-hikari.com/ Suchstichwort "Pick" eingeben -> pdf.

25. Jedes Tripel hat folgende Eigenschaften:

  • Die Vektoren haben ganzzahlige Koordinaten, d.h. als Ortsvektoren, ausgehend vom Koordinatennullpunkt, liegen ihre Spitzen auf ganzzahligen Raumgitterpunkten.
  • Die Vektoren stehen paarweise senkrecht aufeinander (man teste die paarweisen Skalarprodukte, die null ergeben), bilden also drei Kanten eines Quaders.
  • Die Vektoren haben ganzzahlige Länge, d.h. die Kantenlängen des durch sie erzeugten Quaders sind ebenfalls ganzzahlig.

Jedes Tripel erzeugt somit einen Quader mit ganzzahligen Eckkoordinaten und ganzzahligen Kantenlängen, einen -wie man sagen könnte- "diophantischen Quader".

Anleitung zum Erzeugen ganzzahliger Quader (pdf)

P.S. Eines der gezeigten Tripel stellt einen diophantischen Würfel dar. Welches?


ganzzqubild
Ein Quader mit ganzzahligen Eckkoordinaten und ganzzahligen Kantenlängen.

 
 
 
 
 

Grafische Darstellung der diophantischen Gleichung

 

851x + 444y = 111

     diophant_vgl

            |                  |                     |

allg. Lösung = partikuläre L. + homogene L.

 

Die Lösungsmenge besteht aus den Punkten mit ganzzahligen Koordinaten der Geraden y = (-23/12)x + 0.25.



Ausgehend vom Punkt (-3 | 6) trägt man den Vektor [12; -23] t-mal ab, wobei t eine ganze Zahl ist.

  diophant_grafisch  
 
 
 
 

26. Setzen Sie sich selber in die Mitte der Sechsergruppe. Um Sie herum befinden sich also noch 5 Personen. Von Ihnen aus (M) aus laufen 5 "Beziehungsgraphen" zu den übrigen Personen. Diese färben wir grün ("kennen sich bereits") oder rot ("kannten sich bisher noch nicht") ein. Nach dem Schubfachprinzip (5 Strecken in nur 2 "Farbtöpfe" tauchen) kommt eine der Farben mindestens 3-mal vor. Sei dies die grüne Farbe (ist es die rote, verläuft die Überlegung genau gleich, einfach mit vertauschten Farben). Wir haben nun die Situation von Abb. 1a. Die Personen aussen wurden dabei so angeordnet, dass die gleichfarbigen "Speichen" nebeneinander liegen.

Ist nun in der Situation von Bild 1a eine der Strecken AB oder BC ebenfalls grün (oder sind gar beide grün), sind wir fertig: Wir haben ein grünes "Cliquen-Dreieck" oder eine noch grössere Clique gefunden. Oder in Fachsprache: Wir haben einen grünen Sub-Graphen mit Ordnung ≥3 gefunden.

Sind jedoch AB und BC beide rot, liegt die Situation von Bild 1b vor. Nun ist die Frage, wie die Strecke AC gefärbt ist. Ist AC grün gefärbt, haben wir mit AMC eine grüne Dreierclique gefunden, ist AC jedoch rot gefärbt, stellt ACB eine rote Dreierclique dar.

In jedem Fall finden wir also bei 6 Personen eine grüne oder eine rote Dreierclique.

6 ist die minimale Anzahl geladener Gäste für die Existenz solcher Dreiercliquen, d.h. zu m = 3 gehört die Ramseyzahl R(m) = 6. Beachten Sie, dass unser Beweis die Minimalität der Zahl 6 nicht einschliesst. Es ist aber leicht zu zeigen, dass man mit Zahlen < 6 immer eine Situation konstruieren kann, in der es keine Cliquen von Ordnung 3 oder höher gibt.

Für die Existenz von Vierercliquen (m=4) bräuchte es bereits mindestens 18 geladene Gäste. Für höhere m gibt es bisher keine sicheren Zahlen, nur die Gewissheit, dass es eine solche minimale Zahl gibt.

 

ramsey

 

http://en.wikipedia.org/wiki/Ramsey%27s_theorem

s. auch in der Online-Enzyklopädie der Zahlfolgen A120414

 
 
 
 
 

27. Betrachten r = √2√2 . Ist r irrational oder rational?

Fall a) r ist rational: Wir sind fertig: Mit r = √2√2 ist eine Zahl wie verlangt gefunden.

Fall b) r ist irrational. Dann wählen wir x = r = √2√2 und y = √2. Wir bilden
xy = (√2√2)√2 = √22 = 2 (= rational). Nun ist dies eine Zahl wie verlangt.

 

Quelle: Proof and Other Dilemmas, MAA, Spektrum, Bonnie Gold, Roger A.Simons

 

Wann ist ein Problem gelöst?

Man wundert sich hier vielleicht: Wir wissen nicht, ob Variante a) oder Variante b) zutrifft, erhalten aber auf jeden Fall ein positives Ergebnis, haben also unser Problem zwar positiv gelöst, können jedoch keine konkrete Lösung angeben. (Das erinnert ein wenig ans bluffende kleine Kind, das sagt: "Ich weiss es, aber ich sage es nicht!").

Hier klaffen mathematische Existenz und konstruktiv-konkrete Existenz auseinander.

Ähnliches haben wir bestimmt schon mehrfach angetroffen. Niemand kennt alle Dezimalziffern von √2, obwohl sie "im Prinzip" eindeutig definiert sind. ("Im Prinzip" erinnert ein wenig an die alten Radio Eriwan-Witze...)

 
 
 
 
  28. Tabelle:
n 1 2 3 4   5   6
a(n) 1 1 2 6 18 65
 

siehe Online-Enzyklopädie der Zahlfolgen: A108066

Das rote Dreieck ist nicht rechtwinklig.

 
 
 
 
  29. 7 oder 7-3 . Herleitung?   30. Welches ist die nächstmögliche Spiegelzahl?  
 
 
 
 

31.

a) Sei x die erste Zahl, y die zweite Zahl. Bsp: x = 111111, y = 222. Sei n die Anzahl Ziffern von y.

Es ist x = 100 + 101 + ... + 102n-1 = (102n - 1) / 9.

Ferner ist y = 2(100 + 101 + ... + 10n-1) = 2(10n - 1) / 9.

Dann ist x - y = (102n - 2⋅10n + 1) / 9 = [(10n - 1) / 3]2.

Bsp: Für n = 3 ergibt sich x - y = 3332.

 

b) Je ein Faktor 5 und ein Faktor 2 kombiniert ergeben einen Faktor 10, d.h. eine Null hinten. Faktoren 2 gibt es im Überfluss. Die Frage bleibt: Wie viele Faktoren 5 hat 100! ?
25; 50; 75 und 100 haben je 2 Faktoren 5.
5; 10; 15; 20; 30; 35; 40; 45; 55; 60; 65; 70; 80; 85; 90 und 95 haben je einen Faktor 5.
Total: 24 Faktoren 5; diese kombiniert mit je einem Faktor 2 ergeben 24 Faktoren 10, d.h. 100! endet mit 24 Nullen.

c) Der Zehnerlogarithmus der Zahl ist gleich 99⋅lg(9) = 369'693'099.6, somit hat die Zahl 369'693'100 Ziffern. Das ergäbe bei 10 Ziffern pro 1.5 cm einen Streifen von ca. 555 km Länge.
Da ist 9hoch doch eine kürzere Schreibweise.

d) Endziffer 9. Mögliche Begründung:
Der Exponent ist ungerade. Eine Zahl (10x + 9)ungerade Zahl hat Endziffer 9, da als Einerziffer nur 9ungerade Zahl bleibt, und alle ungeraden Neunerpotenzen haben Endziffer 9.

 
 
 
 
  32. 18 Jahre. Herleitung?      
 
 
 
 

33. Seien 0 der linke Punkt des Stabes, x1 und x2 die Bruchstellen (nicht unbedingt der Grösse nach geordnet) und 1 der Endpunkt des Stabes.

Damit ein Dreieck möglich ist, müssen alle Dreiecksseiten < 1/2 sein. Wir tragen die Bruchstelle x1 auf der horizontalen Achse (von 0 bis 1) und x2 auf der vertikalen Achse (zwischen 0 und 1) ab.
Genau dann, wenn das Bruchstellenpaar (x1 | x2) im grünen Bereich liegt, sind alle Dreiecksseiten < 1/2. Der grüne Bereich ist 1/4 des ganzen Einheitsquadrats.

ksbruchstellen

Wir erhalten somit für die gesuchte Wahrscheinlichkeit, dass ein Dreieck gebildet werden kann, den Wert 1/4.

Quelle der Aufgabenstellung: Béla Bollobás: The Art of Mathematics, Coffee Time in Memphis, Cambridge, 2006.

Eine mögliche Lösung für die rechts formulierte Anschlussaufgabe findet sich hier (als pdf).

 

Eine andere Herleitung für n = 2:

bary1     bary2

Wir betrachten das gleichseitige Dreieck mit Seitenlänge 1. Für jeden Punkt im Innern dieses Dreiecks gilt - geometrisch sofort ersichtlich -
u + v + w = 1.
Wir fassen u, v und w als die drei Bruchstücke unserer zerbrochenenen Einheitsstrecke auf (die Gesamtlänge ist immer 1): Jede Lage von P erzeugt ein Zerbrechen des Einheitsstabes in 3 Bruchstücke mit Summe 1. Die Bedingung, dass alle Bruchstücke <1/2 sein müssen, wird durch die Lagen von P innerhalb des grauen kleinen Dreiecks im Bild rechts angegeben. Dessen Fläche ist 1/4 der Gesamtfläche des grossen Dreiecks. Damit haben wir erneut p = 1/4 gefunden.

Die in der angegebenen Quelle hergeleitete Formel für beliebige n lautet:

p("konvexes Polygon möglich") = 1 -  (n + 1)/2n .

Für n = 2 (Dreieck) ergibt sich unser Wert 1/4, für n = 3 (Viereck) der Wert 1/2.

Anschlussaufgabe: Man suche eine Herleitung, die leichter auf beliebige n zu verallgemeinern ist, als unsere speziell auf n = 2 zugeschnittene geometrische Herleitung.

 
 
 
 
 

34. Sei n = Anzahl Schülerinnen und Schüler, a = Anzahl Personen des einen Geschlechts,
b = n - a = Anzahl Personen des andern Geschlechts. Sei a > b.

Lösungsweg 1: Baum zeichnen (s. Spalte rechts)

Lösungsweg 2:
Anzahl günstige Paare (gemischt): ab = a(n - a)
Anzahl mögliche Paare: n (n - 1) / 2.
=> a(n - a) : [n(n - 1)/2] = 1/2 =>

4a2 - 4an + n2 - n = 0.
Wir lösen diese quadratische Gleichung nach a auf und finden (a ist der grössere Anteil; wir wählen also die grössere der beiden Lösungen - die andere ist b):

a = (n + √n) / 2 und b = (n - √n) / 2.

Da a und b ganzzahlig sein müssen, muss n eine Quadratzahl sein. Die ersten Lösungen sehen so aus:

n 0 1 4 9 16 25 36 ...
a 0 1 3 6 10 15 21 ... Dreieckszahlen
b 0 0 1 3 6 10 15 ... Dreieckszahlen (1 Stufe verschoben)

Wir finden:
a und b sind aufeinanderfolgende Dreieckszahlen und n = a + b.

 

baum

Baum zu Lösungsweg 1: Die Pfadregeln führen auf dieselbe quadratische Gleichung wie Lösungsweg 2.

 

Aufgabe (leicht modifiziert) aus Dierk Schleicher, Malte Lackmann: Eine Einladung in die Mathematik, Springer Spektrum, Heidelberg 2013.

 
 
 
 
 

35.

imo86

Versuch 1: Eine naheliegende Idee wäre, als Funktion s = |a|+|b|+|c| zu betrachten. Wie man rasch feststellt, gibt es jedoch Fälle, in denen diese Funktion von Schritt zu Schritt nicht abnimmt.

Wie sähe diese Funktion nach einem Schritt aus? Es ergäbe sich:
|a+b|+|b|+|b+c|.
Es treten somit neue Terme auf, nämlich Summen benachbarter Zahlen. Man kann nun versuchsweise solche Summen benachbarter Zahlen in die gesuchte Funktion einbauen:

Versuch 2: s = |a|+|b|+|c|+|a+b|+|b+c|+|c+a|. Diese Funktion ist symmetrisch (invariant) in Bezug auf zyklische Vertauschung von a, b und c (das muss sie auch sein). Wie sieht nun die Funktion nach einem Schritt aus? Es ergibt sich:
|a+b|+|b|+|b+c|+|a|+|c|+|a+2b+c|. Die Funktion wird langsam "selbstgenügsam"; viel wesentlich Neues kommt in einem Iterationsschritt nicht mehr dazu.

 

Es ist nun tatsächlich

|a|+|b|+|c|+|a+b|+|b+c|+|c+a| > |a+b|+|b|+|b+c|+|a|+|c|+|a+2b+c|

oder gleichbedeutend

|a+c| >
|a+2b+c|,

denn (a+c) ist positiv (weil b negativ ist, a+b+c jedoch positiv sein muss); daraus folgt obige Behauptung.

 

Die gesuchte Funktion lautet somit:

s = |a| + |b| + |c| + |a+b| + |b+c| + |c+a|.

Diese Funktion nimmt von Schritt zu Schritt echt ab, und folglich endet das Verfahren einmal. (Es sind noch andere Funktionen möglich, die denselben Zweck erfüllen.)

Nun kann eine Verallgemeinerung auf Vier- und Fünfecke vermutet werden...

 
 
 
 
 

Bemerkung zum Lösen mathematischer Probleme
In obigem Lösungsansatz kommen folgende Arbeitstechniken zum Zug:

  • "Verkleinern" des Problems. Anstelle eines Fünfecks wird lediglich ein Dreieck betrachtet.
  • Suchen einer Funktion, welche jeder Konfiguaration eine natürliche "Kennzahl" zuordnet. Das Betrachten dieser Kennzahl ist einfacher als das Betrachten der Zahlkonfigurationen. Eine Lösung gelingt allein durch Kenntnis solcher Kennzahlen. Man projiziert das ursprüngliche Problem mittels einer Funktion in die einfache Struktur der natürlichen Zahlen.
  • Symmetriebetrachtungen: Die Funktion, die jeder Konfiguration eine natürliche Zahl zuordnet, muss unter zyklischer Vertauschung von a, b, c unverändert bleiben, denn anstelle von b könnten auch c oder a negative Zahlen sein.
 

Es darf bezweifelt werden, ob ein noch so hoch entwickelter Supercomputer je in der Lage sein wird, beispielsweise solche Hilfsfunktionen oder andere nützliche Lösungswerkzeuge zu suchen. Dazu ist eine ganze Erfahrungs-Biografie nötig. Oft entstehen kreative und neue Lösungen durch Erfahrungen, die man in ganz verschiedenen Gebieten der Mathematik gesammelt hat. In loser Assoziation tauchen mögliche Werkzeug-Ideen auf, die man früher einmal erfolgreich angewendet hat. Es gibt in diesem Stadium noch keine formale Begründung für die Wahl und das Ausprobieren eines solchen Werkzeugs. Falls das Werkzeug erfolgreich ist, entsteht die formale Begründung hinterher. Es gab keine vorprogrammierte Intuition, vielmehr findet ein bildhaftes, suchendes Herumkramen in der eigenen Biografie bisheriger Problemlösungen statt. Oft braucht es -wie der Mathematiker Henri Poincaré es beschreibt- dazu auch noch ein paar Tassen starken Kaffee und den überreizten Zustand einer durchgearbeiteten Nacht...

 
 
 
 
 

36.

  Wir betrachten den Zahlenstrahl, wenden jedoch einen Trick an: Wir schliessen das Stück [0 ; 1] des        
  Zahlenstrahls zu einem Kreis mit Umfang 1.

  Nun starten wir bei 0 und tragen im Gegenuhrzeigersinn laufend log(7) ab. Jedes Mal, wenn wir beim
  roten Punkt (s. Abb.) vorbeikommen, zählt uns ein "Zähler" eine Runde dazu.

1976_3

 

Da lg(7) irrational ist, entstehen beim fortwährenden Addieren von lg(7) stets neue Punkte. Es "regnet" also fortwährend neue Punkte in die Kreislinie hinein. Dieser Punktregen wird immer dichter.

Zu zeigen wäre noch, dass der Punktregen sich "gut" über die Kreislinie verteilt, dass insbesondere keine Dauerlücke um den roten Punkt herum offen bleibt. Wie liesse sich dies plausibel erklären? *)

Unter dieser Voraussetzung wird nun der Punktregen um den roten Punkt herum beliebig dicht und man findet einen Punkt n⋅lg(7), der ein beliebig kurzes Kreisbogenstück oberhalb des roten Punktes liegt.

Damit ist gezeigt, dass es zu jedem noch so hohen m ∈ ℕ Siebnerpotenzen mit mindestens m aufeinander folgenden Nullen in der Dezimaldarstellung gibt.

Allerdings ist damit noch nicht gezeigt, dass es zu jedem m Siebnerpotenzen mit genau m aufeinander folgenden Nullen in der Dezimaldarstellung gibt.
Man kann jedoch aus einer Siebnerpotenz der Dezimalform 1 0...0 ∗∗∗ durch Multiplikation mit 7 oder mit 72 eine neue Siebnerpotenz mit weniger Nullen in Folge erzeugen, z.B. aus
7510 = 1.0000009...⋅10431 (6 Nullen in Folge) die Zahl
7511 = 7.000006... ⋅10431  (5 Nullen in Folge) und mittels erneuter Multiplikation mit 7 die Zahl
7512 = 4.900004... 10432   (4 Nullen in Folge).

Bemerkung: Wann ist ein Problem gelöst? Unser Beweis ist ein reiner Existenzbeweis. Er gibt keine konkrete Zahl an. Wir haben eine wichtige Arbeitstechnik verwendet: Anstelle des unendlichen Zahlenstrahls betrachteten wir eine geschlossene Kreislinie. Dadurch verlief sich der "Punkte-Regen" nicht ins Unendliche, sondern wurde auf der begrenzten Kreislinie immer dichter.

Gibt es "konkretere" Lösungen dieses Problems?

*) 6⋅log(7) überschreitet den roten Punkt um ca. 0.07... Solche "Sechserschritte" rastern somit den Kreis bereits recht eng. Der Punkt nach 15 solcher Sechserschritte, also 90⋅log(7) überschreitet den roten Punkt um 0.05...< 0.07... Diese Neunzigerschritte erzeugen somit einen noch engeren Raster und lassen schliesslich einen Punkt entstehen, dessen Abstand zum roten Punkt noch kleiner wird als 0.05..., z.B. 17⋅90⋅log(7) = 1530⋅log(7). Dieser Punkt überschreitet den roten Punkt um nur noch 0.000001... . Auf diese Weise entstehen immer dichtere Raster und Punkte, die vom roten Punkt beliebig kleinen Abstand haben.
Das Beispiel unten zeigt, dass jedoch bereits 510⋅log(7) einen sehr, sehr eng am roten Punkt anliegenden Punkt liefert: Sein Abstand beträgt noch 0.0000004....
Gibt es ev. einen Algorithmus, der systematischer vorgeht als der hier skizzierte Gedankengang?

 
 
 
 
 

Obiger Beweis ist sehr unkonkret.

Das Durchprobieren von n⋅ lg(7) mittels eines Computerprogramms zeigt:
510⋅ lg(7) = 431.0000004... .
W ir betrachten somit 7510. Rechts das Resultat mit seinen 432 Ziffern. Man sieht, dass 6 Ziffern 0 in Folge auftreten.

Man braucht unheimlich riesige Potenzen, um die Punktdichte auch nur wenig anwachsen zu lassen. So ist z.B.
1'878'356'265⋅lg(7) = 1'587'395'198.0000000073...
Die riesige Zahl 71'878'356'265 ergäbe also eine Zahl, die 7 Nullen in Folge enthielte
(100.0000000073...≈ 1.000000017...).

Der oben geführte Existenzbeweis kommt also ziemlich nonchalant daher. Er kümmert sich überhaupt nicht um praktisch-algorithmische Schwierigkeiten. Hier, im Bereich der Numerik und der Algorithmen, würde es dann erst richtig knifflig.

  7hoch510  
 
 
 
  Bemerkung:
In obiger Aufgabe zeigen sich auch die Grenzen der intuitionistischen oder konstruktivistischen Mathematik, welche nur Beweise zulässt, die konstruierbar sind. Das Vorgehen oben ist ja eine Konstruktionsanleitung für die Herstellung der geforderten Siebnerpotenzen. Trotzdem wird für hohe Werte von m jeder auch noch so leistungsfähige Rechner versagen, da unglaublich hohe Zahlen entstehen. Selbst wenn es dereinst immer noch bessere Rechner geben wird, kommen diese bei noch höheren m-Werten erneut an ihre Grenzen.
  Der mathematische Konstruktivsmus versagt also bereits bei konstruktiven Beweisen, die sehr hohe Zahlen benötigen. Er muss sich hier ebenfalls auf eine "Konstruktion im Prinzip" stützen, die real nicht durchführbar ist. Eine solche Konstruktion ist somit nicht viel konkreter als eine via indirekten Beweis geführte Existenzaussage, die gar keine Konstruktion angibt, sondern nur eine Existenz beweist (vgl. Problem Nr. 27).  
 
 
 
  37.      
 

Sei x(k) die Anzahl Möglichkeiten, k Treppenstufen mittels der erlaubten Stufenschritte (hier zunächst 1- oder 2-Stufenschritte) zu ersteigen.

 

8 Treppenstufen in 1- oder 2-Stufenschritten ersteigen:

Sei x(8) die Anzahl Möglichkeiten dafür.

Wir können 2 Fälle unterscheiden:

-Fall 1: Der letzte Schritt ist ein Einerschritt. Das führt zu gleich vielen Möglichkeiten wie x(7).

-Fall 2: Der letzte Schritt ist ein Zweierschritt. Das führt zu gleich vielen Möglichkeiten wie x(6).

Es ist also x(8) = x(6) + x(7).

Wir können also das Problem stufenseise aufbauen:

x(1): Treppe mit 1 Stufe: 1 Möglichkeit; x(1) = 1

x(2): Treppe mit 2 Stufen: 2 Möglichkeiten; x(2) = 2

x(3) = x(1) + x(2) = 1 + 2 = 3

x(4) = x(2) + x(3) = 2 + 3 = 5

usw.

Es entsteht die bekannte Fibonacci-Folge:

1   2   3   5   8   13   21   34    55

Mit 8 Stufen ergeben sich somit 34 Möglichkeiten, diese mit Einer- oder Zweierschritten zu ersteigen.

 

8 Treppenstufen in 1- oder 2- oder 3-Stufenschritten ersteigen:

Die Verallgemeinerung auf 1- oder 2- oder 3-Stufenschritte liegt auf der Hand: Um das neue Glied der Zahlfolge zu erhalten, müssen wir die drei Vorgängerglieder addieren:

x(1) = 1

x(2) = 2

x(3) = 4

x(4) = 1 + 2 + 4 = 7

x(5) = 2 + 4 + 7 = 13, usw.

Es entsteht die Folge der Tribonacci-Zahlen(vgl. Online Encyclopedia of integer sequences)

1    2    4    7    13    24    44    81    ...

Es gibt also 81 Möglichkeiten, 8 Stufen in Einer- oder Zweier- oder Dreierschritten zu bewältigen.

Anzahl Möglichkeiten, wenn 1- bis 7-Stufenschritte erlaubt sind?

1    2    4    8    16    32    64    127    253    ... (Heptanacci-Zahlen).

Folgefrage:

Besteht der Anfang der Folge immer aus Zweierpotenzen? Die Antwort ist ja (siehe Problem 38).

Anzahl Möglichkeiten, wenn 1- bis k-Stufenschritte erlaubt sind?

Es entsteht die Folge der "k-bonacci-Zahlen". Die Folge kann so aufgebaut werden:

-Zuerst setzt man k Nullen, anschliessend eine 1.

-Des Weiteren ergibt sich das nächste Glied immer aus der Summe der k Vorgängerglieder.

Beispiel k = 7:

0    0    0    0    0    0    0    1    1    2    4    8    16    32    64    127    253    ...

Man sieht, dass anfänglich die Zweierpotenzen entstehen: 1    2    4    8    ...    64.

 
 
 
 
 

38. Summenzerlegungen einer natürlichen Zahl

     
 

- Auf wie viele Arten kann ich eine 7-stufige Treppe in 1-, 2-, ..., oder 7-Stufenschritten ersteigen? Allgemein: eine m-stufige Treppe in Schritten der Weite 1 oder 2 oder ... oder m?

- Auf wie viele Arten kann ich zwischen m Spielsteine Trennstäbe einbauen (max. 1 Trennstab zwischen zwei benachbarte Steine)?

- Auf wie viele Arten kann ich die natürliche Zahl m in Summanden zerlegen?

Beispiel: 5 = 1 + 1 + 1 + 1 + 1 = 1 + 1 + 3 = 1 + 3 + 1 = ...

 

Alle 3 Probleme sind gleichwertig, d.h. haben dieselbe Lösung.

Am einfachsten ist wohl das Legen von Trennstäben:

m Steine haben m - 1 Lücken. Bei jeder Lücke habe ich 2 Möglichkeiten: Trennstab legen oder Trennstab nicht legen.

Das ergibt total 2m -1 Möglichkeiten.

So kann ich die Zahl 5 auf 24 = 16 Arten in Summanden zerlegen.

 

treppe

Ersteigen einer 8-stufigen Treppe in lauter Einer- oder Zweierschriten

 
 
 
 
  38a. Anzahl Partitionen einer natürlichen Zahl      
 

4
3+1
2+2
2+1+1
1+3
1+2+1
1+1+2
1+1+1+1

Die gleichfarbigen Varianten werden identifiziert. Es verbleiben 5 Partitionen der 4.

 

Zur Zahl 9 existieren 30 Partitionen.

Artikel dazu hier.

 
 
 
 
  39. Eine vereinfachte Aufgabe aus dem IMO-Skript Zahlentheorie      
 

x3 - y3 = 91. Wir setzen: x - y =: d.      Somit ist x = y + d   und

x3 - y3 = (y + d )3 - y3 = y3 + 3y2d + 3yd2 + d3 - y3 =

3y2d + 3yd2 + d3 = d(3y2 + 3yd + d2) = 7 * 13 = 13 * 7 = 1 * 91 = 91 * 1

Wegen y > 0 muss d < 4 sein, sonst würde 3y2d + 3yd2 + d3 > 91. Von obigen Zerlegung bleibt also einzig 1 * 91, d.h. d = 1 und 3y2 + 3yd + d2 = 91, d.h.
3y2 + 3y + 1 = 91 oder 3y2 + 3y - 90 = 0 und somit y = 5 und x = 6.

Somit lautet die einzige Lösung mit natürlichen Zahlen (6 / 5) oder 63 - 53 = 91.

 

Alternativlösung:

x3 - y3 = (x - y)(x2 + xy + y2) = 91

Es ist sicher x ≤ 7, denn 73 - 63 = 127 > 91. Dann ist x - y ≤ 6.

Dann bleibt für (x - y) als Teiler von 91 nur 1, d.h. x - y = 1 oder y = x - 1

Es folgt: x2 + xy + y2 = x2 + x(x - 1)+ (x - 1)2 = 3x2 - 3x + 1 = 91

oder 3x2 - 3x - 90 = 0 => x = 6 => y = 5

 

 
 
 
 
  40. Fibonacci, Tribonacci, Tetranacci, ...      
  Fibonacci-Folge:
x(n+2) = x(n) + x(n+1). Sei x der Grenzwert der Quotientenfolge
x(n+1) / x(n). Je grösser n ist, desto besser nähert sich dieser Quotient dem Grenzwert x an. Sehr, sehr weit hinten in der Fibonacci-Folge gilt also näherungsweise:
x(n+1) = x * x(n) und x(n+2) = x2 * x(n), somit
x(n+2) = x(n) + x(n+1) oder x2 * x(n) = x(n) + x * x(n). Division durch x(n) ergibt
x2 = 1 + x oder x2 - x - 1 = 0. x = (√5 + 1) / 2.
 

Die Verallgemeinerung liegt auf der Hand:

Tribonacci-Folge:
Die Quotientenfolge konvergiert gegen die Lösung der Gleichung
x3 - x2 - x - 1 = 0, d.h. gegen x = 1.839286755...

 
 
 
 
  41. Ein Quadrat in kleinere Quadrate unterteilen      
 

quadrat2

Das kleinste Quadrat hat Seitenlänge 2. Quadrat: 112 x 112.

 

Zusatz:

Im Quadrat liegt das kleinste Quadrat sicher nicht am Rand des grossen Quadrates (warum?).

Nehmen wir an, wir hätten eine Würfelunterteilung in lauter verschiedene, kleinere Würfel. Auf der Bodenfläche des grossen Würfels entsteht dadurch eine Quadratunterteilung in lauter verschiedene kleinere Quadrate. Das kleinste dieser Quadrate befindet sich im Innern und nicht am Rand. Der Würfel W über diesem Quadrat steht somit im Inneren des grossen Würfels auf einem inneren Quadrat und ist von grösseren Würfeln umgeben.

detail

Auf der oberen Fläche von W befinden sich somit noch kleinere Würfel als W. Wir betrachten nun wieder den kleinsten Würfel, der sich auf der oberen Fläche von W im Inneren dieser oberen Fläche befindet... Der Prozess setzt sich ins Unendliche fort; es entstehen immer kleinere Würfel ohne Ende. Eine endliche Unterteilung ist nicht möglich.

Anmerkung: Was ist Mathematik? - Mathematik enthält auch solche "pittoreske" Beweise jenseits langfädiger formaler Schlussketten. Elegante Überlegungen und "schöne" Beweisfiguren sind genau so Teil der mathematischen Kultur wie formale Ableitungen.

 
 
 
 
 

Lösung Rechteck, unterteilt in 9 verschiedene Quadrate:

33x34

Format: 33 x 32.

 

33x34

Wir wählen die Seitenlänge des kleinen weissen Quadrates = 1. Sollten sich in der Folge nicht-ganzzahlige Seitenlängen ergeben, multiplizieren wir alle Seitenlängen mit einem geeigneten gemeinsamen Faktor. Das schwarze Quadrat habe Seitenlänge x. Nun lassen sich alle übrigen Quadratseiten durch x ausdrücken (Bild oben).

Es muss nun sein: x + 26 = 3x + 12 (Länge obere Seite = Länge untere Seite). => x = 7 und alle Quadratseiten sind damit bereits ganzzahlig.

 
 
 
 
  42. Zwei Zahlrätsel      
 

Rätsel 1

Beispiel: 33 = 3 + 4 + 5 + 6 + 7 + 8 = s(8) - s(2).

Dabei sei s(i) die Summe der natürlichen Zahlen von 1 bis i.

s(i) = i (i +1) /2.

Zahlen, die als fortlaufende Summe natürlicher Zahlen dargestellt werden können, haben somit die Form n = s(j) - s(i), j > i.

=> 2n = j (j+ 1) - i (i + 1) = j2- i2 + j - i

= (j + i)(j - i) + (j - i) = (j - i)(j + i + 1) = 2n.

Die Differenz der beiden Faktoren links beträgt 2i + 1, ist also ungerade, d.h. die beiden Faktoren haben verschiedene Parität, d.h. einer der Faktoren ist sicher ungerade. Das bedeutet, dass n sicher einen ungeraden Faktor enthalten muss.

Die Zahlen, die nicht als fortlaufende Summe natürlicher Zahlen dargestellt werden können (mit Ausnahme der trivialen Darstellung n = n), dürfen somit keinen ungeraden Faktor enthalten, sind also Zweierpotenzen.

Umgekehrt:

Sobald eine Zahl n einen ungeraden Faktor u enthält, lässt sie sich als fortlaufende Summe natürlicher Zahlen schreiben. Konstruktionsanleitung:

Beispiel: 45 = 3*15.         15 = 7 + 8. An diesen Kern setzen wir links und rechts je 3-mal ganze Zahlen an (gleichfarbige Zahlen ergeben Summe 15):

45 = 3 * 15 = 5 + 6 + (7 + 8) + 9 + 10.

Dieses Vorgehen ist allgemein möglich, sobald ein ungerader Teiler vorhanden ist. Somit sind es genau die Zweierpotenzen, die eine solche Darstellung nicht zulassen (mit Ausnahme der trivialen Darstellung n = n).

Weitere Möglichkeit der Zerlegung von 45:     45 = 5*9.         9 = 4 + 5.

45 = 0 + 1 + 2 + 3 + (4 + 5) + 6 + 7 + 8 + 9 = 1 + 2 + 3 + (4 + 5) + 6 + 7 + 8 + 9

Noch eine Möglichkeit:

45 = 9*5.         5 = 2 + 3

45 = (-6) + (-5) + (-4) + (-3) + (-2) + (-1) + 0 + 1 + (2 + 3) + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11

= 7 + 8 + 9 + 10 + 11.

Die Negativ-Anteile in der Konstruktion (rot) werden am Schluss noch eliminiert, um eine Darstellung mit natürlichen Zahlen zu erhalten.

Jeder ungerade Teiler kann in dieser Konstruktion als "Mittelkern" dienen; es gibt genau so viele Darstellungen von n in fortlaufende natürliche Zahlen, wie es verschiedene ungerade Teiler von n gibt. Nehmen wir den Teiler n hinzu, entsteht auch die triviale Darstellung n = n. Wollen wir diese nicht berücksichtigen, lassen wir den Teiler n weg.

Im Beispiel: Teiler von 45:       1, 3, 5, 9, 15, (45).     Dies liefert 5 nicht-triviale Darstellungen (negative Anteile eliminiert) und die triviale Darstellung n = n:

45 = 22 + 23;      45 = 14 + 15 + 16;           45 = 7 + 8 + 9 + 10 + 11

45 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9;        45 = 5 + 6 + 7 + 8 + 9 + 10;      (45 = 45)

 

Rätsel 2

 

 

 

 

 

 

Das kgV der Teiler von n (ohne n selber) ist gleich n, wenn es eine nicht-triviale Zerlegung n = ab gibt mit ggT(a, b) = 1. Dann ist kgV(a, b) = n, denn es gilt

kgV(a, b) = ab / ggT(a, b) = n / ggT(a, b).

 

Sobald eine Zahl n in der Primfaktorzerlegung zwei verschiedene Primfaktoren p und q enthält, ist eine solche Zerlegung möglich: n = pr b, r maximal. Es ist dann b≠1, da b noch den Primfaktor q enthält, und pr und b sind teilerfremd.

 

Dies darf gemäss Aufgabenstellung nicht passieren. n muss deshalb die Potenz eines einzigen Primfaktors p sein. Dies ist auch hinreichend, wie man sofort einsieht.

 

 

Beispiel: 27. Echte Teiler: 1, 3, 9. kgV(1, 3, 9) = 9 ≠ 27.

 
 
 
 
  43. Iteration      
 

Der Vorgang konvergiert gegen die Lösung 0.739085... der Gleichung
cos(x)=x. (Warum?) Sie haben diese Gleichung durch Iteration gelöst.

Nicht bei jeder Gleichung f(x)=x konvergiert das Verfahren, oder man erhält von mehreren existierenden Lösungen nur eine, egal von welchem Startwert man ausging. Es gibt also Lösungen, die als Attraktoren und solche, die als Repulsoren wirken.
Wer tiefer schürfen will, kann auch diese Phänomene genauer untersuchen.

Bild rechts: Die Iteration grafisch. Das Verfahren konvergiert gegen den Schnittpunkt von y=cos(x) mit y=x; der Schnittpunkt wirkt als Attraktor.

Wie funktioniert diese grafische Iteration? Man beginnt mit einem Startwert ("Start") und geht nach oben zum Graphen der Kosinusfunktion. Indem man von diesem Schnittpunkt aus nach rechts auf die Gerade y=x geht und von dort wieder nach unten zur x-Achse (was man grafisch nicht wirklich auszuführen braucht), macht man diesen Kosinuswert wieder zum neuen x-Eingabewert, von dem man erneut den Kosinuswert abliest, also zum Graphen der Kosinusfunktion hochgeht.
So fährt man weiter: Vom neuen Schnittpunkt zur Geraden y=x und wieder in senkrechter Richtung zum Graphen der Kosinusfunktion, usw.

   
 
 
 
  44. Zahlentrick      
 

Das Verfahren terminiert entweder bei der Zahl 1 oder in einer zyklisch durchlaufenen Schleife mit den Zahlen (4; 16; 37; 58; 89; 145; 42; 20). Weitere Schleifen existieren nicht.
Der längste Weg bis zur Endschleife geht von der Zahl 60 oder 6 aus (10 Stufen). Spätestens die 10. Person wird also bei der 1 oder bei der Endschleife landen.
Man kann die 1 ausschliessen und fordern, dass man bei Erreichen der 1 mit einer 2 fortfahren soll. Dann gerät man stets in die unten rot gefärbte Endschleife.

  Man braucht sich also nur die acht Wörter der Seiten 4, 16, 20, 37, 42, 58, 89 und 145 zu merken.
 
 
 
 
 

Bild oben (die linke und rechte Bildhälfte ergeben zusammen das ganze Bild): die Bahnen dieses Zahlenspiels.

Hier noch der Hinweis auf die Online Enzyklopädie der ganzzahligen Zahlfolgen oeis.org.

 

Übrigens: Ein Satz von Fermat besagt, dass sich jede Primzahl, die bei Division durch 4 Rest 1 ergibt als Summe zweier Quadratzahlen darstellen lässt.
Beispiele:
5=22+12; 13=22+32;  17=12+42;    29=22+52;    41=42+52;    53=22+72; usw.
Das obige Strukturbild illustriert dies: Die Primzahlen dieser Form stehen nie am Anfang einer Kette.

 
 
 
 
  45. Spezielle Vielecke?      
 

Antwort: nein. Für einmal sei die Argumentation physikalisch:

Man denke sich das Vieleck mit einer Dicke ausgestattet, so dass es ein Prisma wird.
Betrachten Sie Lot Nr. 2, das vom Schwerpunkt S senkrecht auf die horizontale momentane Standfläche dieses Prismas verläuft. Aus physikalischen Gründen wird das Prisma kippen; es entstünde eine neue Standfläche.

Träfe jetzt das neue Lot auf die neue Standfläche erneut ausserhalb dieser Standfläche auf, so würde das Prisma erneut kippen. So ginge es immer weiter, wenn jedes Lot ausserhalb der aktuellen Standfläche aufträfe: Der Körper würde von selber dauernd kippen (nach links oder nach rechts) und sich folglich ohne Antrieb stets bewegen: Wir hätten ein Perpetuum mobile, was unmöglich ist.

Folglich existiert ein Vieleck mit der geforderten Eigenschaft nicht.

P.S. In neben stehendem Fünfeck treffen zwei der fünf Lote ausserhalb der zugehörigen Seiten auf. Sind Fünfecke denkbar, bei denen die Anzahl der Lote mit dieser Eigenschaft grösser als 2 ist?

   
 
 
 
  46. Zwischenzentralität - Mathe gegen Mafia      
   

Zwischenzentralitätswerte der einzelnen Punkte:

Nr. 1:     0

Nr. 2:     0

Nr. 3:     9.333...

Nr. 4:     1

Nr. 5:     0.333...

Nr. 6:     1

Nr. 7:     1.333...

 
 
 
 
  47. Es gibt nur abzählbar-unendlich viele algebraische Zahlen      
 

Hier nochmals Cantors Definition für die Höhe N eines Polynoms vom Grad n mit Koeffizienten aus ℤ:
N = (Summe der Absolutbeträge der Koeffizienten) + n - 1.

Aufgabe 1:

N=4: 12 Polynome mit natürlichen und 44 Polynome mit ganzen Koeffizienten.

 

Aufgabe 2:

Wäre die Höhe N lediglich als Grad n des Polynoms definiert, gäbe es unendlich viele Koeffizienten-Möglichkeiten (die würden ja gar nicht in die Berechnung von N einfliessen) und es gäbe somit unendlich viele Polynome mit dieser "Höhe".

Wäre die Summe der Absolutbeträge der Koeffizienten allein für die Höhe N verantwortlich, so könnte der Grad und damit die Anzahl Nullstellen beliebig hoch sein.

Cantors Definition beschränkt die Möglichkeiten für die Koeffizienten UND für den Grad (der höchstens gleich N sein kann). Damit wird erst eine Auflistung möglich, wie wir sie am Beispiel N = 4 in der linken Spalte ausgeführt haben.

Auflistung für N = 4: Man bringe die 44 Polynome links in eine Reihenfolge. Anschliessend bringe man innerhalb jedes Polynoms dessen Nullstellen in eine Reihenfolge. Somit hat man für N = 4 die algebraischen Zahlen "aufgezählt". So verfährt man für jede Wahl von N; die N-Werte werden ebenfalls aufsteigend geordnet. Damit entsteht eine Aufzählung aller algebraischer Zahlen.

 
 
 
 
  48. Cantor-Bernstein-Schröder-Theorem      
   

Anmerkung:
Die links unter d) definierte Abbildung h ist eine Bijektion h: ℝ⁺ → [0 ; 1].

Eine Bijektion f: ℝ → (-1 ; 1) lässt sich elementargeometrisch, also ohne CBS-Satz, wie folgt finden:


Der reellen Zahl r auf der x-Achse wird via die Punkte R und S (grüne Pfeile) der Punkt r' im Intervall (-1 ; 1) bijektiv zugeordnet.

Die Formeln ergeben sich direkt via Ähnlichkeit und lauten:



Zuordnung f: ℝ → (-1 ; 1) als Graph:

Statt also ganz ℝ zu studieren, kann man häufig lediglich die "Nullkomma-Zahlen" im Intervall
(-1 ; 1) betrachten.

 
 
 
 
  49. Spiegelzahlen      
 

Seien 10a+b und 10c+d zwei Zahlen, welche die Denksport-Bedingung

(10a+b)(10c+d)=(10b+a)(10d+c)

erfüllen; a, b, c, d ∈ {1,2,3,4,5,6,7,8,9}.
(Die Null entfällt, da wir uns auf echte zweistellige Zahlen beschränken; damit entfallen auch alle Zehnerzahlen, deren Spiegelzahlen einstellig wären.)

Beispiel:  36 und 42 (a=3, b=6, c=4, d=2): Es gilt: 36⋅42=63⋅24.

Ausmultiplizieren und Kürzen der Gleichung (10a+b)(10c+d)=(10b+a)(10d+c) zeigt,

dass die Denksportbedingung genau dann gilt, wenn a⋅c=b⋅d oder, äquivalent, a:b=d:c ist.

Das bedeutet zum Beispiel, dass zu 12 als Partnerzahl noch genau 21, 42, 63 und 84 in Frage kommen (d:c=1:2).
12 selber kann aber auch noch durch die Zahlen 24, 36 und 48 ersetzt werden, welche dasselbe Ziffernverhältnis 1:2 haben wie 12. Dies führt dann wieder zu einer korrekten Gleichung.
Beispiel: 36⋅42 = 63⋅24 erfüllt immer noch a:b=d:c und somit die Denksportbedingung.

Zur Zahl 12 gibt es also folgende Möglichkeiten: Wir haben eine linke Schublade L von möglichen Ausgangszahlen (a:b=1:2) und eine rechte Schublade R von dazu möglichen Partnerzahlen (d:c=1:2 oder, äquivalent, c:d=2:1):
L = {12, 24, 36, 48}, R = {21, 42, 63, 84}. (R besteht aus den Spiegelzahlen von L.)

Man entnehme eine Zahl aus L und eine aus R. Dies ergibt eine Gleichung, welche die Denksportbedingung erfüllt: Beispiel: 36⋅84 = 63⋅48; a:b=d:c ist erfüllt.

Triviale Gleichungen
Es gibt 45 triviale Schnapszahlgleichungen der Art 11⋅22=11⋅22 oder 55⋅66=55⋅66, usw.
Dann gibt es 36 ebenfalls triviale Gleichungen der Art 12⋅21=21⋅12 oder 15⋅51=51⋅15, bei denen völlig klar ist, dass die Ziffernumkehr dasselbe Produkt liefert.

Beispiel: Zur Zahl 15 existiert kein Vielfaches mit Ziffernverhältnis a:b=1:5 (1:5 ist wegen der 5 im einstelligen Bereich nicht erweiterbar); wir haben L={15}, R={51}. Diese einelementigen Schubladen genieren lediglich die triviale Gleichung 15⋅51=51⋅15.

Nicht-triviale Lösungen gibt es nur, wenn wir die Schnapszahlen weglassen und wenn die oben erwähnten Mengen L und R mehr als ein Element enthalten.

 

Es bleiben 14 nicht-triviale Gleichungen:

Es bleiben folgende zweistellige Zahlen, die nicht-triviale Gleichungen liefern können (alle Ziffern müssen ≤ 4 sein, damit die Ziffernverhältnisse a:b im einstelligen Bereich erweiterbar sind und so die Mengen L und R mindestens 2 Elemente haben):

12, 13, 14, (21), 23, 24, (31), (32), 34, (41), (42), (43). Die eingeklammerten Zahlen sind die Umkehrzahlen von bereits aufgezählten Zahlen und kommen in die R-Schublade. Zu den Zahlen der Liste fügen wir noch die Vielfachen hinzu, die bei schriftlicher Multiplikation keine Überträge generieren (mithin dasselbe Ziffernverhältnis haben) und verstauen diese 28 Zahlen in folgende L-R-Schubladen, die nun alle zwei oder mehr Elemente haben:

L = {12, 24, 36, 48} und R = {21, 42, 63, 84} generiert 6 nicht-triviale Gleichungen
L = {13, 26, 39} und R = {31, 62, 93} generiert 3 nicht-triviale Gleichungen
L = {14, 28} und R = {41, 82} generiert 1 nicht-triviale Gleichung
L = {23, 46, 69} und R = {32, 64, 96} generiert 3 nicht-triviale Gleichungen
L = {34, 68} und R = {43, 86} generiert 1 nicht-triviale Gleichung


Haben L und R je n Elemente, so ergeben sich n⋅(n-1)/2 nicht-triviale Gleichungen.
Es entstehen somit 6 + 3 + 1 + 3 + 1 = 14 nicht-triviale Gleichungen.

Die Formel n⋅(n-1)/2 sei am Beispiel L = {13, 26, 39} und R = {31, 62, 93} erläutert:
13⋅62 = 31⋅26; 13⋅93 = 31⋅39; 26⋅93 = 62⋅39. Weitere nicht-triviale Gleichungen sind mit diesem L-R-Vorrat nicht möglich. Wir erhalten 3⋅2/2 = 3 nicht-triviale Gleichungen.

Dies sind die 14 nicht-trivialen Gleichungen:

12⋅42=21⋅24 12⋅63=21⋅36 12⋅84=21⋅48 24⋅63=42⋅35 24⋅84=42⋅48 36⋅84=63⋅48
13⋅62=31⋅26 13⋅93=31⋅39 26⋅93=62⋅39      
14⋅82=41⋅28          
23⋅64=32⋅46 23⋅96=32⋅69 46⋅96=64⋅69      
34⋅86=43⋅68          

(Erneut verifiziert man überall a⋅c = b⋅d oder äquivalent a : b = d : c)

 
 
 
 
  50. n+1 natürliche Zahlen      
 

Die Menge M = {1, 2, ... , 2n} enthält n gerade und n ungerade Zahlen.
Beispiel: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} enthält 5 gerade und 5 ungerade Zahlen.
Wir wählen n+1 Zahlen aus M aus. Somit enthält jede Auswahl mindestens eine gerade und eine ungerade Zahl, d.h. jede Auswahl ist "gemischt".

Wir nehmen nun eine (oder allenfalls die eine) gerade Zahl und dividieren sie so lange durch 2, bis das Ergebnis ungerade wird (ist die gerade Zahl eine Zweierpotenz, wird das Ergebnis schliesslich 1). Wenn das ungerade Ergebnis u in unserer Auswahl liegt, sind wir fertig: Wir haben u und 2ⁱ⋅u in der Auswahl.
Falls u nicht in der Auswahl liegt, muss dafür notwendigerweise eine weitere gerade Zahl in der Auswahl liegen (für jede nicht-vorkommende ungerade Zahl liegt eine gerade Zahl in der Auswahl). MIt dieser verfahren wir gleich. Es entsteht erneut eine ungerade Zahl. Liegt sie in der Auswahl, sind wir fertig, wenn nicht, liegt eine weitere gerade Zahl vor, mit der wir gleich verfahren, usw.
Schliesslich muss eine der entstehenden ungeraden Zahlen in der Auswahl liegen, denn jede Auswahl ist ja "gemischt". Damit sind wir fertig. u und 2ⁱ⋅u liegen in der Auswahl und u teilt 2ⁱ⋅u.

 

Beispiel: M = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. n = 5, n+1 = 6. Wir wählen 6 Zahlen aus M.

Auswahlbeispiel 1 : {1, 2, 4, 6, 8, 10}.

1 teilt jede andere Zahl der Auswahl.

Auswahlbeispiel 2: {2, 3, 5, 6, 8, 9}.

Wir wählen z.B. 8 und teilen fortlaufend durch 2. Es entsteht 1: nicht in der Auswahl. Wir nehmen eine andere gerade Zahl, z.B. 4: Fortlaufendes Teilen durch 2 liefert erneut 1: nicht in der Auswahl. Wir nehmen eine andere gerade Zahl: 6. Fortlaufendes Teilen durch 2 liefert 3: Liegt in der Auswahl: 3 teilt 6.

 
 
 
 
  51. Gewichtete Würfel      
 

Sei xi die Wahrscheinlichkeit, dass der erste Würfel die Augenzahl i zeigt.
Sei yj die Wahrscheinlichkeit, dass der zweite Würfel die Augenzahl j zeigt.

Wir vergleichen die "Extreme": Augensumme 2 und Augensumme 12 mit Augensumme 7.
P steht für "Probability":
Es ist P(Augensumme 2)=P(Augensumme 7)=1/11 und P(Augensumme 12)=P(Augensumme 7)=1/11;
formal:
(1): x1y1 = x6y1 + x5y2 + x4y3 + x3y4 + x2y5 + x1y6 = 1/11; es folgt x1y1 und damit auch x1, y1 > 0
(2): x6y6 = x6y1 + x5y2 + x4y3 + x3y4 + x2y5 + x1y6 = 1/11; es folgt x6y6 und damit auch x6, y6 > 0

Aus (1) und (2) folgt:
(3.1): x1(y1 - y6) = x6y1 + x5y2 + x4y3 + x3y4 + x2y5 und
(3.2): y1(x1 - x6) = x5y2 + x4y3 + x3y4 + x2y5 + x1y6
(4.1): x6(y6 - y1) = x5y2 + x4y3 + x3y4 + x2y5 + x1y6 und
(4.2): y6(x6 - x1) = x6y1 + x5y2 + x4y3 + x3y4 + x2y5

Die rechten Seiten obiger Gleichungen sind > 0, da x6y1 und x1y6 > 0 sind und kein Summand negativ ist.
Folglich sind auch die linken Seiten positiv und es folgt y1 > y6, x1 > x6, aber auch y6 > y1 und x6 > x1, was ein Widerspruch ist.

Eine Programmierung der Würfel so, dass alle Summen gleich wahrscheinlich sind, ist unmöglich.

     
 
 
 
  52. Mathe-Olympiade 1962, Aufgabe 1      
 

Die Zahl sei x. Wir lassen schrittweise die neue Zahl entstehen:

- Subtraktion der Einer: x - 6.
- Division durch 10 (damit rücken alle Ziffern 1 Stelle nach rechts): (x - 6) / 10
- Vorne die 6 anhängen: 6⋅10n + (x - 6) ⁄ 10 = neue Zahl. (n ist vorläufig noch unbestimmt.)

Es entsteht die Gleichung 4x = 6⋅10n + (x - 6) ⁄ 10. Multiplikation mit 10 ergibt

40x = 6⋅10n+1 + x - 6 oder 39x = 6⋅(10n+1 - 1) bzw. 13x = 2⋅(10n+1 - 1).

Damit ergibt sich x = 2⋅(10n+1 - 1) ⁄ 13.

13 teilt somit (10n+1 - 1). Dies trifft erstmals zu für n = 5, also für 999'999.

Damit wird x = 2⋅(106 - 1) ⁄ 13 = 153'846.

Probe: 615'384 ist das Vierfache von 153'846.

 

Eine viel elegantere Lösung wird hier gezeigt:

 

https://artofproblemsolving.com/wiki/index.php/IMO_Problems_and_Solutions#1962

 

alte Zahl: endet mit 6, neue Zahl beginnt mit 6:   6......
alte Zahl ist ein Viertel der neuen Zahl, somit neue Zahl (schriftlich) durch 4 teilen:

Neue Zahl : 4 teilen :     6............ :4 = 1........... = alte Zahl => neue Zahl = 61...
Weiter schriftlich teilen: 61.......... :4 = 15......... = alte Zahl => neue Zahl = 615...
Weiter schrifltich teilen: 615.........:4 = 153....... = alte Zahl => neue Zahl = 6153...
Weiter schriftlich teilen: 6153.......:4 = 1538..... = alte Zahl => neue Zahl = 61539...
Weiter schriftlich teilen: 61538.....:4 = 15384... = alte Zahl => neue Zahl = 615384...
Weiter schriftlich teilen: 615384...:4 = 153846  = alte Zahl, aufgehend.

 

 
 
 
 
  53. Um 1 verminderte Zweierpotenzen      
 

a) 23 - 1 = 7 ist z.B. durch 7 teilbar. 23 = 8 ergibt bei Division durch 7 Rest 1.
Wir fragen allgemein: Welche Zweierpotenzen ergeben bei Division durch 7 Rest 1?

2er-Potenz 20 21 22 23 24 25 26
Siebnerrest 1 2 4 1 2 4 1

Alle Zweierpotenzen der Form 23n, n ∈ ℕ, ergeben Siebnerrest 1, d.h. die Zahlen
23n - 1 (oder gleichbedeutend 8n - 1) sind durch 7 teilbar.

  b)
Damit eine um 1 vermehrte Zahl durch 7 teilbar ist, muss sie Siebnerrest 6 haben (Bsp: 6, 13, 20, usw.).
Eine Zweierpotenz hat jedoch, wie die Tabelle links zeigt, nie Siebnerrest 6.
Es gibt folglich keine Zahl 2n+ 1, n ∈ ℕ, die durch 7 teilbar ist.
 
 
 
 
  54. Näherungsbruch für Wurzel 2      
 

Wir erinnern uns an das uralte babylonische Verfahren, um eine Folge sich annähernder Bruchzahlen zu berechnen.

Als Startzahl wählen wir 1.4, also den Anfang der Dezimaldarstellung von Wurzel 2.



Der Startwert ist wichtig. Wir wählten den Bruch mit einstelligem Zähler und Nenner, welcher der Wurzel 2 am nächsten kommt. Ein weiter entfernter Startwert (z.B. 1.5) würde uns den Bruch 99 ⁄ 70 nicht liefern; es entstünde 17 ⁄ 12.

 

Konvergenzverhalten des babylonischen Verfahrens und Abschätzung von 99 ⁄ 70:

  Mit jedem Iterationsschritt verdoppelt sich die Anzahl korrekter Stellen.
  Der nächste Bruch 19'601 ⁄ 13'860 stimmt bereits auf 8 Nachkommastellen: 1.41421356...
  Das babylonische Verfahren konvergiert somit sehr schnell (quadratisch).

 

 
 
 

Ergänzung: Das Newton-Verfahren zur iterativen Bestimmung von Nullstellen:

Gegeben ist eine zweimal stetig differenzierbare Funktion mit Nullstelle.
Beispiel: x2 - 2 = 0 mit Nullstelle Wurzel 2.
Taschenrechner ermitteln diese Nullstelle iterativ. Newton-Verfahren:

1. Wähle einen Punkt x0. Lege bei f(x0) die Tangente an den Funktionsgraphen; diese hat die Nullstelle x1.
2. Lege bei f(x1) die Tangente an den Funktionsgraphen; diese hat die Nullstelle x2. Fahre so weiter.

Die Punkte xn werden bei günstiger Wahl der Startstelle x0 gegen die Nullstelle der Funktion f konvergieren.

 

Herleitung der Iterationsformel:

Im Fall der Quadratwurzeln ist das Newton-Verfahren identisch mit dem alten babylonischen Verfahren der Mittelwerte. Der Taschenrechner benötigt nur ganz wenige Iterationsschritte, um die Wurzeln auf hinreichend viele Nachkommastellen genau zu bestimmen.

 
 
 
 
  55. Summen und Produkte      
 

Die Menge M = {1, 2, ... , n} werde disjunkt aufgeteilt in die Teilmengen S ("Summanden") und F ("Faktoren").
Die Vereinigung von S und F ergibt M.
Die Summe der Elemente von S soll dasselbe ergeben wie das Produkt der Elemente von F.

Sei zunächst n ungerade, d.h. n = 2k+1, k≥2.

Die Summe aller Elemente von M ist n(n+1)/2 = (2k+1)(2k+2)/2 = (2k+1)(k+1) = 2k2+2k+k+1. (*)

Nun bildet man mit 1, k und 2k die Menge F, die übrigen Zahlen bilden die Menge S.
Die Summe der Elemente von S ist deshalb nach (*) gleich 2k2, ebenso das Produkt der Elemente von F.

Diese Konstruktion funktioniert für alle k≥2, d.h. für alle ungeraden Zahlen ≥5.

Beispiel 1:
n = 7, d.h. k = 3: F = {1, 3, 6}, S = {2, 4, 5, 7}. 1⋅3⋅6 = 2+4+5+7 = 18.

Beispiel 2:
n = 99, d.h. k = 49: F = {1, 49, 98}. S = {2, 3, ... , 48, 50, 51, ... , 97, 99}.
Summe bzw. Produkt = 4802.

 

Der Fall n gerade, d.h. n = 2k, ist weniger einfach zu knacken. Man kommt ihm aber auf die Spur durch Vergleich von n = 7 und n = 6, d.h. beide Male k = 3:

n = 7:
1⋅3⋅6 = 2+4+5+7

n = 6:
1⋅2⋅6 = 3+4+5

Offenbar wird der mittlere Faktor um 1 verringert, was das Gesamtprodukt um 6 kleiner macht:
Auf der Summenseite wird 2 durch 3 ersetzt (Zuwachs 1), jedoch 7 weggelassen (Verringerung 7) , was die Summe insgesamt ebenfalls um 6 verkleinert. Somit bleiben Summe und Produkt wieder gleich.

Dieses Beispiel kann nun leicht allgemein gefasst werden:

n = 2k. n(n+1)/2 = 2k(2k+1)/2 = k(2k+1) = 2k2+k. (*)
Nun bildet man mit 1, (k-1) und 2k die Menge F; der Rest bildet S.
Die Summe der Elemente von S wird somit nach (*) 2k2+k - 1 - (k-1) - 2k = 2k2 - 2k.
Das Produkt der Elemente von F wird ebenfalls gleich 2k2 - 2k.
Dieses Vorgehen funktioniert für alle k≥3, d.h. für alle geraden Zahlen ≥6.

Insgesamt gelingt eine Aufteilung von M = {1, ... , n} in F und S mit Produkt der Elemente von F gleich Summe der Elemente von S für alle n≥5. (Eine triviale Lösung ausserhalb des beschriebenen Rezeptes ist für n = 3 möglich: F = {3}, S = {1, 2}.) Die Rezepte für ungerade und gerade n differieren ein wenig.

Beispiel: n = 10, d.h. k = 5: F = {1, 4, 10}, S = {2, 3, 5, 6, 7, 8, 9}. Summe bzw. Produkt = 40.

 
 
 
 
  Bemerkung:
Man kann jeder natürlichen Zahl ≥5 den gemäss obigem Verfahren gewonnenen Summen- bzw. Produktwert zuordnen. Dies führt zur Folge 8 12 18 24 32 40 50 ..., deren Aufbau leicht zu durchschauen ist.
In der Online Enzyklopädie der ganzen Zahlfolgen werden weitere Anwendungen dieser Folge gezeigt.
  Insbesondere ergibt sich die Summe bzw. das Produkt bei gegebenem n≥5 sofort als FLOOR((n-1)2/2).
Bsp: n = 6. FLOOR(52/2) = 12.   n = 7. FLOOR(62/2) = 18.    n = 99: FLOOR(982/2) = 4802.
 
 
 
 
  56. IMO 1966, Aufgabe 1      
 

A, B, C zusammen: 25 Personen
Wir wählen z.B. folgende Variablen für die entsprechenden Personenzahlen:
x:     nur B gelöst (gelb)
y:     nur C gelöst (grün)
z:     B UND C, nicht aber A gelöst (rot)

 

Hier nochmals die Bedingungen:

(1): A, B, C zusammen: 25
(2): Unter NICHT-A: Doppelt so viele B gelöst wie C gelöst, d.h. x+z=2(y+z)
(3): NUR-A: 1 mehr als "A und mindestens 1 weitere Aufgabe gelöst" (blau markierter Bereich),
       d.h. Anzahl Blaue = Anzahl Weisse minus 1
(4): Genau 1 gelöst: Davon die Hälfte NICHT-A (Gelb plus Grün; x + y),
       somit NUR-A (Weiss) ebenfalls x + y (im Diagramm eingetragen)

Aus (4) folgt: Anzahl NUR-A gleich x + y.

Aus (3) folgt: Blau markierter Teil: x + y - 1.

Daraus folgt: A: 2x + 2y - 1.

Daraus folgt zusammen mit (1): NICHT-A: 25 - 2x - 2y + 1 oder 26 - 2x - 2y.

Daraus folgt (s. Diagramm): 26 - 2x - 2y = x + y + z oder 26 - 3x - 3y = z    (*)

Aus (2) folgt: x + z = 2y + 2z oder x = 2y + z    (**)

Setzen wir (**) in (*) ein, folgt: 26-6y-3z-3y=z oder

26 = 9y + 4z.

Die ganzzahlige Lösung ist y = z = 2. Daraus folgt mit (**) x = 6.

Lösung: 6 Personen lösten nur B.

 
 
 
 
  57. IMO 1968, Aufgabe 2      
 

Sei x = dn⋅10n + dn-1⋅10n-1 + ... + d0 eine n+1-stellige natürliche Zahl
mit Ziffernprodukt dn⋅dn-1⋅ ... ⋅ d0 = x2 - 10x - 22.

1) x ist nicht einstellig. Auch ist x ≠ 10 und x ≠ 11. Somit ist x ≥ 12.

2) Es gilt di ≠ 0 für alle i, sonst wäre das Ziffernprodukt x2 - 10x - 22 = 0;
    diese Gleichung hat jedoch keine Lösung x in den natürlichen Zahlen.

3) Es gilt
    x2 - 10x - 22 = dn⋅dn-1⋅ ... ⋅ d0 < dn⋅10⋅ ... ⋅10 = dn⋅10n

    < dn⋅10n + dn-1⋅10n-1 + ... + d0 = x ,

    also x2 - 10x - 22 < x   =>  x2 - 11x - 22 < 0 => x ≤ 12.

    Zusammen mit x ≥ 12 folgt x = 12.

    In der Tat ist 1⋅2 = 122 - 10⋅12 - 22 = 2.

x = 12 ist somit die einzige Lösung.

 

 

 
 
 
 
  58. IMO 1967, Aufgabe 6      
 

Es muss m = 7k + 1 sein.

1.Tag verteilt: 1 + k, restliche Medaillen: 6k
2.Tag verteilt: 2 + (1/7)⋅(6k - 2).

Das bedeutet: 6k - 2 muss durch 7 teilbar sein.
Dies trifft erstmals zu für k = 5.

 

Wir probieren k = 5 => m = 36:

1. Tag verteilt: 1 + (1/7)⋅35 = 1 + 5 = 6, restliche Medaillen 30
2. Tag verteilt: 2 + (1/7)⋅28 = 2 + 4 = 6, restliche Medaillen 24
3. Tag verteilt: 3 + (1/7)⋅21 = 3 + 3 = 6, restliche Medaillen 18
4. Tag verteilt: 4 + (1/7)⋅14 = 4 + 2 = 6, restliche Medaillen 12
5. Tag verteilt: 5 + (1/7)⋅  7 = 5 + 1 = 6, restliche Medaillen   6
6. Tag verteilt: 6 + (1/7)⋅  0 = 6 + 0 = 6, restliche Medaillen   0

Lösung: m = 36, n = 6.

 
 
 
 
  59. Keine Primzahlen      
 

n4 + 4 lässt sich wie folgt faktorisieren:

n4 + 4 = (n2 + 2)2 - 4n2 = (n2 + 2)2 - (2n)2 (erste Binomische Formel). Dies ist nun ein Term der Form "Quadrat minus Quadrat", und solche Terme können mithilfe der dritten Binomischen Formel faktorisiert werden:

(n2 + 2 + 2n)(n2 + 2 - 2n).

 

Anstelle der 4 sind weitere Zahlen a ∈ ℕ möglich, so dass n4 + a für alle n ∈ ℕ faktorisierbar ist:

n4 + a = n4 + 4b4 = (n2 + 2b2)2 - 4n2b2 = (n2 + 2b2 + 2nb)(n2 + 2b2 - 2nb).

D.h. setze a = 4b4, b∈ ℕ. Unser vereinfachter Fall war b = 1.

 
 
 
 
  60. Teilbarkeit 1      
 

p teilt die Differenz (n2 + 1) - (m2 + 1) = n2 - m 2

= (n + m)(n - m). Aber p teilt (n - m) nicht, da p > n - m,

also ist p Teiler von m + n und deshalb auch von (m + n)2 =

m2 + 2mn + n2. Wir subtrahieren n2 + 1 und m2 + 1 (ebenfalls Vielfache von p) und erhalten:

p teilt 2mn - 2 = 2(mn - 1). Folglich (p > 2) ist p Teiler von mn - 1.

     
 
 
 
  61. Eine Spielerei mit Teilmengen      
 

Wir vermuten aufgrund von Versuchen: Summe = n. Für n = 1, 2, 3 stimmt die Vermutung.

Sei die Vermutung für 1 bis n bewiesen. Welche Teilmengen kommen für n + 1 dazu?

Es sind {n + 1} und {n + 1} vereinigt mit jeder Teilmenge vom Fall n.

 

Das ergibt einen Summenzuwachs von 1/(n + 1) + n/(n + 1) = 1.

Folglich ist die Summe im Fall n + 1 gleich n + 1.

 
 
 
 
  62. Primzahllücken      
 

Beispiel für eine Zahl, hinter welcher eine Primzahl-Lücke ≥9 entsteht:

z = 2⋅3⋅5⋅7⋅9 + 1 = 1891.

Begründung:

z + 1 ist gerade
z + 2 ist durch 3 teilbar
z + 3 ist gerade
z + 4 ist durch 5 teilbar
z + 5 ist gerade
z + 6 ist durch 7 teilbar
z + 7 ist gerade
z + 8 ist durch 9 teilbar
z + 9 ist gerade

Hinter z sind also mindestens 9 Nachfolgerzahlen nicht prim.

Bemerkung: Statt das Produkt aller ungerader Zahlen ≤ 9 zu wählen und 1 zu addieren, genügte es auch, lediglich das Produkt aller Primzahlen ≤ 9 zu wählen und dazu 1 zu addieren. So entstünde ein kleineres z, hinter dem eine Primzahllücke von mindestens Grösse 9 besteht.

 

Für eine Lücke von mindestens Länge 100 bzw. 101 bilden wir analog zum Beispiel links:

z = 2⋅3⋅5⋅7⋅9⋅ ... ⋅101 + 1 = 5.505292122...⋅1080. Hinter dieser 81-stelligen Zahl klafft eine Primzahl-Lücke von mindestens Länge 101.

Es gibt somit beliebig grosse Primzahllücken, allerdings "sehr, sehr weit hinten" in der Zahlreihe.


Das führt zu Folgefragen:

Wird die Primzahldichte immer kleiner? - Nicht unbedingt; als Kompensation für die riesigen Lücken könnten dazwischen auch wieder gehäuft Primzahlen vorkommen, z.B. Primzahlzwillinge. Und die grossen Lücken entstehen "astronomisch weit hinten".
Die Primzahldichte wird jedoch tatsächlich kleiner; trotzdem gibt es unendlich viele Primzahlen!

 
 
 
 
  63. Zahlensteckbrief - Zahlen gesucht      
 

Die Teiler einer Zahl, z.B. 75, weisen folgende Symmetrie auf (Beispiel n = 75):

1, 3, 5, 75/5, 75/3, 75/1.

Sei n eine solche Zahl.
Seien 1, a, b, ... , n/b, n/a, n ihre Teiler mit Produkt n3.

Daraus folgt, dass n genau 6 Teiler hat:

1, a, b, n/b, n/a, n/1: Das Produkt dieser Teiler ist genau dann gleich n3.

Ergebnis:
Genau die Zahlen mit 6 Teilern erfüllen somit die verlangte Eigenschaft.

Nun fragen wir: Welche Zahlen haben genau 6 Teiler?

 

Wie bestimmt man die Anzahl Teiler einer Zahl? Beispiel 75 = 31⋅52. Vom Primfaktor 3 kann man die nullte oder die erste Potenz nehmen, vom Primfaktor 5 die nullte, erste oder zweite Potenz. Das ergibt (1+1)⋅(2+1) = 6 Möglichkeiten, Teiler zu bilden.

Allgemein: Sei n = p1a1⋅p2a2⋅ ... in die Primfaktor-Potenzen zerlegt.

Anzahl Teiler: (a1 +1)⋅(a2 +1) = 6

Es ergeben sich die beiden Möglichkeiten 1⋅6 und 2⋅3.

Erste Möglichkeit: a1 +1 = 1 => a1 = 0 und a2 = 5, d.h. n = p10⋅p25 = p25

Zweite Möglichkeit: a1 +1 = 2 => a1 = 1 und a2 = 2, d.h. n = p11⋅p22

Lösung: n ist von der Form p5 oder p⋅q2,  (p, q prim).

 

Beispiele: 243 ist eine Lösung vom Typ p5 und 75 ist eine Lösung vom Typ p⋅q2.

 
 
 
 
  64. Teilbarkeit 2      
 

Sei p eine Primzahl grösser als 3.

a)
Es ist p2 + 11 = p2 - 1 + 12 = (p - 1)(p + 1) + 12.

p - 1, p und p + 1 sind drei im Zahlenstrahl der natürlichen Zahlen aufeinanderfolgende Zahlen. p selber ist ungerade und nicht durch 3 teilbar (beachte: p > 3). Deshalb sind entweder p-1 oder p+1 durch 3 teilbar, denn von drei benachbarten Zahlen auf dem Zahlenstrahl ist stets eine durch 3 teilbar - und p ist es nicht.
Deshalb ist (p-1)(p+1) durch 3 teilbar.
p-1 und p+1 sind gerade Zahlen. Als aufeinanderfolgende gerade Zahlen ist eine davon sogar durch 4 teilbar.
Deshalb ist (p-1)(p+1) durch 8 teilbar.
Zusammen ergibt sich: (p-1)(p+1) ist durch 24 teilbar.

Folglich ist p2 + 11 = (p-1)(p+1)+12 als Summe zweier durch 12 teilbare Zahlen ebenfalls durch 12 teilbar, was zu zeigen war.

 

b)
p2 + 11 ist nach a) ein echtes Vielfaches von 12 (beachte: p > 3). Der Faktor 12 hat bereits 6 Teiler, nämlich {1, 2, 3, 4, 6, 12}. Ein echtes Vielfaches von 12 hat auf jeden Fall noch mehr Teiler, also mehr als 6 Teiler.

 

Bemerkung:
Die einzige Primzahl, für die p2 + 11 genau 6 Teiler hat, ist 3.
Begründung:
32 + 11 = 20 hat die Teiler {1, 2, 4, 5, 10, 20}. 32 + 11 ist auch nicht durch 12 teilbar, da für p = 3 ein Argument im Beweis links nicht funktioniert. Welches?
Für p = 2 ergibt sich 22 + 11 = 15 mit nur 4 Teilern.
p = 1 ergäbe 12 + 11 = 12, eine Zahl mit 6 Teilern. Aber 1 ist keine Primzahl.

 
 
 
 
  65. Eine Aufgabe zu positiven reellen Zahlen      
 

a)
Sei a > 0.
(a -1)2 ≥ 0 ⇒ a2 - 2a + 1 ≥ 0 ⇒ a2 +1 ≥ 2a, daraus folgt (Division durch a > 0):

a + a-1 ≥ 2.

(a > 0 ist wesentlich; bei der Division durch eine positive Zahl bleibt das Ungleichungs-Relationszeichen erhalten.)


Visualisierung: Die Funktion y = x + 1/x für x > 0. Es ist stets y ≥ 2.

b)
n = 1: Der Fall ist trivial: a1 = 1 und (1 + 1) ≥ 21 .

n = 2: Die Zahlen seien a und a-1.
⇒ (1 + a)(1 + a-1) = 1 + a + a-1 + 1 = 2 + (a + a-1) ≥ 2 + 2 = 22 gemäss Teilaufgabe a).

 

n = 3:
Die Zahlen seien a, b und (ab)-1 mit a, b > 0.
Die Wahl der letzten Zahl berücksichtigt die Voraussetzung, dass das Produkt aller Zahlen gleich 1 sein soll.

(1 + a)(1 + b)(1 + (ab)-1) = 1 + a + b + ab + (ab)-1 + b-1 + a-1 + 1.

Wir haben 23 Summanden.
Die roten Summanden sind die Kehrwerte der schwarzen, fett markierten Summanden.
Es entstehen 4 Paare "Zahl plus Kehrwert", deren Paarsumme gemäss Teilaufgabe a) je ≥ 2 ist:
(1 + 1) + (a + a-1) + (b + b-1) + (ab + (ab)-1) ≥ 2 + 2 + 2 + 2.
Die Gesamtsumme ist folglich ≥ 23.





Verallgemeinerung:
Auch für beliebige n ∈ ℕ entstehen Summen mit 2n Summanden, die sich zu 2n-1 Paaren des Typs "Zahl plus Kehrwert" mit je Paarsummenwert ≥ 2 gruppieren lassen.
Somit ist die Gesamtsumme ≥ 2⋅2n-1 = 2n.
Gleichheit besteht genau dann, wenn alle ai = 1 sind.

 
 
 
 
  66. Ein formales Buchstabenspiel      
 

Hier nochmals die Vereinfachungsregeln:
(1): aaa = 1
(2): bbbb = 1
(3): abab = 1

Wir gewinnen zunächst weitere Vereinfachungsregeln:

Aus (3) entsteht durch Linksmultiplikation mit aa:
aaabab = aa => (wegen (1))
(4): bab = aa

Aus (3) folgt durch Rechtsmultiplikation mit bbb:
ababbbb = bbb => (wegen (2))
(5): aba = bbb

 

Nun folgt:

abbaaaabba = abbabba = abaaba (wegen (4)) = (aba)(aba) = (bbb)(bbb) (wegen (5)) = (bbbb)bb = bb (wegen (2)).

Dies ist die maximale Vereinfachung.

 

Theoretischer Hintergrund:
Dieses Buchstabenspiel erzeugt die Würfeldrehgruppe. a entspricht einer Würfeldrehung um 120° um eine Körperdiagonale des Würfels, b entspricht einer 90°-Drehung um eine Seitenfläche. ab entspricht einer 180°-Drehung um eine Achse, die die Mitten zweier diagonal gegenüberliegender Kanten verbindet.

 
 
 
 
 

Exkurs: Die Würfeldrehgruppe

Vereinbarung: Blicken wir in Pfeilrichtung einer Achse, geschehe die Drehung im Gegenuhrzeigersinn. Die Drehachsen seien raumfest gedacht, d.h. drehen mit dem Würfel nicht mit; man kann sie sich als eine Art raumfester "Motoren" vorstellen.

Es gibt 24 Würfeldrehungen (inkl. der neutralen Operation "id").

Drehungen:

keine Drehung: Neutralelement id ("Identität").

orange Achsen: z1: Drehung um die z-Achse um 90°; z2: Drehung um die z-Achse um 180°, z3: Drehung um die z-Achse um 270°. Analog Drehungen um die x- und die y-Achse.

grüne Achsen: Drehungen um 120° bzw. 240° um die Körperdiagonalen.

blaue Achsen: Drehungen um 180° um die gezeichneten Kantenmittenachsen.

 

Zwei Würfeldrehungen, hintereinander ausgeführt, können durch eine einzige Drehung ersetzt werden. Unten stehende Gruppentafel gibt darüber Auskunft. Die Tabelle ist so aufgebaut, dass man die Operationen von rechts nach links liest. a1 x3 bedeute: Führe zuerst x3 aus und dann a1. Gelesen: "a1 nach x3". Diese Kombination lässt sich gemäss Tabelle ersetzen durch z1.

Im Buchstabenspiel von Aufgabe 66 entspricht a der Drehung a1 und b der Drehung z1.
Somit wird die Motivation für die Wahl der Vereinfachungsregeln klar:
aaa sind drei Drehungen a1 mit je 120°, somit eine 360°-Drehung, welche den Würfel wieder in die ursprüngliche Lage bringt; aaa wirkt somit neutral: aaa = 1.
bbbb sind vier 90°-Drehungen um die z-Achse, was ebenfalls keine Veränderung bewirkt: bbbb = 1.

ab bedeutet: a1 z1 = k1 = 180°-Drehung. Somit ist abab neutral: abab = 1.

Unsere Denksportaufgabe 66 ging aus von x2 y2 = z2.
x2 entspricht abbaa (Operationen immer von rechts nach links gelesen!), y2 entspricht aabba. x2 y2 entspricht somit abbaaaabba, was vereinfacht bb ergeben sollte.
Mithilfe der drei Vereinfachungsregeln liess sich dies zeigen.

Die Buchstaben a, b und die drei Vereinfachungsrelationen aaa = bbbb = abab = 1 erzeugen die Würfeldrehgruppe. Diese ist übrigens isomorph zur Symmetrischen Gruppe S4 (jeder Würfeldrehung entspricht eineindeutig eine Permutation der vier Körperdiagonalen).

 
 
 
 
  67. Unendlich viele Primzahlen der Form 3n-1      
 

Um etwas anschaulicher zu werden, färben wir die natürlichen Zahlen ein:

grün: 0, 3, 6, 9, 12, ...: Form 3n

rot: 1, 4, 7, 10, 13, ...: Form 3n + 1

blau: 2, 5, 8, 11, 14, 17, ... : Form 3n - 1

h1) Das Produkt zweier roter Zahlen ist wieder rot: (3n + 1)(3m + 1) = 9mn + 3n + 3m + 1 = 3(3mn+n+m)+1.

h2) Wir betrachten eine zerlegbare blaue Zahl x. Sie enthält gewiss keinen grünen Faktor, sonst wäre die Zahl selber grün (durch 3 teilbar). Enthielte die Zerlegung von x ausschliesslich rote Faktoren, wäre das Produkt, also x, nach h1 selber rot; x ist aber blau. Somit muss x mindestens einen blauen Primfaktor enthalten.

Beispiel: 14 = 27.

 

Lösung der Aufgabe:

Gäbe es in der blauen Folge eine grösste Primzahl P, so würden wir alle Primzahlen ≤ P betrachten, wieder wie im ursprünglichen euklidschen Beweis deren Produkt bilden und davon 1 subtrahieren.
Das Ergebnis ist eine blaue Zahl N.

Ist N prim, steht dies im Widerspruch zur Annahme einer grössten blauen Primzahl.
Ist N nicht prim, zerlegt N sich und enthält nach h2 mindestens einen blauen Primfaktor, der jedoch keiner der bisher vorkommenden Primfaktoren sein kann, mithin auch grösser als P ist: erneuter Widerspruch.

Die blaue Folge der Zahlen vom Typ 3n - 1 enthält somit ebenfalls unendlich viele Primzahlen, d.h. die Folge der Primzahlen 2, 5, 11, 17, 23, 29, 41, ... bricht nie ab oder anders gesagt: Es gibt unendlich viele Primzahlen der Form 3n-1.

Weitere Hinweise zur Folge 2, 5, 11, 17, 23, 29, 41, ..: Online Encyclopedia of Integer Sequences OEIS.

Aufgabe und Beweisidee nach Rademacher, Toeplitz: Von Zahlen und Figuren, Springer 1968, p.4f.

 
 
 
 
  68. Binomialkoeffizient und Primfaktoren      
   

Bemerkung:

(2n tief n) ist teilbar durch alle Primzahlen, die zwischen n und 2n liegen. Begründung analog zum Beispiel links.

Beispiele:
(20 tief 10) = 2211⋅13⋅17⋅19
(30 tief 15) = 24⋅32⋅5⋅17⋅19⋅23⋅29

(20 tief 10)+1 = 47⋅3931 (keine Primteiler zwischen 10 und 20)
(30 tief 15)+1 = 13⋅31⋅384'907 (keine Primteiler zwischen 15 und 30)