1-stellige Quersumme berechnen < Klassen 5-7 < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:28 Sa 25.08.2018 | | Autor: | donp |
| Aufgabe | Für $n [mm] \in \IN^{+}$ [/mm] sei $q(n)$ die 1-stellige Quersumme von n zur Basis b.
Beweisen Sie:
[mm] $$q(n)=\begin{cases} b-1, & \mbox{für } n \equiv 0 \;(mod\; (b-1)) \\ n \;mod\; (b-1), & \mbox{sonst} \end{cases}$$ [/mm] |
Hintergrund:
Es sollen z.B. 9 auf einem geschlossenen Band angeornete Elemente schrittweise vor einem Fenster vorbeiziehen, wobei immer nur eines im Fenster sichtbar ist. Bei n Schritten interessiert nur, welches Element schließlich im Fenster erscheint. Für große n ist es nicht effizient, alle Schritte tatsächlich auszuführen. Für z.B. n=9 muss gar kein Schritt ausgeführt werden, oder eben 9 Schritte.
Anscheinend entspricht die Anzahl auszuführender Schritte der 1-stelligen Quersumme von n, z.B. im Dezimalsystem für $n=12345 [mm] \Rightarrow [/mm] q(12345)=q(15)=q(1+5)=6$. Nun würde ich das gerne auch richtig beweisen.
Es ist klar, dass $$1 [mm] \,\le\, [/mm] q(n) [mm] \,<\, [/mm] b$$ gilt, im Dezimalsystem mit [m]b=10[/m] z.B. ist [m]q(n)[/m] eine der Zahlen $1 [mm] \dots [/mm] 9$.
Mir ist intuitiv auch klar, dass b-1 bzgl. der 1-stelligen Quersumme sozusagen das neutrale Element der Addition ist, weil im Dezimalsystem z.b [m]q(27)=q(18+9)=q(18-9)=9[/m] gilt.
Aber wie zeigt man das am besten?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Danke und Gruß,
Don P
|
|
| |
|
Vielleicht hilft dieser Tipp ( dabei steht [mm] \equiv [/mm] für ... ist gleich ... mod (b-1)):
Für k [mm] \ge [/mm] 1 gilt:
[mm] a*b^k \equiv a*b^k [/mm] - [mm] a*b^{k-1}+a*b^{k-1} \equiv (b-1)a*b^{k-1}+a*b^{k-1} \equiv a*b^{k-1} [/mm] und somit
[mm] a*b^k \equiv a*b^{k-1} \equiv a*b^{k-2} \eqiv [/mm] ... [mm] \equiv a*b^0 [/mm] = a
Falls du damit nicht klar kommst, melde dich noch mal.
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 19:09 Di 28.08.2018 | | Autor: | donp |
> Für k [mm]\ge[/mm] 1 gilt:
>
> [mm]a*b^k \;\equiv\; a*b^k[/mm] - [mm]a*b^{k-1}+a*b^{k-1}[/mm]
Gut, beide Seiten sind gleich und somit kongruent bzgl. jedes Moduls [mm]m[/mm].
Und wegen [m](a*b^k - a*b^{k-1})=b*(a*b^{k-1})-1*(a*b^{k-1})= (b-1)*a*b^{k-1}[/m] sind wieder beide Seiten gleich und daher kongruent:
[mm] $$a*b^k \equiv (b-1)*a*b^{k-1}+a*b^{k-1}$$ [/mm] Den nächsten Schritt zu [mm] $$(b-1)*a*b^{k-1}+a*b^{k-1}\equiv a*b^{k-1}$$ [/mm] verstehe ich aber nicht auf Anhieb inzwischen auch ![[lichtaufgegangen]](/images/smileys/lichtaufgegangen.gif "[lichtaufgegangen]") :
Setzen wir $$l = [mm] a*b^{k-1}$$ [/mm] $$m=(b-1)$$ dann hat [m]a*b^{k-1} + (b-1)*a*b^{k-1}[/m] die Form [m]l + m*l[/m], was die Kongruenz von [m]l[/m] bzgl. des Moduls [m]m[/m] zeigt.
Der Rest wäre dann auch klar:
> und somit [mm]a*b^k \equiv a*b^{k-1} \equiv a*b^{k-2} \eqiv \dots \equiv a*b^0 = a[/mm]
Somit hat sich diese Frage erledigt. Anscheinend kann ich sie nicht selber auf beantwortet setzen ![[keineahnung]](/images/smileys/keineahnung.gif "[keineahnung]") .
Vielen Dank für den Tipp,
Don P
Mein ursprünglicher Beweis geht so:
Es seien [mm](a,b,n) \in \IN_{+}^3[/mm] und [m]Q(n)[/m] die normale Quersumme von [m]n[/m] zur Basis [m]b[/m].
Mit [m]m=b-1[/m] sind die Zahlen $a [mm] \in \{1...m\}$ [/mm] Repräsentanten der Restklassen $a + m [mm] \mathbb{N}$ [/mm] (Äquivalenzklassen von a bezüglich der Kongruenz modulo m).
Definition der Restklasse $a + m [mm] \mathbb{Z}$ [/mm] nach Wikipedia: Sie besteht aus allen ganzen Zahlen c, die sich aus a durch die Addition ganzzahliger Vielfacher von m ergeben:
$$a + m [mm] \mathbb{Z} [/mm] = [mm] \{ c\mid c=a+km\ \, \mathrm{f\ddot ur\ ein}\ \, k\in\mathbb Z\} [/mm] = [mm] \{ c \mid c \equiv a \; ({\rm mod} \; m) \}$$ [/mm] Als Definition muss die Aussage wohl nicht extra bewiesen werden.
Denkt man sich die Repräsentanten $a [mm] \in \{1...m\}$ [/mm] kreisförmig angeordnet und den ganzen Zahlenstrang [mm] \IN^{+} [/mm] entsprechend spiralförmig, dann liegen konkruente Zahlen [m]\{ c \mid c \equiv_{m} a\}[/m] immer an Position [m]a[/m] im Kreis, für [m]m=9[/m] z.B. $$c=1 = 1 + 0*m [mm] \mbox [/mm] { an Position } a=1=Q(1) [mm] \;\dots$$ [/mm] $$c=9 = 9+0*m [mm] \mbox [/mm] { an Position } a=9=Q(9) [mm] \;\dots$$ [/mm] $$c=10 = 1+1*m [mm] \mbox [/mm] { an Position } a=1=Q(10) [mm] \;\dots$$ [/mm] $$c=18=9+1*m [mm] \mbox [/mm] { an Position } [mm] a=9=Q(18)\;\dots$$ [/mm] $$c=19=1+2*m [mm] \mbox [/mm] { an Position } a=1=Q(10)=Q(Q(19))$$ usw. Hier haben wir genau die für die Definition der Restklassen [m]a + m \mathbb{N}[/m] benutzte Addition ganzzahliger Vielfacher von [m]m[/m].
Aus dieser Anschauung ergibt sich $$n [mm] \equiv_{m} [/mm] a [mm] \equiv_{m} [/mm] Q(n) [mm] \Rightarrow [/mm] a [mm] \equiv_{m} [/mm] Q(Q(n)) [mm] \equiv_{m} [/mm] Q(Q(Q(n))) [mm] \;\dots \;\equiv_{m} [/mm] q(n)$$ und wegen [mm]1\le q(n)\le m[/mm] folgt für die 1-stellige Quersumme $$q(n) = a$$ w.z.b.w.
Das scheint mir zwar logisch, aber weil ich die ungewöhnliche Vorstellung des Zahlenstrangs als Spirale mit Umfang [m]m[/m] benötige, ist der Beweis wohl umständlich und nicht besonders mathematisch geführt. Das müsste doch besser gehen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:18 Mi 29.08.2018 | | Autor: | donp |
Leider Kann ich meine Frage hier nicht selber beantworten. Sie hat sich aber geklärt:
> Den nächsten Schritt zu [mm](b-1)*a*b^{k-1}+a*b^{k-1}\equiv a*b^{k-1}[/mm] verstehe ich aber nicht auf Anhieb.
Inzwischen schon :
Setzen wir $$l = [mm] a*b^{k-1}$$ [/mm] $$m=(b-1)$$ dann hat [m]a*b^{k-1} + (b-1)*a*b^{k-1}[/m] die Form [m]l + m*l[/m], was die Kongruenz von [m]l[/m] bzgl. des Moduls [m]m[/m] zeigt.
Denn die Definition der Restklasse [m]a + m \mathbb{Z}[/m] ist ja: $$a + m [mm] \mathbb{Z} [/mm] = [mm] \{ c\mid c=a+km\ \, \mathrm{f\ddot ur\ ein}\ \, k\in\mathbb Z\} [/mm] = [mm] \{ c \mid c \equiv a \; ({\rm mod} \; m) \}$$
[/mm]
Vielen Dank für den Tipp,
Don P
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:09 Do 30.08.2018 | | Autor: | donp |
| Aufgabe | Für $n [mm] \in \IN^{+}$ [/mm] sei $q(n)$ die 1-stellige Quersumme von n zur Basis b.
Beweisen Sie:
[mm] $$q(n)=\begin{cases} b-1, & \mbox{für } n \equiv 0 \;(mod\; (b-1)) \\ n \;mod\; (b-1), & \mbox{sonst} \end{cases}$$ [/mm] |
Im Folgenden sei der Modul [m]m=b-1[/m] und [m]k \in \IN[/m].
Für eine natürliche Zahl [m]n[/m], dargestellt durch Ziffern in der Form [m]\mathbf{a}_k \ldots \mathbf{a}_2 \mathbf{a}_1 \mathbf{a}_0[/m], ist die Quersumme die Summe der Ziffernwerte [m]\mathbf{a}_i[/m] $$Q(n) = [mm] \sum_{i=0}^k a_i [/mm] = [mm] a_0 [/mm] + [mm] a_1 [/mm] + [mm] a_2 [/mm] + [mm] \dotsb [/mm] + [mm] a_k$$ [/mm] und es gilt [mm] $$n=\sum_{i=0}^k a_i \cdot b^i [/mm] = [mm] a_0 \cdot b^0 [/mm] + [mm] a_1 \cdot b^1 [/mm] + [mm] a_2 \cdot b^2 [/mm] + [mm] \dotsb [/mm] + [mm] a_k \cdot b^k$$ [/mm] Nach den Rechenregeln für Konguenzen gilt [mm] $$\text{(1)}\ [/mm] \ [mm] (a_1+a_2) \equiv_m (a_1\ [/mm] {mod}\ [mm] m+a_2\ [/mm] {mod}\ m)$$ und der Tipp von HJKweseleit zeigt [mm] $$\text{(2)}\ [/mm] \ a [mm] \equiv_m a*b^k$$ [/mm] Aus (1) und (2) folgt $$n [mm] \equiv_m [/mm] Q(n)$$ Falls [m]Q(n)[/m] mehr als eine Ziffer hat, gilt entsprechend [m]n \equiv_m Q(Q(n))[/m] usw. und für die 1-stellige Quersumme [m]Q_1(n)[/m] somit ebenfalls $$n [mm] \equiv_m Q_1(n)$$ [/mm] Für [m]n>0[/m] ist [m]1\le \,Q_1(n)\,\le m[/m] und mit [m]Q_1(n) \equiv_m 0 \equiv_m m[/m] ist [m]Z = \{1,2,\dots,m\}[/m] dann die Zielmenge. Daraus folgt für die 1-stellige Quersumme
[mm] $$q(n)=\begin{cases} m, & \mbox{für } n \equiv 0 \;(mod\; m) \\ n \;mod\; m, & \mbox{sonst} \end{cases}$$ [/mm] w.z.b.w.
Die Rechenregel (1) habe ich nicht bewiesen, was man streng genommen auch noch tun müsste.
Bin mir zwar ziemlich sicher, dass es so stimmt, würde mich trotzdem freuen, wenn es mir ein Mathematiker noch kurz bestätigen könnte.
Danke und Gruß,
Don P
|
|
|
| |
|
Ja, das ist so richtig und auch sehr schön, kompakt und verständlich zusammengestellt.
|
|
|
|
