| Autor |
Beitrag |
    
Basicuser1 (Basicuser1)
Neues Mitglied
Benutzername: Basicuser1
Nummer des Beitrags: 4
Registriert: 06-2004
| | Veröffentlicht am Freitag, den 09. Juli, 2004 - 19:49: | 
|
Hallo! Wer kann mir bei folgender Aufgabe weiterhelfen?
Auf einem Brett befinden sich 1000 Lämpchen, die von 1 bis 1000 durchnummeriert sind. Zunächst sind alle aus. Dann werden alle, deren Nummer durch 1 teilbar ist (also alle) angeschaltet. Beim 2. Schritt werden alle, deren Nummer durch 2 teilbar ist, ausgeschaltet. Allgemein: Beim k-ten Schritt wird jedes Lämpchen, dessen Nummer durch k teilbar ist umgeschaltet von an nach aus oder von aus nach an, je nachdem, ob es gerade brennt oder nicht.
Frage: Welche Lämpchen brennen nach 1000 solchen Schritten?
|
Thjalfi (Thjalfi)
Mitglied
Benutzername: Thjalfi
Nummer des Beitrags: 33
Registriert: 01-2001
| | Veröffentlicht am Freitag, den 09. Juli, 2004 - 20:10: |
|
also ich würde mir das so denken:
eine zahl ist ja nicht durch eine größere zahl ohne rest teilbar, also spielt es nur eine rolle, ob k> der fraglichen zahl, bzw. der nummer des lämpchens ist.
jetzt zerlegt man einfach jede nummer in ihre primfaktoren und die anzahl der primfaktoren gibt die anzahl der umschaltvorgänge. tada ;-)
Wer andere Menschen besiegt,
hat Gewalt;
Wer sich selbst besiegt,
der ist stark.
|
Martin243 (Martin243)
Senior Mitglied
Benutzername: Martin243
Nummer des Beitrags: 995
Registriert: 02-2001
| | Veröffentlicht am Freitag, den 09. Juli, 2004 - 20:30: |
|
Hi!
Es geht auch etwas einfacher!
Wir überlegen uns einfach, dass eine Zahl genau dann eine Quadratzahl ist, wenn sie eine ungerade Anzahl von Teilern besitzt.
Wir klappern nun alle möglichen Teiler von 1 bis 1000 ab und es leuchten am Ende nur die Lämpchen, die eben eine ungerade Anzahl von Teilern hatten, also die Quadratzahlen 1, 4, 9, 16, 25, 36, ..., 900, 961
Am Beispiel:
Lämpchen 340, keine Quadratzahl:
1-an, 2-aus, 4-an, 5-aus, 10-an, 17-aus, 20-an, 34-aus, 68-an, 85-aus, 170-an, 340-aus
Lämpchen 441, Quadratzahl:
1-an, 3-aus, 7-an, 9-aus, 21-an, 49-aus, 63-an, 147-aus, 441-an
Am Ende leuchten also die besagten 31 Quadratzahlen bis 1000.
MfG
Martin
Die Natur spricht die Sprache der Mathematik:
Die Buchstaben dieser Sprache sind Dreiecke, Kreise und andere mathematische Figuren.
Galileo Galilei
|
Thjalfi (Thjalfi)
Mitglied
Benutzername: Thjalfi
Nummer des Beitrags: 34
Registriert: 01-2001
| | Veröffentlicht am Samstag, den 10. Juli, 2004 - 09:52: |
|
sehr schön, und was hast du da gemacht?
genau, du hast die zahlen in ihre primfaktoren zerlegt.
aber beweise doch mal bitte, dass zahlen mit ganzzahliger wurzel immer eine ungerade anzahl von primteilern haben.
Wer andere Menschen besiegt,
hat Gewalt;
Wer sich selbst besiegt,
der ist stark.
|
Jair_ohmsford (Jair_ohmsford)
Senior Mitglied
Benutzername: Jair_ohmsford
Nummer des Beitrags: 734
Registriert: 10-2003
| | Veröffentlicht am Samstag, den 10. Juli, 2004 - 10:09: |
|
Hallo allerseits,
zunächst mal geht es ja gar nicht um die Anzahl von Primteilern, sondern um die Anzahl der Teiler. Diese Zahl muss ungerade sein. (Z.B. hat 30 eine ungerade Anzahl von Primteilern: 2,3 und 5. Lampe 30 erfüllt aber sicher nicht die Bedingung, am Ende der Schaltvorgänge eingeschaltet zu sein.)
Der Nachweis, dass eine Zahl mit geradzahliger Wurzel immer eine ungerade Anzahl von Teilern hat, ist nun aber so einfach, dass selbst ein Fünftklässler ihn schafft:
Ist t ein Teiler einer Zahl z aus N, so gibt es nach Definition ein x aus N, so dass
z = t*x
t und x sind genau dann gleich, wenn t die Wurzel aus z darstellt, in allen anderen Fällen also verschieden.
Ist z also keine Quadratzahl, so finden wir zu den n Teilern t mit t*t<z genau n Teiler x mit x*x>z und t*x=z. Das sind 2n Teiler, also eine gerade Anzahl.
Ist z dagegen eine Quadratzahl, dann findet man außer den 2n Teilern wie oben auch noch den einen Teiler w, für den gilt
w*w=z.
Das war's.
Viele Grüße
Jair
PS: Die entsprechende Aussage über die Primteiler ist übrigens falsch. Denk z.B. mal an 36 = 2*2*3*3. Das ist eine gerade Anzahl von Primteilern (2 verschiedene, 4 insgesamt)
|
Martin243 (Martin243)
Senior Mitglied
Benutzername: Martin243
Nummer des Beitrags: 996
Registriert: 02-2001
| | Veröffentlicht am Montag, den 12. Juli, 2004 - 09:22: |
|
Danke Jair!
Ich war übers Wochenende weg und konnte deshalb nichts mehr erklären. Über die Geschichte mit den Primteilern habe ich gar nicht erst nachgedacht, weil mir meine Lösung viel einfacher erschien.
@Thjalfi:
Dieses "sehr schön" war also gar nicht nötig. Ich weiß, was ich tu (meistens jedenfalls)...
MfG
Martin
(Beitrag nachträglich am 12., Juli. 2004 von +Martin243 editiert)
Die Natur spricht die Sprache der Mathematik:
Die Buchstaben dieser Sprache sind Dreiecke, Kreise und andere mathematische Figuren.
Galileo Galilei
|
|
