Two functions

[Avik Roy]

Consider two functions $f,g: \mathbb {N} \to \mathbb {N}$ so that \[g(n) = |\{a|f(a) \leq n \}| \] \[f(n) = |\{a|g(a) \leq n \}| \] Find the possible ranges for the functions $f$ and $g$

I just hope I didn't make any mistake while formulating this problem

[Corei13]

Note that $g(n) = |\{a|f(a) \leq n-1\}| + |\{a|f(a)=n\}| \geq |\{a|f(a) \leq n-1\}| =g(n-1)$
So, $g$ is increasing function, and so is $f$.
Now, $g(1) = a$ implies, $g(n) \geq a$ for all $n \in \mathbb{N}$, if $a > 1$, $a-1 \in \mathbb {N}$
So, we have, $f(a-1) = 0 \notin \mathbb{N}$, So $g(1)=1$ and similar argument shows that $f(1)=1$
For the sake of induction, let $f(m)=g(m)=m$ for all $m \leq n$
Let, $g(n+1) = n + i$, we know that, $g(n+1) = |\{a|f(a) \leq n\}| + |\{a|f(a)=n+1\}|$, so $|\{a|f(a)=n+1\}| = i$
$i \geq 2$ implies $f(n+1) = f(n+2) = n+1$
Now, $f(n+1) = |\{a|g(a) \leq n\}| + |\{a|g(a)=n+1\}| = f(n) = n$, because $|\{a|g(a)=n+1\}|=0$ as $i > 1$, a contradiction, so $i \leq 1$ or $g(n+1)\leq n+1$, similarly $f(n+1)\leq n+1$
Let, $f(n+1) = n$, Then, $g(n) = |\{a|f(a) \leq n\}| \geq n+1$, contradiction!
Similarly $g(n) > n$

so, $f(n)=g(n)=n$ for all $n\in \mathbb{N}$