Indeed, it is folklore.

Certainly not. Be can build step by step $f(n)$ with infinitely many choices at each step. $f(1)=a$ $f(2)=b$ $f(3)\equiv f(1)\pmod 2$ : infinitely many choices $f(4)\equiv f(1)\pmod 3$ and $f(4)\equiv f(2)\pmod 2$ : infinitely many choices ... And so on (the only thing to check is that at each step constraints are consistant).

I have a nice solution: Answer: no. Lemma$1$(obviously): in any polynomial $p(x)$ with real coefficients, where $p(n) \in \mathbb{N}$ if $n \in \mathbb{N}$, the number of $m \in \mathbb{N}$ for which the inequality $p(m)-p(m+1)>0$ satisfies is finite. It's obvious. Now we will build a function $f:\mathbb N\to\mathbb N$ for which $f(2n-1)>f(2n)$ for all $n \in \mathbb{N}$. By our lemma, this is not a polynomial. We will build by induction. $f(1)$ and $f(2)$ are trivial. Lemma$2$: we have $f(1)$, $f(2)$, $f(3)$, ... $f(k)$ for which $f(m)-f(n)$ is divided by $m-n$ for all $m>n$ ($m<k+1$). Then we always have a solution in CRT for $f(k+1)$ and $f(k+2)$. Prove: suppose we don't have a solution in CRT. Then for some $a$ and $b$ we have two contradictory comparisons: 1)$f(k+1) \equiv f(k-a) \pmod{a+1}$ 2)$f(k+1) \equiv f(k-b) \pmod{b+1}$ Since these comparisons are contradictory, then $a+1$ and $b+1$ are not coprime. Let we have a contradiction with a prime $p$ in our comparisons. Let $V_p(a+1)=x$ and $V_p(b+1)=y$ and let WLOG $x \le y$. It's easy to see, that $f(k-a) \equiv f(k-b) \pmod{a-b}$ or $f(k-a) \equiv f(k-b) \pmod{p^x}$. But it is a contradiction, since we supposed, that we have a contradiction with comparisone and a prime $p$. So, the lemma is proved. The step of induction. First we will fix $f(2n)$. Then we may select $f(2n-1)$ by CRT so that $f(2n-1)>f(2n).$