Kaprekar's constant is 6174: Proof without calculation

Suppose that our digits are $a \ge b \ge c \ge d$: then Kaprekar's routine generates $999(a-d) + 90(b-c)$ as the next step. Since the inequalities tell us that $b-c \le a-d$ we can easily demonstrate that there are at most 55 equivalence classes, being the 10th triangle number. That's a moderate improvement over 70.

A bit of calculation gives the graph:

Kaprekar's routine is a mapping from the set $F_0=\{0000,0001,0002,\dots,6174,\dots,9999\}$ of four digit natural numbers to itself. It only depends on the digits of a number and not on their positions within the number. Kaprekar's routine consists in

• forming an integer by arranging the digits in descending order,
• forming a smaller integer by arranging the digits in ascending order,
• eventually taking the difference of both.

Hence if $\,d_3,d_2,d_1,d_0\,$ are the given digits satisfying $\,9\geqslant d_3\geqslant d_2\geqslant d_1\geqslant d_0\geqslant 0$, then Kaprekar's routine yields $$1000d_3+100d_2+10d_1+d_0\;-\;(1000d_0+100d_1+10d_2+d_3)\\[2ex] =\;999(d_3-d_0) + 90(d_2-d_1)\,. \tag{0}$$ So the result is completely described by the pair $(D,d)$ with $D=d_3-d_0, d=d_2-d_1$, and $\,9\geqslant D\geqslant d\geqslant 0$.

Target of this post is to prove without explicitly calculating all cases that Kaprekar's routine possesses a unique fixed point which is the famous $6174$. Writing 'unique' assumes that we ignore the boring (in the sense of uninteresting) case $0000$.

It is consequent and helpful to not distinguish between numbers in $F_0$ having the same $(D,d)$ value, since Kaprekar's routine generates the same image number from them. Hence partition the set $F_0$ into corresponding subsets labelled by $(D,d)$. The smallest representative in the respective subset is the four digit number $10d+D$, it has at least two leading zeros.
The mapping $K:(D,d)\mapsto (D\,',d\,')$ induced by Kaprekar's routine is referred to as a Kaprekar step. Look at the arrows in the the nice directed graph in Peter Taylor's answer.

$(D=0,d=0)\,$ labels the subset $\{0000, 1111,\ldots, 9999\}\subset F_0$ of numbers with all digits equal. Kaprekar's routine produces $0000$ out of them, thus $K(0,0)=(0,0)$.
If $D\geqslant 1$, then Kaprekar's routine generates numbers ranging from $0999$ to $9801$ which are divisible by $9$, whence $K(D,d)\neq(0,0)$ in that case.
In the sequel attention is restricted to pairs $(D,d)$ with $D\geqslant 1$.

Lemma$\;$ There is a collection of formulae for the Kaprekar step $K(D,d)=(D\,',d\,')$, but case distinction is needed:

1. If $\,D>d=0\,$ then $$\left.\begin{matrix}D\,' \\ d\,'\end{matrix}\right\}\;=\; 4.5 \pm |D-5.5|\tag{1}$$ Note the invariance $K(11-D,d) = K(D,d)$ for $D\geqslant 2$, and that $D\,'>d\,'$.
2. If $\,D=d\geqslant 1\,$ then $$\begin{align} D\,' & \;=\;\; 2\,|D-5|+1\\[1ex] d\,' & \;=\: \big|\:2\,|D-5|-1\,\big| \end{align}\tag{2}$$ Note that $D\,'=d\,'+2\,$ if $\,D\neq 5$.
3. If $\,D>d\geqslant 1\,$ then $$\begin{align} D\,' & \;=\;\: |D+d-10| + \delta_{10,D+d} + (D-d)\\[1ex] d\,' & \;=\; \big| |D+d-10| + \delta_{10,D+d} - (D-d)\,\big|\end{align}\tag{3}$$ where $\delta_{p,q}$ denotes the Kronecker delta.

Proof: The relevant values $\,9\geqslant D\geqslant d\geqslant 0\,$ form a triangle in the first octant in the $D,d$-plane.

