1

Find the number of functions $f(x)$ from nonnegative integers to nonnegative integers so that $f(f(n)) = n+2022$ for every nonnegative integer n.

Let $a_0 = f(0)$ and let $a_n = f(a_{n-1})$ for $n\ge 1$. Then $a_{n} - a_{n-2} = 2022$ for every $n\ge 2$. The characteristic equation of the corresponding homogeneous recurrence is $x^2 - 1,$ which has roots $\pm 1.$ Also, $b_n = 1011 n + b$ satisfies the inhomogeneous recurrence $b_n - b_{n-2} = 2022$ for any integer $b$. So $a_n = A(-1)^n + 1011 n + B$ for some integers $A,B$ and all $n$. We must ensure that $a_n$ is always nonnegative. We must have $a_0\ge 0\Rightarrow A \ge -B.$ Also, $a_1\ge 0\Rightarrow -A +1011 + B \ge 0, a_2\ge 0\Rightarrow A +2022 + B\ge 0.$ In general, for all $n=2k+1> 0$, $B\ge A-1011 n$ and for all $n=2k\ge 0, A\ge -B-1011n$. To satisfy both of these inequalities, it suffices to have $B\ge A-1011$ and $A\ge -B\Rightarrow B\ge -B-1011\Rightarrow 2B\ge -1011.$ So $B$ is at least $-505.$ Though I'm not sure how to determine what $f(n)$ can be. Clearly $f(n) = n+1011$ solves the functional equation and $f(0)$ cannot be zero, so it must be positive. If there exists $n$ so that $f(n) = n$, then we get $n=n+2022$ by plugging this n into the given equation, which is a contradiction. Hence $f$ has no fixed points.

user33096
  • 2,021

1 Answers1

0

$$f(f(n))=n+2022\tag0$$ $$f(f(f(n))=f(n+2022)$$ $$f(n+2022)=f(n)+2022\tag1$$ Thus specifying $f(n)$ for $n\in[0,2021]$ fixes $f$.

Now write the nonnegative integers in a zero-indexed infinite matrix with $2022$ columns so that $n$ has – and is treated as equal to – the coordinates $(\lfloor n/2022\rfloor,n\bmod2022)$. Then if $f$ sends $(q+d,r)$ to $(q,s)$ where $d\ge1$ (a backwards jump), by $(1)$ it must also send $(d-1,r)$ to $(-1,s)$ which is absurd. As a corollary $f$ cannot send $(q,r)$ to $(q+d,s)$ with $d\ge2$ (a long forwards jump), since by $(0)$ $(q+d,s)$ must be sent to $(q+1,r)$, a backwards jump.

Therefore a number $(0,r)=r\in[0,2021]$ can only be sent by $f$ to $(0,s)$ or $(1,s)$; $s\ne r$ since $f$ would then have a fixed point by $(0)$, which is inconsistent with $(1)$. If $f((0,r))=(0,s)$, columns $r$ and $s$ of the infinite matrix are completely defined; if $f((0,r))=(1,s)$, $(1)$ implies $f((0,s))=(0,r)$ with the same end result as before.

The final result is that all admissible functions $f$ are specified by a pairing of residue classes modulo $2022$ and then, for each pair $(r,s)$, whether $f((0,r))=(0,s)$ or the other way round. The number of such $f$ is thus $$\frac{2022!}{1011!}$$ A similar argument shows that for $f^{(p)}(n)=n+pq$ the number of such functions is $$\frac{(pq)!}{q!}$$

Parcly Taxel
  • 103,344
  • Below is my understanding of how you got $2022!/1011!$. Correct me if I'm wrong. first choose a number $s$ for $0$ in $2021$ ways and one of the pairs $(0,s)$ or $(1,s)$ in 2 ways. Then remove the residues $0$ and $s\neq 0$, leaving $2020$ residues. Of the remaining residues, pick the smallest one and choose the pair $(0,s)$ or $(1,s)$ for this residue in $2\cdot 2019$ ways. Continue the process, obtaining $2^{1011} \cdot 2021!!$ ways. – user33096 Sep 25 '22 at 14:53
  • @user33096 Permute the first $2022$ nonnegative integers any way you like ($2022!$ ways). This naturally splits into $1011$ ordered pairs, and these pairs may be permuted in $1011!$ ways without changing $f$. The quotient gives the answer. – Parcly Taxel Sep 25 '22 at 14:59
  • Can you elaborate more on how "this naturally splits into 1011 ordered pairs"? Are you splitting a permutation into 1011 ordered pairs? Also, I find it much easier to justify that f has no fixed points using (0) instead of (1). – user33096 Sep 25 '22 at 15:04
  • @user33096 Yes. Suppose the permutation is $(a_1,a_2,a_3,a_4,\dots,a_{2022})$. Then the pairs are just length-2 chunks $(a_1,a_2)(a_3,a_4)(a_5,a_6)\dots$ The first element in each pair becomes the $(0,r)$ in my construction and the second becomes $(0,s)$, with $f((0,r))=(0,s)$. – Parcly Taxel Sep 25 '22 at 15:38