# A Collatz-like question about permutations

An answer to this question would provide an explicit counterexample to this question, but otherwise I don't know if it is interesting.

Consider all permutations $\pi$ on the natural numbers such that for each $i$, $\pi(3i)=2i$ and $\lbrace \pi(3i+1),\pi(3i+2)\rbrace = \lbrace 4i+1,4i+3\rbrace$.

The question: Is there such a permutation for which all the cycles have finite length?

By computer it is easy to find choices that make the cycles containing the first several thousand integers finite.

• Do you actually have any explicit example of such a permutation? Why do they exist? – Igor Rivin Aug 5 '15 at 14:03
• @Igor: All such $\pi$ are injective and surjective if we choose $\pi(3i+1)\ne \pi(3i+2)$, thus they are all permutations, if this was your question. – domotorp Aug 10 '15 at 20:40

The reason is that there are only countable many cycles, so we can take care of them one by one to make them finite. Suppose up to some point all cycles containing numbers less than $n$ are finite and consider the cycle of $n$. It has two ends and at both ends we can make choices by picking the yet undecided values of $\pi(3i+1)$ and $\pi(3i+2)$ as we like. By making some choices, after a while the two ends will either meet, or both go to some very large values, which means that we can make many choices, as in that high range nothing was decided earlier. Since for your parameters $\frac 32 \cdot \frac 34<2$, the graph of the choices will behave like an expander, so the two ends can be made to meet.