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.

 
 
 
 
 

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.

 
 
 
 
  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) 24 Nullen. [Wieviele Faktoren 2 und 5 enthält die Zahl 100! ? Man beachte die Zahlen, die durch 5, jedoch nicht durch 25 teilbar sind separat von den Zahlen, die durch 25 teilbar sind. Wieviele Faktoren 10 kann man somit herstellen?]

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 (u, v, w sind die baryzentrischen Koordinaten von P).
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 (s.Skizze):

imo86.2

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.
Es genügt zu zeigen, dass es ein n gibt, sodass 7n eine reine Zehnerpotenz 10k nur um "sehr wenig" *) überschreitet (im Fall m = 4  z.B. um weniger als 0.00001⋅10k). Das bedeutet im Fall m = 4:

0 < 7n - 10k  ≤ 0.00001⋅ 10k  

10k  < 7n ≤ 1.00001⋅ 10k  

k < n lg(7) ≤ k + lg(1.00001)

0 < n lg(7) - k ≤ lg(1.00001)

Die Siebnerpotenzen entstehen auf den Zahlenstrahl, indem wir bei 1 starten und fortlaufend mit 7 multiplizieren. Wir betrachten anstelle des gewöhnlichen Zahlenstrahls den mit dem Zehnerlogarithmus lg(x) logarithmierten Zahlenstrahl.
Wir starten bei lg(1)=0, und anstelle der Multiplikation mit 7 tritt nun die Addition von lg(7). Den Zehnerpotenzen auf dem alten Zahlenstrahl entsprechen nun die natürlichen Zahlen 1, 2, 3, ... auf dem logarithmierten Zahlenstrahl. Wir versuchen also, startend bei 0, durch fortlaufendes Addieren von lg(7) eine natürliche Zahl um nur ganz wenig zu übertreffen.

Wir können die Sache noch weiter vereinfachen, indem wir das Stück [0, 1] des neuen Zahlenstrahls zu einem Kreis mit Umfang 1 schliessen:

1976_3

 

Ausgehend vom roten Punkt addieren wir (im Gegenuhrzeigersinn) fortlaufend lg(7) auf der Kreisperipherie.

Jedesmal, wenn wir wieder beim roten Punkt vorbeikommen, zählt uns ein "Zähler" eine Runde k dazu. 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 homogen über die Kreislinie verteilt, dass also nicht etwa eine 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, der ein beliebig kurzes Kreisbogenstück oberhalb des roten Punktes liegt.

Damit ist die Sache bewiesen.

 

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 allenfalls eine Lösung, die sogar konkrete Zahlen liefert? Vielleicht findet jemand einen solchen konstruktiven Beweis oder einen Algorithmus.

 

 

*) "Sehr wenig" ist ziemlich euphemistisch gesprochen. Immerhin übertrifft im Beispiel unten 7510 die Zahl 10431 um ca. 9⋅10424, also um eine unvorstellbar riesige Zahl. Mit "sehr wenig" ist der relative Fehler gemeint, im Beispiel also der Fehler gemessen an 10431. Dieser liegt in unserem Beispiel in der Grössenordnung von 10-6.

 

**) Nicht nur der rote Punkt ist "Sprinklerquelle". Der beschriebene "Punkteregen-Vorgang" startet bei jedem frisch entstandenen Punkt wieder neu.

 
 
 
 
 

Obiger Beweis ist "allgemein", d.h. er wird für beliebige Anzahlen m hintereinander auftretender Nullen gleich geführt.

Das Durchprobieren von n⋅ lg(7) mittels eines Computerprogramms zeigt, dass für n = 510 der Wert 431.0000004... entsteht. Wir betrachten somit 7510. Rechts das Resultat mit seinen 432 Ziffern. Man sieht, dass sogar 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, nicht-konstruktive 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