| Autor |
Beitrag |
    
Sascha (Y2solution)
| | Veröffentlicht am Sonntag, den 29. Oktober, 2000 - 20:11: | 
|
Hallo!!!
Wer kann mir helfen?
"Zeigen Sie, daß die Repräsentation von Zahlen zur Basis 3 mit den Ziffern (-1,0,1) eindeutig ist!"
Danke, Danke, danke!!!
Sascha |
Rob
| | Veröffentlicht am Sonntag, den 29. Oktober, 2000 - 21:20: |
|
Hast du schon eine lösung für die 1.Aufgabe ? Danke |
Matroid (Matroid)
| | Veröffentlicht am Montag, den 30. Oktober, 2000 - 22:01: |
|
Hi Sascha,
sei neZ und nehmen wir mal an, daß es zwei verschiedene Repräsentationen gibt.
Also einerseits Sk i=0 ai*3i = n
und andererseits Sl i=0 bi*3i = n.
Wir können o.B.d.A annehmen, daß k>=l, ansonsten vertauschen wir eben k und l.
Außerdem können wir, falls l<k ist, die zweite Summe auch bis k laufen lassen mit Koeffizienten bi=0 für l<i<=k.
Dann haben wir in beiden Summen gleich viele Summanden. Jetzt bilde die Differenz:
Sk i=0 ai*3i - Sk i=0 bi*3i
= Sk i=0 (ai-bi)*3i = 0
Beweise nun, daß die Koeffizienten alle Null sind und zwar durch vollständige Induktion über k.
k=0 => (a0-b0)*1 = 0 => a0 = b0
Nun k->k+1. Hinschreiben, dann umsortieren und schließlich:
Sk i=0 (ai-bi)*3i = (bk+1-ak+1)*3k+1
Man sieht, die rechte Seite der Gleichung ist durch 3k+1 teilbar. Da auf der linken Seite nur kleiner Dreierpotenzen vorkommen und außerdem -2 < ai-bi < 2 für alle 0<=i<=k, folgt daß bk+1-ak+1=0. Auf den Rest der Darstellung wende die Induktionsvoraussetzung an (hat ja Summe bis k). Also immer gilt ai = bi.
Fertig.
Achtung: Hier wurde nicht gezeigt, daß die geforderte Darstellung existiert. Es wurde gezeigt, daß die Darstellung eindeutig ist, falls sie existiert. Wir haben immer noch keine Ahnung, wie man eine solche Darstellung für ein n ausrechnen kann. Mehr war aber in Deiner Aufgabe nicht verlangt.
Gruß
Matroid |
|
