| Autor |
Beitrag |
    
Magie
| | Veröffentlicht am Mittwoch, den 04. Oktober, 2000 - 18:34: | 
|
Hi ihr da, ich nehme zur Zeit an einer Mathe-Olympiade teil. Ich habe auch schon alles beantwortet, nur an der Aufgabe stimmt es Hinten und Vorn nicht.
Aufgabe der 40. Mathe-Olympiade
400814:
a)Sven hat ein schlechtes Gedächtnis und kennt die Folge der Primzahlen nur bis zur 31 auswendig. Er soll die Zahl 813841 in Primfaktoren zerlegen. Dazu steht ihm zwar ein Taschenrechner, aber keine Primzahltafel zur Verfügung.
Wie kann er die Aufgabe lösen?
b)Sven hat am Lösen solcher Aufgaben Spaß gefunden. Er zerlegt die 813813, die 841841 und weitere sechsstellige Zahlen des Types abcabc in Primfaktoren. Dabei kommt er zu einer Vermutung über Primzahlen, die Teiler von Zahlen dieses Typs sind.
Formuliere eine solche Vermutng!
c)Versuche, deine Vermutung zu beweisen!
d)Untersuch entsprechende Primzahl-Aussagen zu anderen speziellen Typen sechstelliger Zahlen etwa Zahlen des Typs abcba, ababab oder abbabb!
Hinweis: Die Schreibweise abcdef bezeichnet hier die Zahl, die mit den Ziffern a, b, c, d, e, f, in dieser Reihenfolge geschrieben wird. |
Matroid (Matroid)
| | Veröffentlicht am Donnerstag, den 05. Oktober, 2000 - 22:05: |
|
Hallo Magie,
eine Primzahl ist nur durch 1 und sich selbst teilbar (und die kleinste Primzahl ist die 2).
Eine Zahl ist also keine Primzahl, wenn es Zahlen p und q gibt, mit x = p * q. Eine von den beiden Zahlen p und q ist die kleiner von den beiden. Sagen wir mal, die kleinere ist p.
Wenn x keine Primzahl ist, dann können p und q sogar so wählen, daß p der kleinste Primfaktor ist, der x teilt.
Wie groß ist diese kleiner Zahl höchstens? Höchstens Wurzel(x), denn wenn es
einen Zahl r größer als Wurzel(x) gäbe, die ein Teiler von x ist, und die der kleinere der beiden Teiler wäre, dann wäre r also größer als Wurzel x (selbstredend) und r * wurzel(x) > x, aber dann ist r nicht der kleinere der beiden Teiler. Ein Widerspruch.
Was hat man davon? Wenn eine Zahl auf Primzahleigenschaft untersucht werden soll, dann genügt es alle natürlichen Zahlen <= Wurzel(x) zu prüfen, ob sie die Zahl x teilen. Wenn davon keine ein Teiler von x ist, dann ist x eine Primzahl.
Und man muß auch nicht alle Zahlen kleiner Wurzel(x) als möglichen Teiler untersuchen, es reicht natürlich die Primzahlen darunter zu nehmen. Ansonsten gäbe es ja durch anderes Zusammenfassen von Primfaktoren eine andere Möglichkeit für x = p*q, mit einem noch kleineren p - und es war ja angenommen, daß p der kleinste Wert sein sollte.
Nun ein Beispiel:
x= 989. Wurzel(x) = 31,44...
Primzahlen <= 31 sind:
2,3,5,7,11,13,17,19,23,29,31
Man kann nun alles rechnen. Man kann aber auch erst noch ein paar offensichtliche Nicht-Teiler streichen: die 2 und die 3 und die 5.
Wenn einer der Quotienten ganzzahlig ist, dann ist 989 eben keine Primzahl.
Nun 989/7 ist nicht ganzzahlig.
Und 989 durch 11, 13, 17, 19 auch nicht.
Aber 989 / 23 = 43.
Ergebnis 989 ist keine Primzahl.
Und schließlich noch: Man muß eigentlich auch nicht Wurzel(x) berechnen. Vielleicht hat man ja keinen Taschenrechner zur Hand und muß sich auf schriftliches Teilen verlegen.
Dann teilt man eben der Reihe nach die Zahl x durch 7, 11, 13, ....
Und wenn der Quotient anfängt kleiner zu werden als die Zahl, durch die man teilt, dann ist man über Wurzel(x) hinaus und man darf aufhören.
Weiteres Beispiel:
x=907
Primfaktoren 2, 3 und 5 fallen quasi von selbst weg.
907 : 7 = 129,5...
907 : 11 = 82,4...
907 : 13 = 69,7...
907 : 17 = 53,3...
907 : 19 = 47,7...
907 : 23 = 39,4...
907 : 29 = 31,2...
907 : 31 = 29,2...
UND STOP, denn 29,2 ist kleiner als 31, wir sind also über Wurzel(x) hinaus.
Soweit mein Beitrag, vielleicht ist eine Idee für den Rest enthalten. Nutzt ja keinem, wenn er an einer Mathe-Olymiade teilnimmt und nicht selbst auf die Lösung gekommen ist.
Viele Grüße
Matroid |
Olymp. Komitee
| | Veröffentlicht am Dienstag, den 10. Oktober, 2000 - 21:22: |
|
Hallo zukünftige Olympioniken! Jetzt wirds aber Zeit, unter Beweis zu stellen, dass die Lösung ohne weitere fremde Hilfe gefunden wurde, sonst ist sowieso in der ersten Runde schon Schluss.
Wie lautet denn jetzt die Lösung für c), Magie?
Tipp: Du musst nur b) konsequent so befolgen, wie Matroid es an dem anderen Beispiel vorgemacht hat. |
|
