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)!
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