ALL EN FR ES IT

Logo

≡ ► ◄ ▲

Transformationen

Mathematik Nr. 156

Kann man alle Zahlenpaare (x,y) mittels den beiden Transformationen

T1: (x,y) → (x+1, 2*y)

und

T2: (x,y) → (2*x, y+1)

in ein Paar (x,x) überführen, also dass x = y wird? x und y sind positive ganze Zahlen.

Beispiele zur Verdeutlichung:

a) (1, 2) {T2} → (2, 3) {T2} → (4, 4)

b) (3, 7) {T1} → (4, 14) {T2} → (8, 15) {T2} → (16, 16)

Versuchen Sie es mal mit (1,6)!

Lösung anzeigen

Zunächst formulieren wir das Zahlenpaar (x; y) um in (x; x+n); n ist also die Differenz zwischen y und x und ist positiv.

Wenn wir

T1: (x,y) → (x+1, 2*(x+n))

n mal anwenden erhalten wir

(x+n ; 2n*x + 2n*n)

Wenn wir

T2: (x,y) → (2*x, x+n+1)

(n-b) mal anwenden, erhalten wir

(2(n-b)*x + 2(n-b)*n ; 2n*x + 2n*n + n - b)

b ist eine Zahl unserer Wahl kleiner als n, (n-b) ist also positiv.

Nun wenden wir einmal T1 an:

(2(n-b)*x + 2(n-b)*n + 1  ;  2(n+1)*x + 2(n+1)*n + 2n - 2b)

Schließlich wenden wir (b-1) mal T2 an:

(2(n+1)*x + 2(n+1)*n + 2(b+1)  ;  2(n+1)*x + 2(n+1)*n + 2n - b + 1)

Die Differenz dieser beiden Zahlen ist der Absolutwert von

| 2(b+1) + b - (2n + 1) |

Wir erinnern uns, dass die Differenz der beiden ursprünglichen Zahlen n ist. Die Frage ist nun, ob es eine Zahl b gibt, sodass die neue Differenz kleiner als n ist, egal, wie groß die Zahl n ist:

| 2(b+1) + b - (2n + 1) |  <  n

Dies ist immer der Fall, mit Ausnahme von n=1. Wie wir den oben beschriebenen Algorithmus mehrfach anwenden, wird die Differenz der beiden Zahlen immer kleiner, bis sie schließlich 1 oder 2 wird.

Wenn die Differenz 2 ist, führt eine weiterer Durchlauf mit b=1 zu zwei gleichen Zahlen.

Wenn die Differenz 1 ist, führen folgende Schritte zu einem Zahlenpaar mit der Differenz 2:

(x        ;  x+1) ... ein  Zahlenpaar mit der Differenz 1
(x+1   ; 2x+2)  
(x+2   ; 4x+4)
(2x+4 ; 4x+5)
(4x+8 ; 4x+6) ... ein  Zahlenpaar mit der Differenz 2