Beweis zur Quersumme: gilt (Q(n) + Q(2n)) mod 3 = 0 ?

05.01.2012, 17:45

mathemathemathe :D

Auf diesen Beitrag antworten »

Beweis zur Quersumme: gilt (Q(n) + Q(2n)) mod 3 = 0 ?

Meine Frage:
Ich versuche seit einiger Zeit die folgende Aussage zu beweisen und hätte gerne Hilfe (:

Also es gilt ja für die Teilbarkeit von Zahlen
Q(3n) mod 3 = 0 (macht ja logischerweise Sinn.)

Allerdings scheint dassselbe auch für (Q(n) + Q(2n)), also die Quersumme der Zahl n un die Quersumme des doppelten der Zahl n addiert sind durch drei restlos teilbar.

n ist natürlich eine ganze, positive Zahl.

Meine Ideen:
Ich bin schon soweit gekommen, einen Induktionsbeweis anzufangen:

für n0 = 1 gilt 1+2 = 3, 3 mod 3 = 0 ==> w.A

wenn ich also als Vorraussetzung:
(Q(n) + Q(2n)) mod 3 = 0 nehme und nun behaupte, dasselbe gilt für (Q(n+1) + Q(2n+2)) mod 3 = 0, dann lässt sich für den Fall, dass bei der Addition mit 1 bzw. 2 kein Übertrag entsteht das ganze als w.A. beweisen (da die 1 und 2 außerhalb geschrieben werden können und einfach ein +3 anhängen)...

Das Problem: Wenn ich einen Übertrag erhalte gibt es verdammt viele Fälle.

Daher ist meine Frage: Hat jemand einen Ansatz oder einen Link wo ich vielleicht weiter kommen könnte oder eine Idee für einen Beweis?
Vielleicht kennt auch jemand eine Regel oder so, aber ich hab im Internet recherchiert und bin auf nichts gestoßen...

Über Hilfe würde ich mich total freuen (:

05.01.2012, 18:15

Elvis

Auf diesen Beitrag antworten »

Tipp: $\begin{eqnarray*} n=\sum a_i10^i\Rightarrow 2n=\sum 2a_i10^i \Rightarrow Q(n)+Q(2n)\equiv \sum a_i+\sum 2a_i (mod 3) \end{eqnarray*}$

05.01.2012, 18:54

mathemathemathe :D

Auf diesen Beitrag antworten »

Alsooo so ganz hab ich das noch nicht verstanden, aber vielen danke für den Ansatz, ich schätze wenn ich das genauer anschaue dann werd ich das schon schaffen zu beweisen Big Laugh

Big Laugh

vielen, vielen dank für die schnelle antwort und die hilfe! (:

05.01.2012, 19:09

HAL 9000

Auf diesen Beitrag antworten »

Der Weg von Elvis lässt mich etwas die Stirn runzeln:

Für Dezimaldarstellung $\begin{eqnarray*} n=\sum a_i10^i \end{eqnarray*}$ ist zwar $\begin{eqnarray*} Q(n)=\sum a_i \end{eqnarray*}$ richtig, aber i.a. gilt nicht $\begin{eqnarray*} Q(2n)=\sum 2a_i \end{eqnarray*}$ , nämlich dann nicht, sobald eine oder mehrere Ziffern >5 in $\begin{eqnarray*} n \end{eqnarray*}$ enthalten sind. unglücklich

unglücklich

Nun hat Elvis dies geschickterweise nicht geschrieben bzw. genutzt, sondern "nur" $\begin{eqnarray*} Q(2n) \equiv \sum 2a_i \bmod 3 \end{eqnarray*}$ , aber dies ohne Beweis... Augenzwinkern

Augenzwinkern

Und das ist der Punkt: Am besten beweist man $\begin{eqnarray*} Q(n)\equiv n \bmod 9 \end{eqnarray*}$ für alle natürlichen Zahlen, dann gilt insbesondere auch $\begin{eqnarray*} Q(n)\equiv n \bmod 3 \end{eqnarray*}$ und man kann ganz einfach folgern

$\begin{eqnarray*} Q(n)+Q(2n) \equiv n+2n = 3n \equiv 0\bmod 3 \end{eqnarray*}$ .

05.01.2012, 20:57

mathemathemathe :D

Auf diesen Beitrag antworten »

Warum kann ich dann einfach folgern, dass das gilt?
Weil es ist ja relativ einfach diese teilbarkeitsregeln von 9 und 3 zu beweisen (findet sich im Internet u.a. ja in Unmengen), aber ich kann daraus doch nicht einfach deine letzte Folgerung ziehen...
Also Elvis' Begründung ist mir noch irgendwo eingeleuchtet, nach überlegen. Weil wenn ich
n = Summe (ai 10^i) (sorry, ich weiß nicht wie ich diese Formeln mache :s) dann kann gilt ja für 2n = 2*Summe (ai 10^i) und die zwei kann ich ja auch in die Summe schreiben (ansonsten ist sie ja nur ausgeklammert, wenn ich das richtig verstehe)...

05.01.2012, 21:10

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von mathemathemathe
Warum kann ich dann einfach folgern, dass das gilt?

Die Rechenregeln der Modulorechnung sind dir vertraut? Also dass aus $\begin{eqnarray*} a\equiv b\bmod m \end{eqnarray*}$ und $\begin{eqnarray*} c\equiv d\bmod m \end{eqnarray*}$ dann $\begin{eqnarray*} a+c\equiv b+d\bmod m \end{eqnarray*}$ folgt? Nichts anderes habe ich doch dann benutzt!

Zitat:

Original von mathemathemathe
dann kann gilt ja für 2n = 2*Summe (ai 10^i) und die zwei kann ich ja auch in die Summe schreiben

Das ist doch nicht der Punkt - hast du denn meinen Beitrag gar nicht gelesen? Es geht darum, dass $\begin{eqnarray*} 2n \end{eqnarray*}$ nicht notwendig aus den Ziffern $\begin{eqnarray*} 2a_i \end{eqnarray*}$ besteht, und dass deswegen die Quersummenformel $\begin{eqnarray*} Q(2n)=\sum 2a_i \end{eqnarray*}$ i.a. nicht gilt, jedenfalls nicht als Gleichheit.

Anzeige

05.01.2012, 21:32

mathemathemathe :D

Auf diesen Beitrag antworten »

Doch ich habe deinen Beitrag gelesen ihn aber nicht verstanden, da er in einem ziemlichen Widerspruch zu dem von Elvis', den ich ja eigentlich grade für richtig angedacht habe.

Aber vielen dank für die Erklärung, ich denke jetzt hab ich es verstanden. Und irgendwie hatte ich bezüglich dessen, dass ab 5 bei der Verdopplung die Zahl Stelle ja nicht mehr einfach verdoppelt sondern es einen Übertrag gibt, ein Brett vorm Kopf gehabt Big Laugh

Big Laugh

Also vielen danke (:

06.01.2012, 17:27

Elvis

Auf diesen Beitrag antworten »

Da ist kein Widerspruch zwischen Hal 9000 und mir, denn seit "2001 Odysee im Weltraum" wissen wir dass Hal 9000 immer recht hat, und ich habe auch recht. Big Laugh

Big Laugh

Ich habe einen Tipp gegeben, keine Komplettlösung. Insbesondere wollte ich darauf hinweisen, dass hier die Kongruenzrechnung hilft, wohingegen die vollständige Induktion Probleme macht.
Daran stimmt alles, und man muss sich immer überlegen, warum Implikationen richtig sind.

06.01.2012, 17:29

HAL 9000

Auf diesen Beitrag antworten »

Stimmt, deswegen hatte ich das "geschickterweise" geschrieben. Augenzwinkern

Augenzwinkern

Wenn man aber sowieso noch diese Kongruenz beweisen muss, dann kann man auch gleich über $\begin{eqnarray*} Q(n)\equiv n\bmod 9 \end{eqnarray*}$ gehen - das war der Punkt, weswegen ich hier überhaupt interveniert hatte.

07.01.2012, 10:22

mathemathemathe :D

Auf diesen Beitrag antworten »

Ich bin mit mod noch nicht so erfahren, hab aber einen Beweis für deine Formel gefunden Big Laugh

Big Laugh

ich hab nur eine frage: für eine Zahl die durch 9 teilbar ist ergibt doch n mod 9 immer 0. 0 als Quersumme existiert ja nun aber nicht. kann ich dann einfach festlegen, dass der Rest in so einem Fall 9 ist - dann haut die Regel auch hin - ansonsten wäre das ja eigentlich ein Widerspruch.

Nochmals vielen dank für die Hilfe!

07.01.2012, 11:24

Elvis

Auf diesen Beitrag antworten »

Ich glaube, ich habe hier noch einen viel einfacheren Beweis erstellt, und ich brauche nur $\begin{eqnarray*} m\equiv Q(m) (mod 3) \end{eqnarray*}$ - was wir schon aus der Schule wissen.

$\begin{eqnarray*} n\equiv Q(n), 2n\equiv Q(2n) (mod 3)\Rightarrow Q(n)+Q(2n)\equiv n+2n=3n\equiv 0 (mod 3) \end{eqnarray*}$

... das ist ja der Hammer ! Das hat Hal 9000 gemacht ! Klasse !

07.01.2012, 17:33

mathemathemathe :D

Auf diesen Beitrag antworten »

Ja, der Beweis macht sinn und ist ziemlich clever.

Eben nur der eine Punkt, dass m mod 3= Q(m) für eine Zahl m die durch 3 teilbar ist ja eigentlich ein Widerspruch ergibt ==> m mod 3 wäre 0 und eine Quersumme kann ja nicht 0 ergeben.

07.01.2012, 17:37

Elvis

Auf diesen Beitrag antworten »

Nein, bei solchen Kongruenzen geht es um etwas ganz anderes. Eine Zahl ist durch 3 teilbar (d.h. lässt bei Division durch 3 den Rest 0) genau dann wenn ihre Quersumme durch 3 teilbar ist (d.h. diese lässt bei Division durch 3 den Rest 0).

07.01.2012, 17:42

HAL 9000

Auf diesen Beitrag antworten »

@mathemathemathe

Die Aussage lautet NICHT $\begin{eqnarray*} Q(m) = m\bmod 3 \end{eqnarray*}$ , sondern $\begin{eqnarray*} Q(m)\equiv m\bmod 3 \end{eqnarray*}$ . Anscheinend verwechselst du die Modulo-Kongruenz (so war es hier gemeint) mit dem Modulo-Operator im Bereich der ganzen Zahlen (so hast du es aufgefasst). unglücklich

unglücklich

07.01.2012, 18:03

mathemathemathe :D

Auf diesen Beitrag antworten »

wir hatten modulo noch nicht im unterricht, dementsprechend hab ich davon nocht so viel ahnung (sonst hätte ich ja schon gesagt, danke alles verstanden tschüss...)

aber dann schau ich mir mal die modulo kongruenz an, ich denk mal, wenn ich verstehe, dann ist mir das klar.

thx.

25.02.2012, 11:09

Collatz-Problem

Auf diesen Beitrag antworten »

Alles viel zu kompliziert!
Wir wissen doch, dass Q(n) mod 3 = n mod 3.

Also können wir schreiben:

(Q(n) + Q(2n)) mod 3 = 0
<==>
(Q(n) mod 3 + Q(2n) mod 3) mod 3 = 0
<==>
(n mod 3 + 2n mod 3) mod 3 = 0
<==>
(n + 2n) mod 3 = 0
<==>
(3n) mod 3 = 0

wahre Aussage, gilt also auch für ganz oben.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »