Fantastic problem, but certainly very difficult . Let $P(n)$ and $Q(a,b)$ denote the first and second given equations respectively. We divide the proof into 3 parts. Part I: $f(1)=1$ and shenanigans. Let $f(1)=c$. $P(1)$ gives $f(c+1)=1$. Then $Q(a,c+1)$ gives $f(a+c) \leq f(a)+1$ for all $a$. Assume FTSOC that $c>1$. If $f(a+c) \leq f(a)$ for some $a$, then look at the sequence $f(a),f(a+c),f(a+2c), \dots$. Some two terms of this sequence must be equal. This is because every next term is at most one more than the previous, and so either the sequence is bounded and only takes finitely many values, or it must cross $f(a)$ again somewhere, at which point the term will be equal to $f(a)$ by discrete continuity. Thus $f(b)=f(b+kc)$ for some positive integers $b,k$. Now $P(b+kc)$ gives: \begin{align*} b+kc &= f(f(b+kc)+b+kc) \\ &= f(f(b)+b+kc) \\ & \leq f(f(b)+b)+k \\ \implies b+kc &\leq b+k \end{align*}contradicting $c>1$. Thus $f(a+c)=f(a)+1$ for all $a$. But putting $a=1$ gives $$1=f(1+c)=f(1)+1>1$$Contradiction! Thus $f(1)=1$. Now note that this gives $c=1$, so $f(2)=f(c+1)=1$ and $f(a+1) \leq f(a)+1$ for all $a$. Thus $f$ satisfies discrete continuity, in the following sense: if $f(a)=u<v=f(b)$ for some $a<b$, then for any $u \leq y \leq v$, there is an $a \leq x \leq b$ such that $f(x)=y$. $P(2)$ gives $f(3)=2$, and $P(3)$ gives $f(5)=3$. A standard induction now gives $f(F_n)=F_{n-1}$ for all Fibonacci numbers $F_n$, but we won't use that beyond $5$. Part II: $f$ is non-decreasing. We need a small claim for that: Claim: If $f(a)=f(b)$, then $|a-b| \leq 3$. Proof: Assume FTSOC that $f(n)=f(n+k)$ for some $n,k$ with $k \geq 4$. Then $P(n+k)$ gives $$n+k=f(f(n+k)+n+k)=f(f(n)+n+k)$$Note that $4=5-1$. Thus, for any $m$: \begin{align*} f(m+k) &= f(m+4+(k-4)) \\ &\leq f(m+4)+k-4 \\ &\leq f(m)+f(5)+k-4 \\ \implies f(m+k) &\leq f(m)+k-1 \end{align*}Using this, we get $$n+k=f(f(n)+n+k) \leq f(f(n)+n)+k-1 = n+k-1$$Contradiction! Thus the claim is proved. $\blacksquare$ Suppose $f(n+1)<f(n)$ for some $n$. We have 3 cases: Case I: $f(n+1)=f(n)-1$ Then $P(n+1)$ directly gives $$n+1=f(f(n+1)+n+1)=f(f(n)+n)=n$$Contradiction! Case II: $f(n+1)=f(n)-2$ Then $P(n+1)$ and $P(n)$ give \begin{align*} f(f(n)+n)+1 &=n+1 \\ &= f(f(n+1)+n+1) \\ &= f(f(n)+n-1) \\ \implies f(f(n)+n) &=f(f(n)+n-1)-1 \end{align*}which reduces to Case I with $f(n)+n-1$ instead of $n$. Case III: $f(n+1) \leq f(n)-3$ Since $f$ is surjective, it must cross $f(n)$ again at some point. Thus, by discrete continuity, there is a $k>0$ such that $f(n)=f(n+k)$. But, $f$ can increase by at most $1$ at each step, so we must have $k \geq 4$, which contradicts the Claim. Thus we get a contradiction in each case, so $f(n+1) \geq f(n)$ for each $n$, which implies that $f$ is non-decreasing. In particular, we also have that the function $f(n)+n$ is strictly increasing. Now the tedious part of the proof is done, and we can get to the meat of the problem. Part III: $f(n)$ can take at most two values for each $n$. Let $\alpha=\frac{\sqrt5-1}{2}$. Note that $\alpha^2+\alpha=1$. Let $g(x)=\lfloor \alpha x \rfloor +x$. Note that $g$ is a strictly increasing function on the natural numbers. Lemma: $g(\lfloor \alpha n \rfloor)+1 \leq n \leq g(\lfloor \alpha n \rfloor +1)$ for each positive integer $n$. Proof: Standard proof, just using the facts that $g$ takes integer values, and $x-1< \lfloor x \rfloor < x$ whenever $x$ is not an integer. $\blacksquare$ Now we use induction on $n$ to prove that: $$\boxed{f(n) \in \{ \lfloor \alpha n \rfloor, \lfloor \alpha n \rfloor +1\}}$$for each positive integer $n$. The base cases $n=1,2$ are already done, because $f(1)=1=\lfloor \alpha \rfloor+1$ and $f(2)=1=\lfloor 2 \alpha \rfloor$. Now assume we have some $n \geq 3$, and the claim is true for all positive integers less than $n$. Let $m'=\lfloor \alpha n \rfloor$, and let $m$ be the largest positive integer such that $f(m)+m \leq n$ (such an $m$ exists since $f(1)+1=2 < n$). Since $n \geq 3$, we have $n \geq m'+2$ (this can be seen pretty easily, for example by noting that since $\alpha<1$, the function $n-\lfloor \alpha n \rfloor$ is non-decreasing, and it is equal to $2$ when $n=3$). By induction hypothesis, $\lfloor \alpha k \rfloor \leq f(k) \leq \lfloor \alpha k \rfloor +1$, thus $g(k) \leq f(k)+k \leq g(k)+1$ for all $k<n$. But by the lemma and induction hypothesis, we have $f(m')+m' \leq g(m')+1 \leq n$, so by maximality of $m$, we have $m \geq m'$. Also from the lemma and induction hypothesis, we have $$n \leq g(m'+1)<g(m'+2) \leq f(m'+2)+m'+2$$(here if $m'+2 = n$, we can't use the induction hypothesis, but in that case it is obvious that $f(m'+2)+m'+2>n$) So $m \leq m'+1$ (because $f(x)+x$ is strictly increasing). This implies $m \in \{m',m'+1\}$. We have two cases: Case I: $f(m)+m<n$ By the lemma and induction hypothesis, we have $n \leq g(m'+1) \leq f(m'+1)+m'+1$, so we must have $m=m'$. But in this case, $$f(m')+m' < n \leq f(m'+1)+m'+1$$$$\implies m'=f(f(m')+m') \leq f(n) \leq f(f(m'+1)+m'+1)=m'+1$$$$\implies f(n) \in \{m',m'+1\}$$ Case II: $f(m)+m=n$ In this case we directly get $$f(n)=f(f(m)+m)=m \in \{m',m'+1\}$$ From both cases, we have that $f(n) \in \{m',m'+1\}$, which is what we wanted to prove. Thus we are done by induction. Note that in fact we have shown that $f(2022) \in \{1249, 1250\}$.

