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