1. corresponds to the lower edge of the triangle. Kaprekar's routine yields $$999D\;=\; 1000\,(D-1) + 100\cdot 9 + 10\cdot 9 + (10-D)\,.$$ Reading off the digits and using $$\left.\begin{matrix}\min(p,q) \\ \max(p,q)\end{matrix}\right\} \;=\; \frac12\big(p+q\mp |p-q|\big)\tag{4}$$ with $\,p=D-1, q=10-D$, the formula is obtained.
2. corresponds to the upper "diagonal" edge.
   Kaprekar's routine, not yet specialising to $D=d$ in view of case 3, yields $$999D+90d\;=\; 1000\,D + 100\,(d-1) + 10\,(9-d) + (10-D)\,.\tag{5}$$ Setting $d=D\,$ now, and rewriting the digits with the help of $(4)$ gives $5\pm |D-5|, 4\pm |D-5|$. This leads to $$\begin{align} D\,' & \;=\; 5+|D-5| - \big(4-|D-5|\big)\\[1ex] d\,' & \;=\; \big|\, 5-|D-5| - \big(4+|D-5|\big)\big|\,. \end{align}$$
3. corresponds to the interior of the triangle including the RHS vertical edge.
   From $(5)$ we read off the digits which satisfy $9-d\geqslant 10-D$ in the present case, and $D>d-1$ anyway. Thus, $$\begin{align} D\,' & \;=\; \max(D,9-d) - \min(d-1,10-D)\\[1ex] d\,' & \;=\; \big|\min(D,9-d) - \max(d-1,10-D)\,\big|\,, \end{align}$$ and using $$\begin{align} \begin{matrix}\max\\ \min\end{matrix}\big(D,9-d\big) &\;=\; \frac{9+D-d\pm |D+d-9|}2\\[1.67ex] \begin{matrix}\max\\ \min\end{matrix}\big(d-1,10-D\big) & \;=\; \frac{9-(D-d)\pm |D+d-11|}2\\[2ex] \frac{|D+d-9|+|D+d-11|}2 & \;=\; |D+d-10| +\delta_{10,D+d} \end{align}$$ one deduces the desired.$\quad\blacksquare$

Just an observation regarding the set of pairs $(D,d)$ with $d\geqslant 1$, as covered by cases 2. and 3. in the lemma: The mapping $(D,d)\mapsto (10-d,10-D)$ defines an involution, and the formulae $(2)$ and $(3)$ are invariant under it.

Fixed point theorem$\;$ The Kaprekar step has precisely one fixed point, namely $K(6,2)=(6,2)$.

Proof: Looking for fixed points we proceed along the cases in the lemma.

1. If $\,d=0\,$ then $\,0\stackrel{!}{=}d\,'=4.5-|D-5.5|\implies D=1$, but $(1)$ would require $D\,'=9\,$.
2. If $\,D=d\,$ then $$K(D,D) \;=\; \begin{cases}(1,1) & D=5\\ (d\,'+2,d\,') & \text{else.}\end{cases}$$ Hence again, no $(D,D)$ is a fixed point.
3. Now we assume $\,D>d\,$ and the fixed point conditions read $$\begin{align} D & \;\stackrel{!}{=}\;\: |D+d-10| + \delta_{10,D+d} + (D-d)\iff d\;=\;\: |D+d-10| + \delta_{10,D+d}\tag{6}\\[1ex] d & \;\stackrel{!}{=}\; \big| |D+d-10| + \delta_{10,D+d} -D +d\,\big|\tag{7}\end{align}$$ Inserting $(6)$ into $(7)$ implies $d =|2d-D|$, thus $D=3d$ as $\,D>d\,$ needs to be fulfilled.
   Insert this into $(6)$, the Kronecker delta will vanish, and the resulting equation $\,d=|4d-10|\,$ is uniquely solved by $d=2\implies D=3d=6\,$.$\quad\blacksquare$

The fixed point $(6,2)$ of $K$ determines the unique fixed point of Kaprekar's routine as $\,999\cdot 6+90\cdot 2=6174\,$.