Supercali wrote: Fantastic problem, but certainly very difficult Completely agreed. Your use of discrete continuity everywhere is amazing. Full motivation on my blog. Define $\phi=\frac{\sqrt5-1}{2}$. Claim 1: $f(n)\ge \lfloor \phi n\rfloor$. Proof. This is obvious for $n=1$. Else suppose $f(n+1)=y$. From the second condition we get $$f(a+n)\le f(a)+y\implies f(a+kn)\le f(a)+ky \quad \forall a,k\in \mathbb{N}$$Define $C=f(1)+f(2)+\cdots+f(n)$. Note that for any number $T>n$, we can let $T=qn+r$ where $0\le r<n$ and $q\ge 1$. Thus, $$f(T)=f(qn+r)\le f(r)+qy\le C+\frac{Ty}{n}$$Using the first equation, $$T=f(f(T)+T)\le \frac{(f(T)+T)y}{n}+C\le \frac{(C+\frac{Ty}{n}+T)y}{n}+C$$This rearranges to $$Tn^2\le Ty^2+Tyn+Cyn+Cn^2$$Taking sufficiently large $T$, we must have $n^2\le y^2+yn$ and so $y\ge \phi n$, or $f(n+1)\ge \phi n$. Thus, $f(n)\ge \phi(n-1)$ and since $f(n)$ is an integer it is $\ge \lfloor \phi n \rfloor$. Claim 2: $f(n)\le \lfloor \phi n \rfloor +2$. Proof. Suppose $f(n)=\lfloor \phi n \rfloor +c$. From the first equation, $$n=f(f(n)+n)=f(\lfloor \phi n \rfloor+c+n)\ge \lfloor \phi ( \lfloor \phi n \rfloor+c+n)\rfloor\ge \lfloor \phi^2n+(c-1)\phi +\phi n\rfloor=\lfloor n+(c-1)\phi \rfloor$$Thus $c<3$, concluding the proof. Claim 3: $f$ is non-decreasing. Proof. Suppose $f(a+1)=f(a)-c$. We have $\lfloor \phi(a+1) \rfloor \le f(a+1)=f(a)-c\le \lfloor \phi a \rfloor +2-c$, so $c\le 2$. If $f(n+1)=f(n)-1$, then $f(f(n+1)+n+1)=f(f(n)+n)$, which is a contradiction. If $f(n+1)=f(n)-2$, then $n+1=f(f(n+1)+n+1)=f(f(n)+n-1)$ but $n+1=f(f(n)+n)+1$, so this in fact reduces to the previous case. Claim 4: $f(n)=\lfloor \phi n\rfloor$ or $\lfloor \phi n\rfloor+1$. Proof. It suffices to show $f(n)\ne \lfloor \phi n\rfloor+2$. Suppose $f(n)=\lfloor \phi n \rfloor+2$. Note that $$f(f(\lfloor \phi n \rfloor+1)+\lfloor \phi n \rfloor+1)=\lfloor \phi n \rfloor+1<f(n)$$$$\implies f(\lfloor \phi n \rfloor+1)+\lfloor \phi n \rfloor+1< n$$But $f(\lfloor \phi n \rfloor+1)+\lfloor \phi n \rfloor+1> \lfloor \phi(\lfloor \phi n \rfloor+1)\rfloor+\phi n\ge \lfloor \phi^2n\rfloor+\phi n>\phi^2n+\phi n-1=n-1$. Since we are working with integers, $f(\lfloor \phi n \rfloor+1)+\lfloor \phi n \rfloor+1\ge n$, contradiction. This concludes the proof.