Aufzähltechniken < Stochastik < Hochschule < Mathe < Vorhilfe
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
Es sei die k-stellige Zahl
[mm]Z(k)=N\bruch{10^k-1}{9}[/mm],
wobei N eine natürliche Zahle zwischen 2 und 9 ist.
Wie oft erscheint die 0 beim Aufschreiben aller natürlichen
Zahlen von 1 bis Z(k)?
|
|
| |
|
Hallo Danny! (So eine Begrüßungsformel kommt übrigens immer gut  )
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Es sei die k-stellige Zahl
>
> [mm]Z(k)=N\bruch{10^k-1}{9}[/mm],
>
> wobei N eine natürliche Zahle zwischen 2 und 9 ist.
> Wie oft erscheint die 0 beim Aufschreiben aller
> natürlichen
> Zahlen von 1 bis Z(k)?
Nennen wir "Anzahl der 0er beim Aufschreiben von allen natürlichen Zahlen von 1 bis Z(k)" [mm]=: C_N(k)[/mm] (N als Parameter)
Überlegen wir uns erstmal ein konkretes Beispiel, und zwar [mm]C_5(6)[/mm], wir zählen also von 1 bis [mm]Z_5(6)=555.555[/mm]. Meine "Aufzähltechnik" wäre jetzt folgende: Wir teilen die Zählung der 0er zunächst in drei Bereiche ein:
a) 1-99.999 (also von 1 bis [mm]10^{k-1}-1[/mm])
b) 100.000-499.999 (also von [mm]10^{k-1} - (N*10^{k-1}-1)[/mm])
c) 500.000-555.555 (also von [mm](N*10^{k-1}) - Z_N(k)[/mm])
In diesen Bereichen zählen wir jetzt jeweils die Nullen, und zwar Stelle für Stelle:
a) Vorkommen kann die 0 an den Stellen 1-4 (Stellen von rechts nach links gezählt). Jetzt überlegen wir, wieviele Zahlen es in diesem Bereich mit der 0 an der
- Stelle 4 gibt: Stelle 5 kann von 1-9 durchlaufen, St. 1-3 können von 0-9 durchlaufen. Es gibt also [mm]9*10*10*10=9*10^3[/mm] Zahlen im B. a) mit 0 an dieser Stelle.
- Stelle 3 gibt: Es sind [mm]9*10^3+9*10^2[/mm], weil entweder St. 5 mit 1-9 besetzt ist (dann haben St. 4,2,1 jeweils 10 Mögl.) oder St.5 frei ist (dann hat aber St.4 nur 1-9 zur Auswahl)
- Stelle 2 gibt: Es sind [mm]9*10^3+9*10^2+9*10[/mm]
- Stelle 1 gibt: Hier sind es dann [mm]9*10^3+9*10^2+9*10+9[/mm]
Is doch schon ein gewisses Muster erkennbar! Insgesamt gibt es also in diesem Bereich [mm]\summe_{i=1}^{4} i*9*10^{i-1}[/mm] Nullen.
b) Die 0 kann an den Stellen 1-5 vorkommen.
- Stelle 5: [mm]4*10^4[/mm] Zahlen mit der 0 an dieser Stelle (Stelle 6 hat 4 Möglichkeiten, die anderen alle 10) Aber auch für alle anderen 0-Stellen gilt:
- Stelle 4,3,2,1: Es gibt [mm]4*10^4[/mm] mögliche Zahlen.
Insgesamt gibt es also in diesem Bereich [mm]5*(4*10^4)[/mm] Nullen.
c) Um das Aufzählverfahren rekursiv zu machen, teilen wir die Nullen in diesem Bereich in die Nullen links von einer Ziffer verschieden von Null und den Rest (der dann gleich [mm]C_N(k-1)[/mm] ist) ein, also:
wir zählen z.B. bei der Zahl [mm]500.302[/mm] nur die zwei Nullen links von der 3, die Null an der Stelle 2 nicht - sie ist bereits in [mm]C_5(5)[/mm] mitgezählt.
Wieviele solche "Links-Nullen" gibt es hier?
-Stelle 5: [mm]10^4[/mm] Mögl., da St. 6 ja fest ist (Ziffer 5) und die St. 1-4 von 0-9 laufen können.
-Stelle 4: [mm]10^3[/mm], da St.6 und 5 (Ziffern "50") fest sind.
-St. 3+2+1: [mm]10^2+10^1+1[/mm]
Insgesamt gibt es also in diesem Bereich [mm]\summe_{i=1}^{5} 10^{i-1}[/mm] "Linksnullen" und [mm]C_5(5)[/mm] "Rechtsnullen".
Es ist also
[mm]C_5(6)=\summe_{i=1}^{4} i*9*10^{i-1}+5*(4*10^4)+\summe_{i=1}^{5} 10^{i-1} + C_5(5)[/mm]
Ausgehend von dieser Idee kannst du jetzt selber einen allgemeinen Ansatz entwickeln und hier posten.
mfg
Daniel
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:43 Fr 21.10.2005 | | Autor: | ribu |
hallo
von der idee von danieliteraktiv ( hoffe das ist richtig ) ausgehend,
würde ich das als allgemeine formel vorschlagen:
$ [mm] C_n(n+1)=\summe_{i=1}^{n-1} i\cdot{}9\cdot{}10^{i-1}+n\cdot{}((n-1)\cdot{}10^{n-1})+\summe_{i=1}^{n} 10^{i-1} [/mm] + [mm] C_n(n) [/mm] $
ich hoffe das kann man so schreiben, wenn nicht dann korrigiert meinen vorschlag doch bitte...
mfg ribu
|
|
|
| |
|
Hallo ribu,
die Formel stimmt nicht, aber bevor ich da jetzt was korrigiere, sollte Danny sich mal Gedanken dazu machen und eine Lösung vorschlagen!
(Das soll ja hier kein Lösungsbuch, sondern Hilfe zur Selbsthilfe sein)
mfg
Daniel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:03 Fr 21.10.2005 | | Autor: | Cool-Y |
ich hätte einen anderen vorschlag(läuft auf eine explizite darstellung hinaus, ich weiß nicht ob das bei der anderen lösung auch der fall wäre):
die i-te ziffer(von rechts) ist genau dann eine null, wenn die zahl ohne die ersten i-1 ziffern (wieder von rechts) durch zehn teilbar ist. die anzahl der zahlen, die kleiner sind als z(k) und bei denen dies zutrifft, ist [mm] 10^{i-1}*[z(k)/10^{i}] [/mm] (<- Gaußklammern).
Also muss man jetzt das noch für alle i zusammenzählen(es reicht bis k-1, weil die letzte ziffer(von rechts) nicht null sein darf):
[mm] \summe_{i=1}^{k-1}(10^{i-1}*[z(k)/10^{i}])
[/mm]
[mm] =\summe_{i=1}^{k-1}(n*10^{i-1}*(10^{k-i}-1)/9)
[/mm]
[mm] =\bruch{n}{9}*\summe_{i=1}^{k-1}(10^{i-1}*(10^{k-i}-1))
[/mm]
[mm] =\bruch{n((9k-10)*10^{k-1}+1)}{81}
[/mm]
ich hab die zwischenschritte jetzt weigehend weggelassen, aber das ist ja wie daniel sagt, kein lösungsbuch.
|
|
|
| |
|
Hallo Mario,
> ich hätte einen anderen vorschlag(läuft auf eine explizite
> darstellung hinaus, ich weiß nicht ob das bei der anderen
> lösung auch der fall wäre):
Irgendwann sollte sie schon darauf hinauslaufen (nach Berechnung
der ersten paar Werte für verschiedene k's, Vermutung und anschließend
vollständige Induktion nach k- dort braucht man dann auch die rekursive Darstellung!)
>
> die i-te ziffer(von rechts) ist genau dann eine null, wenn
> die zahl ohne die ersten i-1 ziffern (wieder von rechts)
> durch zehn teilbar ist. die anzahl der zahlen, die kleiner
> sind als z(k) und bei denen dies zutrifft, ist
> [mm]10^{i-1}*[z(k)/10^{i}][/mm] (<- Gaußklammern).
> Also muss man jetzt das noch für alle i zusammenzählen(es
> reicht bis k-1, weil die letzte ziffer(von rechts) nicht
> null sein darf):
soweit richtig und mir klar!
> [mm]\summe_{i=1}^{k-1}(10^{i-1}*[z(k)/10^{i}])[/mm]
> [mm]=\summe_{i=1}^{k-1}(n*10^{i-1}*(10^{k-i}-1)/9)[/mm]
Und was ist mit den Gaußklammern passiert? (außerdem ist doch [mm]\bruch{z(k)}{10^i}=n*\bruch{10^{k-i}-\red{10^{-i}}}{9}[/mm])
Entweder ich verstehe das nicht oder es ist (glaube ich) nicht so einfach, die Gaußklammern umzuformen.
mfg
Daniel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:00 Fr 21.10.2005 | | Autor: | Cool-Y |
also ich hab mir das so gedacht:
wenn man bei der zahl z(k) das komma um i stellen nach links verschiebt, bekommt man doch [mm] \bruch{z(k)}{10^{i}}. [/mm] wenn man dann die größte ganze zahl j nimmt mit j [mm] \le \bruch{z(k)}{10^{i}} [/mm] , dann ist das doch einfach z(k), ohne die letzten i ziffern(von links). und da z(k) überall die selbe ziffer, nämlich n, hat, kann man [mm] [\bruch{z(k)}{10^{i}}] [/mm] dann so ausdrücken: [mm] [\bruch{z(k)}{10^{i}}]=n*\bruch{10^{k-i}-1}{9} [/mm] (=eine zahl mit k-i mal der ziffer n).
|
|
|
| |
|
ja, jetzt verstehe ich die Idee und den Schritt 
Super Lösung!! ![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]")
Ich hab mich da wohl wirklich zu sehr in die Idee des Rekursiven verstiegen...
mfg
Daniel
|
|
|
|
