eindeutigeDarstellung nat.Zahl < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:51 Sa 17.11.2012 | | Autor: | sissile |
| Aufgabe | Zeige: Jede natürliche Zahl n besitzt eine eindeutig bestimmte Darstellung der Form
n = [mm] a_1*1!+a_2*2!+a_3*3!+.....+a_k*k!, [/mm] mit [mm] 0<=a_i<=i.
[/mm]
Ist k die größte Zahl mit ak ungleich 0, so schreibt man [mm] n=(a_1,a_2,...,a_k).
[/mm]
Finde eine möglichst einfache Methode zur Berechnung der Ziffern [mm] a_i [/mm] |
HalliHallo
Nun ist $ [mm] a_1\cdot1!+a_2\cdot2!+a_3\cdot3!+\dots+a_k\cdot k!=1(a_1+2(a_2+3(a_3+4(a_4+\dots +(k-1)(a_{k-1}+k a_k)\dots)))) [/mm] $.
Man sieht, dass der Summand [mm] 2(a_2+3(a_3+4(a_4+\dots +(k-1)(a_{k-1}+k a_k)\dots))) [/mm] gerade ist.
Mit division sehe ich schnell:
Wenn n gerade ist muss [mm] a_1 [/mm] =0
Wenn n ungerade ist muss [mm] a_1 [/mm] =1
$ [mm] \frac{n-a_1}{2}=a_2+3(a_3+4(a_4+\dots +(k-1)(a_{k-1}+k a_k)\dots))) [/mm] $
Da wäre es dann das selbe Spiel.
Der Summand $ [mm] 3(a_3+4(a_4+\dots +(k-1)(a_{k-1}+k a_k)\dots))) [/mm] $ ist durch 3 teilbar.
Also ist [mm] a_2 [/mm] der Rest wenn ich [mm] \frac{n-a_1}{2} [/mm] durch 3 teile.
Wenn n durch 3 teilbar ist muss [mm] a_2 [/mm] =0
Wenn n nicht durch 3 teilbar ist muss [mm] a_2 [/mm] =1, 2 rauskommen
Aber so wird das nicht eindeutig.. bin verwirrt^^
|
|
| |
|
Hallo sissile,
in dieser Richtung wird das nichts. Du musst anders herum anfangen.
> Zeige: Jede natürliche Zahl n besitzt eine eindeutig
> bestimmte Darstellung der Form
>
> n = [mm]a_1*1!+a_2*2!+a_3*3!+.....+a_k*k!,[/mm] mit [mm]0<=a_i<=i.[/mm]
>
> Ist k die größte Zahl mit ak ungleich 0, so schreibt man
> [mm]n=(a_1,a_2,...,a_k).[/mm]
> Finde eine möglichst einfache Methode zur Berechnung der
> Ziffern [mm]a_i[/mm]
>
> HalliHallo
> Nun ist [mm]a_1\cdot1!+a_2\cdot2!+a_3\cdot3!+\dots+a_k\cdot k!=1(a_1+2(a_2+3(a_3+4(a_4+\dots +(k-1)(a_{k-1}+k a_k)\dots)))) [/mm].
> Man sieht, dass der Summand [mm]2(a_2+3(a_3+4(a_4+\dots +(k-1)(a_{k-1}+k a_k)\dots)))[/mm]
> gerade ist.
> Mit division sehe ich schnell:
> Wenn n gerade ist muss [mm]a_1[/mm] =0
> Wenn n ungerade ist muss [mm]a_1[/mm] =1
>
> [mm]\frac{n-a_1}{2}=a_2+3(a_3+4(a_4+\dots +(k-1)(a_{k-1}+k a_k)\dots)))[/mm]
> Da wäre es dann das selbe Spiel.
> Der Summand [mm]3(a_3+4(a_4+\dots +(k-1)(a_{k-1}+k a_k)\dots)))[/mm]
> ist durch 3 teilbar.
> Also ist [mm]a_2[/mm] der Rest wenn ich [mm]\frac{n-a_1}{2}[/mm] durch 3
> teile.
> Wenn n durch 3 teilbar ist muss [mm]a_2[/mm] =0
> Wenn n nicht durch 3 teilbar ist muss [mm]a_2[/mm] =1, 2
> rauskommen
>
> Aber so wird das nicht eindeutig.. bin verwirrt^^
Wie gesagt, falsche Richtung. Das Problem ist hier, dass [mm] (n-1)!\mod{n} [/mm] zu wenig hilfreiche Informationen bietet, denn:
Für n=4 ist [mm] 3!\equiv 2\mod{4}
[/mm]
Für alle anderen n gibt es nur zwei Möglichkeiten:
Ist n prim, so gilt [mm] (n-1)!\equiv -1\mod{n}
[/mm]
Ist n zusammengesetzt, so gilt [mm] (n-1)!\equiv 0\mod{n}
[/mm]
Und genau deswegen klappt es so nicht.
Andersherum: wir suchen erstmal k, so dass [mm] k!\le n\le(k+1)! [/mm] ist.
Setze [mm] n_1:=n.
[/mm]
Dann ist [mm] a_k=\left\lfloor\bruch{n_1}{k!}\right\rfloor
[/mm]
Setze [mm] n_2=n_1-a_k*k!
[/mm]
Weiter natürlich [mm] a_(k-i)=\left\lfloor\bruch{n_{i+1}}{(k-i)!}\right\rfloor
[/mm]
und [mm] n_{i+2}=n_{i+1}-a_{k-i}*(k-i)!
[/mm]
Das durchläufst Du für i=1 bis k-1.
Das Prinzip müsste Dir bekannt vorkommen: So berechnet man die Position einer Permutation von n Elementen in lexikalischer Anordnung der Permutationen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:36 Sa 17.11.2012 | | Autor: | sissile |
Ich versteh es nicht wieso mein Ansatz nicht passt
[mm] 1(a_1+2(a_2+3(a_3+4(a_4+\dots +(k-1)(a_{k-1}+k a_k)\dots)))) [/mm] $.
[mm] a_1 [/mm] zeigt ob n gerade und ungerade ist
[mm] a_2 [/mm] zeigt ob k=0,1,2
[mm] a_3 [/mm] zeigt ob k=0,1,2,3
..
ist.
z.B die Zahl 1 000 000
1 000 000 = 0 (mod 2)
also ist [mm] a_1 [/mm] =0
500 00 =2 (mod 3)
also [mm] a_2 [/mm] =2
166 666 =2 (mod 4)
also [mm] a_3 [/mm] = 2
... usw.
|
|
|
| |
|
Hallo nochmal,
> Ich versteh es nicht wieso mein Ansatz nicht passt
> [mm]1(a_1+2(a_2+3(a_3+4(a_4+\dots +(k-1)(a_{k-1}+k a_k)\dots))))[/mm]
> $.
> [mm]a_1[/mm] zeigt ob n gerade und ungerade ist
> [mm]a_2[/mm] zeigt ob k=0,1,2
> [mm]a_3[/mm] zeigt ob k=0,1,2,3
> ..
> ist.
Nein, es geht doch um Fakultäten. Vielleicht ist es ja auch nur blöd formuliert oder notiert.
> z.B die Zahl 1 000 000
> 1 000 000 = 0 (mod 2)
> also ist [mm]a_1[/mm] =0
> 500 00 =2 (mod 3)
> also [mm]a_2[/mm] =2
> 166 666 =2 (mod 4)
> also [mm]a_3[/mm] = 2
> ... usw.
Ja, so funktioniert es. Bisher hatte ich noch nicht verstanden, dass Du auch dividieren willst.
Machen wir mal weiter:
[mm] 41666\equiv 1\mod{5}
[/mm]
also [mm] a_4=1
[/mm]
[mm] 8333\equiv 5\mod{6}
[/mm]
also [mm] a_5=5
[/mm]
[mm] 1388\equiv 2\mod{7}
[/mm]
also [mm] a_6=2
[/mm]
[mm] 198\equiv 6\mod{8}
[/mm]
also [mm] a_7=6
[/mm]
[mm] 24\equiv 6\mod{9}
[/mm]
also [mm] a_8=6
[/mm]
schließlich noch [mm] 2\equiv 2\mod{10}
[/mm]
also [mm] a_9=2
[/mm]
Probe: $0*1!+2*2!+2*3!+1*4!+5*5!+2*6!+6*7!+6*8!+2*9!=1.000.000$
Schön. Mir gefällt nur die Schachtelnotation oben nicht.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 21:49 Sa 17.11.2012 | | Autor: | sissile |
Hallo
Jap das meinte ich.
Trotzdem das schön in einen beweis aufzuschreiben gelingt mir nicht. (da auch soviele Sachen gleichzeitig zu beweisen sind(Existenz, Eindeutigkeit, wie [mm] a_i [/mm] aussehe..) Deinen Ansatz hab ich leider gar nicht verstanden. Ich werds die tage noch weiter versuchen, wenn ich was hab meld ich mich.
Wenn du noch einen Hinweis hast wäre ich auch nicht abgeneigt..
Liebe Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:02 Sa 17.11.2012 | | Autor: | reverend |
Hallo,
> Trotzdem das schön in einen beweis aufzuschreiben gelingt
> mir nicht. (da auch soviele Sachen gleichzeitig zu beweisen
> sind(Existenz, Eindeutigkeit, wie [mm]a_i[/mm] aussehe..)
Wenn Du Deinen Ansatz vernünftig notieren kannst, sind Existenz und Eindeutigkeit kein Problem.
> Deinen
> Ansatz hab ich leider gar nicht verstanden. Ich werds die
> tage noch weiter versuchen, wenn ich was hab meld ich
> mich.
> Wenn du noch einen Hinweis hast wäre ich auch nicht
> abgeneigt..
Na, noch den weiter unten, zu Rainers Vorschlag. Aber damit beweist Du ja noch nicht alles.
Ich denk mal drüber nach, aber nicht viel. 
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:20 Mo 19.11.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:36 Sa 17.11.2012 | | Autor: | rainerS |
Hallo
Vielleicht noch dieser Tipp: Überlege dir, dass dir Darstellung nur dann eindeutig sein kann, wenn
[mm] a_1*1!+a_2\cdot{}2!+a_3\cdot{}3!+.....+a_{k-1}\cdot{}(k-1)! < k! [/mm]
gilt. Dann beweise diese Ungleichung.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:49 Sa 17.11.2012 | | Autor: | reverend |
Hallo sissile,
zu Rainers Tipp zur Eindeutigkeit:
> Vielleicht noch dieser Tipp: Überlege dir, dass dir
> Darstellung nur dann eindeutig sein kann, wenn
>
> [mm]a_1*1!+a_2\cdot{}2!+a_3\cdot{}3!+.....+a_{k-1}\cdot{}(k-1)! < k![/mm]
>
> gilt. Dann beweise diese Ungleichung.
Dazu zeige [mm] 1*1!+2*2!+3*3!+\cdots+(k-1)*(k-1)!=\summe_{m=1}^{k-1}m*m!=k!-1
[/mm]
Induktion hilft.
Grüße
reverend
|
|
|
|
