Problem. Define the operation base change from $k$ to $m$: to make the operation for natural number $n$ we should write $n$ in the base-$k$ numeral system and read this in the base-$m$ numeral system.
Let $n$ be a natural number. Make for $n$ base change from $2$ to $3$, then subtract $1$, then change base from $3$ to $4$, then subtract $1$ and so on.
Prove that we'll get zero after finitely many steps.
For example, for $n=4$ the sequence is $$9,8,10,9,11,10,12,11,12,11,12,11,12,11,12,11,12,11,\\ 12,11,11,10,10,9,9,8,8,7,7,6,6,5,5,4,4,3,3,2,2,1,1,0.$$
For $n=6$ the sequence contain 762 terms.
The problem has elementary proofs, but it's from a book on Set Theory and authors says that it has a solution using ordinals: change all bases to $\omega$ and get decreasing sequence of ordinals.
I can't understand this hint.
Suppose at the base $n$ stage you have the representation $a_ka_{k-1}\dots a_1a_0$, representing
$$g_n=a_kn^k+a_{k-1}n^{k-1}+\ldots+a_1n+a_0\;,$$
where $a_0,\dots,a_k\in\{0,\dots,n-1\}$, and $a_k\ne 0$. Let
$$\hat g_n=\omega^k\cdot a_k+\omega^{k-1}\cdot a_{k-1}+\ldots+\omega\cdot a_1+a_0\;,$$
where the arithmetic is all ordinal arithmetic. The change of base from $n$ to $n+1$ changes the interpretation of $a_ka_{k-1}\dots a_1a_0$ to
$$a_k(n+1)^k+a_{k-1}n^{k-1}+\ldots+a_1(n+1)+a_0\;.\tag{1}$$
If $a_0\ne 0$, subtracting $1$ yields
$$g_{n+1}=a_k(n+1)^k+a_{k-1}n^{k-1}+\ldots+a_1(n+1)+(a_0-1)\;,$$
and
$$\hat g_{n+1}=\omega^k\cdot a_k+\omega^{k-1}\cdot a_{k-1}+\ldots+\omega\cdot a_1+(a_0-1)<\hat g_n\;.$$
In general suppose that $a_i$ is the rightmost non-zero coefficient/digit. Then subtracting $1$ from $(1)$ yields
$$g_{n+1}=a_k(n+1)^k+\ldots+(a_i-1)(n+1)^i+\underbrace{n(n+1)^{i-1}+\ldots+n(n+1)+n}_{\text{all coefficients }=n}\;,$$
and
$$\hat g_{n+1}=\omega^k\cdot a_k+\omega^{k-1}\cdot a_{k-1}+\ldots+\omega^i\cdot(a_i-1)+\underbrace{\omega^{i-1}\cdot n+\ldots\omega\cdot n+n}_{\text{all coefficients }=n}\;.$$
This is again less than $\hat g_n$, since
$$\omega^i\cdot a_i>\omega^i\cdot(a_i-1)+\underbrace{\omega^{i-1}\cdot n+\ldots\omega\cdot n+n}_{\text{all coefficients }=n}\;:$$
this follows from the (possibly more evident) fact that
$$\omega^i>\underbrace{\omega^{i-1}\cdot n+\ldots\omega\cdot n+n}_{\text{all coefficients }=n}\;,$$
since $\omega^i\cdot a_i=\omega^i\cdot(a_i-1)+\omega^i$.
Thus, the sequence of ordinals $\hat g_n$ is strictly decreasing and must terminate at $0$ in finitely many steps. But $\hat g_n=0$ if and only if $g_n=0$, so the same is true of the sequence of numbers $g_n$.