Aufgabe #45 (ZT) < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 15:25 Do 19.05.2005 | | Autor: | Hanno |
Hallo an alle!
Man zeige: unter zehn aufeinanderfolgenden, natürlichen Zahlen gibt es immer wenigstens eine, die zu den übrigen 9 Zahlen relativ prim ist.
Liebe Grüße,
Hanno
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:25 Sa 21.05.2005 | | Autor: | moudi |
Hallo Hanno
Im Journal "Elemente der Mathematik Vol. 56 (2001)" wird auf Seite 173 folgende Frage gestellt:
"Wir betrachten Folgen von $k\ (>2)$ aufeinanderfolgenden Zahlen:
[mm] $n,n+1,\dots, [/mm] n+k-2,n+k-1$.
In den meisten derartigen Folgen gibt es mindestens eine Zahl, die zu allen anderen Zahlen der Folge teilerfremd ist. Man finde die kleinste Folge [...], in der es keine Zahl gibt, die zu allen anderen Zahlen der Folge teilerfremd ist."
Diese Aufgabe ist ein bisschen schwieriger, aber wenn du die Herausforderung liebst. Die Lösung findet sich dann in Vol. 57 (2002).
mfG Moudi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:54 So 22.05.2005 | | Autor: | jbulling |
Es müsste eine Folge mit 12 Zahlen geben.
Von 12 sind 6 Zahlen ungerade.
Davon sind maximal teilbar
durch 3 => 4 Zahlen
durch 5 => 3 Zahlen
durch 7 => 2 Zahlen
durch 11 => 2 Zahlen
Für die erste ungerade Zahl [mm] z_1 [/mm] der Folge muss gelten, dass sie durch 5 teilbar ist, da es sonst keine zweite ungerade Zahl in der Folge geben kann, die durch 5 aber nicht durch 3,7,11 teilbar ist.
also
[mm] z_1 \equiv [/mm] 0 (mod 5)
[mm] z_1 \equiv x_1 [/mm] (mod 3) mit [mm] x_1 \in [/mm] {1,2}
[mm] z_1 \equiv x_2 [/mm] (mod 7) mit [mm] x_2 \in [/mm] {1,2,3,4,5,6}
[mm] z_1 \equiv x_3 [/mm] (mod 11) mit [mm] x_3 \in [/mm] {1,2,3,4,5,6,7,8,9,10}
Falls es eine minimale Zahlenfolge mit 12 Zahlen länge gibt, dann müssten in den 12 aufeinanderfolgenden Zahlen aber jeweils zwei enthalten sein, die durch 11 bzw 7 teilbar sind. Falls das nicht der Fall istt, dann habe ndie Zahlen nämlich keinen gemeinsamen Teiler, denn bei der so konstruierten Zahlenfolge darf keine der ungeraden Zahlen durch mehr als einen der Primfaktoren 3,5,7,11 teilbar sein.
Damit gilt zusätzlich
[mm] z_1 \equiv [/mm] 1 (mod 11) (sonst kommt 11 nicht zweimal in der Zahlenfolge vor)
daraus folgt wiederum :
[mm] z_1 \equiv [/mm] 2 (mod 3) (bei 1 würde es eine Überschneidung mit 11 geben)
[mm] z_1 \equiv x_2 [/mm] (mod 7) mit [mm] x_2 \in [/mm] {1,2,5,6} (bei 4 würde es eine Überschneidung mit 11 geben, bei 3 mit 3 bei 2 mit 5)
[mm] z_1 \equiv [/mm] 1 (mod 11)
ok weiter komme ich im Moment nicht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:15 So 22.05.2005 | | Autor: | jbulling |
Hallo Hanno,
hier mal Ansätze zu einem Beweis. Sorry wenn das ein bischen improvisiert ist.
Relativ prim können zwei der 10 Zahlen nur sein, wenn sie keine gemeinsamen Teiler ausser 1 besitzen. Alle geraden Zahlen scheiden aus, denn es gibt in einer Folge von 10 Zahlen fünf gerade Zahlen, die alle den Faktor zwei enthalten.
Man kann sich also auf die fünf ungeraden Zahlen beschränken.
Sei M die Menge der ungeraden Zahlen in der Folge.
Angeommen es gibt für jedes a [mm] \in [/mm] M ein b [mm] \in [/mm] M mit a [mm] \not= [/mm] b mit ggT(a,b)>1 (so dass die Zahl nicht relativ prim zu allen anderen Zahlen ist), dann gibt es für jede der fünf Zahlen einen Teiler, der kleiner ist als 10. Denn wenn es keinen solchen Teiler gibt, dann gibt es keine zweite Zahl in der Folge, die genau den selben Teiler besitzt.
Wenn also a,b [mm] \in [/mm] M sind und a [mm] \not= [/mm] b gilt und a und b haben einen gemeinsamen Teiler, dann gibt es t,c, d [mm] \in \setZ [/mm] mit t*c=a und t*d=b und wegen | a - b | < 10 muss damit t<10 gelten.
Es gilt weiter, dass jede Zahl > 1 eindeutig als das Produkt von Primzahlen geschrieben werden kann. Da der positive Teiler einer positiven ganzen Zahl stets kleineroder gleich der Zahl ist reicht es also aus nur die Primzahlen zu betrachten, die als Teiler zweier Zahlen in Betracht kommen. Das sind alle primzahlen kleiner 10. Also 2,3,5,7.
2 Scheidet bereits aus, da nur die ungeraden Zahlen betrachtet werden.
ceil(10/3) = 4 also kann 3 höchsten 4 der Zahlen in der Folge teilen (z.B. die erste die vierte, die siebte und die zehnte).
ceil(10/5) = 2 also kann 5 höchstens 2 der Zahlen teilen
ceil(10/7) = 2 also kann 7 höchstens 2 der Zahlen teilen
Von den 8 möglichen Teilern fallen aber 4 auf gerade Zahlen. Denn sei p [mm] \in [/mm] {3,5,7} und a [mm] \in \setZ [/mm] wobei a ungerade ist, dann ist p*a+p=p(a+1) gerade denn a war ungerade, damit ist a+1 gerade.
Es können also höchstens 4 der Zahlen aus M einen gemeinsamen Teiler mit mindestens einer anderen Zahl aus M haben. Damit bleibt mindestens eine Zahl übrig, die relativ prim zu den anderen Zahlen ist.
|
|
|
|
