nd.aktuell 235/2022, Denkspiel 2

Aufgabe

»Nach welcher Rechnungsart ist es möglich, einer Person zwei Zahlen zu nennen, die diese in Gedanken genommen hat?«

Interpretation

Es werden zwei natürliche Zahlen $m$ und $n$ gewählt. Aus dem Tupel $(m,n)$ ist bijektiv eine Zahl $z$ zu bilden, sodass aus $z$ wieder auf die Ursprungswerte $m$ und $n$ geschlossen werden kann.

Lösungsskizze

Gesucht ist eine eineindeutige Durchnumerierung der Tupel $(m,n)$. Dies kann zum Beispiel mithilfe Cantors erstem Diagonalargument (Beweis zur Abzählbarkeit der Rationalen Zahlen) geschehen; ordnet man $m$ und $n$ als Zeilen und Spalten einer Matrix an, können die Tupel diagonal eineindeutig durchnumeriert werden; der Index gibt die Zahl $z$ an. Da die Abbildung bijektiv ist, kann aus $z$ wieder auf das ursprüngliche Tupel $(m,n)$ geschlossen werden.

Formale Lösung

Wir wählen zwei natürliche Zahlen $m$ und $n$. Als Hilfsvariable definieren wir $s$, $$s:=m+n-1,$$ daraus bilden wir $z$ gemäß $$z:=\frac{s(s-1)}{2}+m;$$ dies können wir als Index in der folgenden Tabelle interpretieren:

	1	2	3	4	5	6	7
1	1	2	4	7	11	16	22
2	3	5	8	12	17	23
3	6	9	13	18	24
4	10	14	19	25
5	15	20	26
6	21	27
7	28

Beispiel

$m$	$n$	$s$	$z$	$t$	$m$	$n$

Erklärung

Dabei berechnet die (leicht modifizierte) Gaußsche Summenformel $$\frac{s(s-1)}{2},$$ wie viele Zahlen bereits in das Diagramm eingetragen wurden, und gibt somit den Startwert der Diagonalen an; anschließend wird $m$ als Offset addiert.

Invertieren

Zum Invertieren können wir entweder in der Tabelle nachlesen, oder folgenden Formelwust bemühen: $$\begin{array}{cc}\hfill t:=& \lfloor \frac{1}{2}(1+\sqrt{1+8(z-0.5)})\rfloor ;\hfill \\ \hfill m=& z-\frac{t(t-1)}{2},\hfill \\ \hfill n=& t-m+1.\hfill \end{array}$$