Examples of "eventually reaches y under iteration" other than the Collatz problem

Question

The Collatz conjecture states that iteratively applying the map

$$f(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ 3n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases}$$

to any positive integer $n_0$ eventually yields $1$.

I'm looking for other non-obvious examples in mathematics of (proven or conjectured) statements of the form:

Take any object $x$ from a set $X$ and repeatedly apply the (not necessarily arithmetic) transformation $\sigma:X\rightarrow X$. You will eventually reach $y\in X$ after a finite number of steps.

The difference between this pattern and an attractor in physics is that here, the system is discrete and converges within a finite number of steps, and that all elements of the set are inside the "basin of attraction" (also, it is possible for even the fixed point to escape again for a cycle, as is the case with the Collatz map for $1 \rightarrow 4 \rightarrow 2 \rightarrow 1$).

Trivial examples I can think of from the top of my head:

• Take any integer $n$ and repeatedly subtract $1$. You will eventually reach $0$.
• Take any polygon and repeatedly cut off a triangle whose one edge connects two corners of the polygon. You will eventually be left with a triangle (though of course this triangle is only unique if you consider it through the lens of graph topology).
• Take any permutation $a \in S_n$ in list form and repeatedly traverse it from left to right, exchanging any two adjacent elements that are in the wrong order. You will eventually reach the trivial permutation $1 \in S_n$ (Bubble sort algorithm).

The problem is that in these examples, the fact that all initial states converge and even the number of steps towards convergence are immediately obvious and predictable. I really like the way the convergence time of the Collatz map behaves pseudorandomly. Are there any more examples with that property?

Answer 1

Let the set $X$ the positive integers which are divisible by $9$. Let the transformation $\sigma$ be the operation of computing the digit sum.
Then taking any element from $X$ and applying repeatedly $\sigma$ gives $y=9$.

Answer 2

An alternative is $$ x_{k+1} = \left\{ \begin{array} {} x_k /2 & \text{if } x_k \equiv 0 \pmod 2 \\ 3 x_k+1 & \text{if } x_k \equiv 1 \pmod 4 \\ 3 x_k-1 & \text{if } x_k \equiv 3 \pmod 4 \\ \end{array} \right. $$

This is -more than the Collatz-transformation- even guaranteed to run into the trivial cycle for every positive starting number $x_0$

If we write the trajectories displaying only the odd natural numbers and always beginning at odd multiples of 3 (because multiples of 3 cannot occur in the tail of a trajectory) we get $$ \begin{array} {} 3 &\to 1 \\ 9 &\to 7 &\to 5 & \to 1 \\ 15 &\to 11 &\to 1 \\ 21 &\to 1 \\ 27 &\to 5 &\to 1 \\ 33 &\to 25 &\to 19 &\to 7 &\to \text{(see above)}\\ ... \\ \end{array}$$

Tightly related are version like $5x+1$ where the following division is made by $2$ or $3$ depending on the modular residue class, where then apparently everything runs into the trivial cycle. (But well, these are not really qualitatively different ideas)

Answer 3

Hm, not sure whether this is an example in the scope of your question... What about rowwise Gaussian elimination in a matrix of $c$ columns and $r=c+a$ rows: the last $a$ rows become evantually zero-vectors?