redacted.

The following is my solution, though the title is entirely by Sutanay, so go get him. I'll let him or someone else post the official solution. Replace condition (b) with "bounded" (the example we show for $c$ which work will work for the $2023$ bound). Clearly, $c>0$ else $f$ will eventually be negative. Replace $c$ by $c-\lfloor c \rfloor$ if necessary, to assume that $0<c<1$ and note that translating $f(x)$ to $f(x)-\lfloor c \rfloor x+M$ for $M$ sufficiently large (to make codomain in $\mathbb{N}$), returns a function which satisfies the problem conditions. Suppose $1/2<c<1$, then replace $f(x)$ by $x-f(x)+K$ for sufficiently large $K$ (again to keep codomain in $\mathbb{N}$), to get a new function which satisfies the problem conditions for the constant $0<(1-c)<1/2$. We conclude by showing that for $c=1/2$ there does exist a required function, but not for $0<c<1/2$, thus by extension, there exists a valid function for all numbers $k+1/2$ with integers $k \geq 0$, but no other constants work. For $c=1/2$, let $f(x)=1+\lfloor x/2 \rfloor$ (the $+1$ is to avoid $f(1)=0$), then (b) is obviously satisfied. For (a), observe that $$\lfloor (x+a)/2 \rfloor -\lfloor x/2 \rfloor \geq \lfloor (x+2)/2 \rfloor - \lfloor x/2 \rfloor \geq 1$$and $$\lfloor (x+a)/2 \rfloor -\lfloor x/2 \rfloor \leq (x+a)/2-(x/2-1) \leq a/2+1 \leq a$$with latter equality only for $a=2$ in which case the $\leq a/2+1$ bound is a strict inequality. Thus, $f(x+a)-f(x)$ is never a multiple of $a$ for $a>1$, so $f$ works. Now for $c<1/2$. Consider the numbers $f(1), f(2), \dots, f(N)$ for large $N>>0$. Each of them are in the range $[1, cN+T]$ for some constant $T>0$. By the pigeonhole principle, some $\lceil N/(cN+T)\rceil \geq 3$ of them are equal, and as $1/c>2$ and $N$ is sufficiently large. Among $i, j, k$ with $f(i)=f(j)=f(k)$, some two of them are not consecutive, i.e., say $k-i>1$. Then $(f(k)-f(i))/(k-i)=0$ is an integer, violating (a) and proving that $c<1/2$ does not work. The conclusion follows: the only $c$ which work are numbers of the form $k+1/2$ for integers $k \geq 0$.

Anecdote

Solution with Pranjal Srivastava, Anant Mudgal and Sutanay Bhattacharya. We call a function $f$ good if it satisfies the given conditions. If a function $f$ is good such that $f(x)-cx$ is bounded then $g(x)=f(x)-\lfloor{c\rfloor}x$ is also good with $g(x)-{c}x$ bounded. We allow functions to be from $\mathbb N$ to $\mathbb Z$. Clearly, if $f:\mathbb N\mapsto \mathbb N$ Now, if $\{c\}<\frac{1}{2}$ then we get that $\exists M$ such that $g(x)-cx\in [-M,M]$ then for all $N$, only $cN+2M$ different values are possible. Now, find an $N$ such that $\frac{N}{cN+2M}>2$ then there are three numbers $n_1<n_2<n_3$ are such that $g(n_1)=g(n_2)=g(n_3)$ this is not possible since $n_3-n_1>1$ and $\frac{f(n_3)-f(n_1)}{n_3-n_1}=0$ is an integer. This is a contradiction. Now similarly if $\{c\}>\frac12$ then for a similar reason $h(x)=x-g(x)$ will not be good for the same reason. Now, if $\{c\}=\frac12$ then let $c=n+\frac12$ for some $n\in \mathbb{N}_0$. Now, consider the function $f(x)=\lfloor{\frac{x}{2}}\rfloor+nx+1$. It can be checked that this works. $\square$ Alternate Solution by Sutanay Bhattacharya: We give a different proof that $\{c\}=1/2$. Let us first prove a claim: Claim: For any $k\ge 1$ and any $x$, $f(x+2^k)-f(x)$ is divisible by $2^{k-1}$ but not $2^k$. Proof. We prove this via induction on $k$. For $k=1$, the claim is trivial. Now assume the statement is true for some $k$, and note that $f(x+2^{k})-f(x)=2^{k-1}y_1$ and $f(x+2^k+2^k)-f(x+2^k)=2^{k-1}y$ for some odd integers $y_1,y_2$. Adding these, we see that $$f(x+2^{k+1})-f(x)=2^{k-1}(y_1+y_2)$$which is divisible by $2^k$ because $y_1+y_2$ is even. The fact that this is not divisible by $2^{k+1}$ follows from the condition on $f$.$\square$

(UGH rg snipe) I found the above super scam but incredibly slick solution after I found this, since the slick one's been posted, I"ll post what I think is the easier sol: The solution set is $c = n + \frac{1}{2}$ for some nonnegative integer $n$. This works by picking $f(n) = \lfloor cn \rfloor + 1$ Claim: $2^{k-1} \mid f(n+2^k) - f(n)$ Proof: By induction, note that $2^{k-2}$ divides $f(n+2^{k-1}) - f(n)$ and $f(n+2^{k}) - f(n+2^{k-1})$ by induction, but $2^{k-1}$ doesn't by problem statement. So it must divide their sum, as claimed. $\square$ So now say $\frac{f(n+2^k) - f(n)}{2^{k-1}}$ equals $\ell$ for some sufficiently large $k$. Note that $f(n+2^k) - f(n)$ is bounded between $c \cdot 2^k - 4046$ and $c \cdot 2^k + 4046$. So dividing by $2^{k-1}$ gives $2c - \frac{4046}{2^{k-1}} \leqslant \ell \leqslant 2c + \frac{4046}{2^{k-1}}$. Taking $k$ to be sufficiently large forces $2c$ to be an integer. Now assume $c$ is an integer and let $g(x) = f(x) - cx$, then the condition says $g$ is bounded and $a \nmid g(x+a) - g(x)$, impossible since you can pick $g(x) = g(x+a)$ with $a \geqslant 2$. So $c$ must be half an odd integer, as claimed. $\blacksquare$

bro the title Imfao this problem is highly motivated by equality case, prolly will fill in this later with a good writeup

My problem This came out of an attempt to classify all functions that satisfy the first condition (which is motivated by the question "how unlike a polynomial can a function be?"). I haven't made much progress on this original question; in fact, I'm increasingly convinced the solution set is extremely unwieldy. Anyone who manages to make any progress on this or find a decent-looking characterization of such functions will have my undying gratitude.

Very very nice problem Sutanay.

The answer is $c = n +\frac 12$ for all nonnegative integers $n$. Surprisingly tricky. To see that these work, consider the function $$f(x) = \begin{cases} \left(n+\frac 12\right) x & x \text{ even} \\ \left(n+\frac 12\right)x - \frac 12 & x \text{ odd.} \end{cases}$$This function obviously satisfies the second condition, and furthermore, $$\frac{f(x+a)-f(x)}a = n+\frac 12 \pm \frac 1{2a}$$for some choice of sign. As $a \geq 2$, this can never be an integer. To see that these are the only solutions, we have the following: Claim. $2^n \mid f(x+2^{n+1}) - f(x)$ for all positive integers $n$. Proof. By induction. Note that $2^{n+1}$ cannot divide the expression by the claim, so we have $$\nu_2(f(x+2^{n+2}) - f(x)) = \nu_2(f(x+2^{n+1}) - f(x)) + 1 = n+1. \ \blacksquare$$ Now fix $f(1) = n$. For large $N$, we have $f(2^N + 1) \equiv n \pmod {2^{N-1}}$ and thus $ f(2^N + 1)$ is in fact fixed. In particular, we there must be such a number in the range $[c \cdot 2^N + c - 2023, c \cdot 2^N + c + 2023]$. However, by the condition on $f(1)$, we also have $$n \in [c-2023, c+2023].$$For these to overlap, $$\left|c \cdot 2^N \bmod {2^{N-1}}\right|<4046. \iff \{2c\} < \frac{4046}{2^{N-1}}.$$Taking the limit as $N \to \infty$, $\{2c\} = 0$. Yet $c$ cannot be an integer, otherwise $2^N \mid f(2^N + 1) - f(1)$. Thus all desired $c$ are described above.

Answer: $\frac{1}{2} + k$ for any nonnegative integer $k$. Firstly, we'll show that there exists nonnegative integer $k$ such that $c = \frac{1}{2} + k$. Consider the following claim: Claim: $\nu_2(f(x+2^k) - f(x)) = k-1$ for every $x \in \mathbb{N}$ Proof. We'll proceed induction on $k$. Base case is clear. For induction step, note that $\nu_2(f(x+2^{k-1}) - f(x)) = k-2$ and $\nu_2(f(x+2^k) - f(x+2^{k-1})) = k-2$, hence $\nu_2(f(x+2^{k-1}) - f(x)) \ge k-1$. If $\nu_2(f(x+2^k) - f(x)) \ge k$, then we have $2^k \mid f(x+2^k) - f(x)$, a contradiction. $\blacksquare$ Now note that $f(1+2^k) = f(1) + 2^{k-1}(2s+1)$ for some $s \ge 0$. Then we have $|f(1+2^k) - c(1+2^k)| < 2023$, which means $|2^{k-1}(2s+1 - 2c) + f(1) - c| < 2023$. Hence $2c = 2s+1$, which means $c = s + \frac{1}{2}$. Now let $f(2n) = 2nk + n$ and $f(2n-1) = n + (2n-1)k$. Then $c = \frac{1}{2} + k$ works. $\blacksquare$

Answer is $n+\frac12$ for integers $n.$ Replace $|f(x)-cx|<2023$ with $|f(x)-cx|$ is bounded. We see that if there exists a $c$ with $0\le c<1$ and a function $f$ then the function $g(x)=f(x)+nx$ achieves all $n+c$ (this part works in both the original and our restated version), similarly if there exists any $c$ and function $f$ then the function $g(x-k)=f(x)-\lfloor c\rfloor x$ for $k$ chosen so that $g$ is always positive works and achieves $\{c\}.$ Thus we need only consider the $0\le c<1$ case. To construct $c=\frac12$ take $f(x)=\left\lceil\frac n2\right\rceil,$ it is easy to check that this works. Now the claim is that $f(2i)$ for $1\le i\le 2^n$ leave distinct remainders $\pmod{2^n},$ and furthermore we have $f(2(i+2^n))\equiv f(2i)\pmod{2^n}$ for all positive integers $n.$ We show this by induction. The base case $n=1$ is clear. Now suppose it holds for $n=k.$ By our assumption we have $f(2(i+2^k))\equiv f(2i)\pmod{2^k}$ but from our condition we must have $f(2(i+2^k))\not\equiv f(2i)\pmod{2^{k+1}},$ this finishes the first part. For the second part notice $f(2(i+2^{k+1}))\equiv f(2i)\pmod{2^k}$ by the assumption, but $f(2(i+2^{k+1}))\not\equiv f(2(i+2^k))\not\equiv f(2i)\pmod{2^{k+1}}.$ Thus the claim is proved. Now suppose $|f(x)-cx|<z$ for $c<1$ and some $z.$ Then $f(x)<cx+z.$ Then for large enough $x$ we have $f(x)<x.$ For each positive integer $i,$ define $x_i$ as the minimum $x$ such that $f(2x_i)\equiv 0\pmod{2^i}.$ From our claim, we see that $x_i\le 2^i.$ Furthermore it is clear that no integer can equal infinitely many $x_i,$ and clearly $x_i$ are nondecreasing. Thus for large enough $i$ we have large enough $x_i$ and we have $f(2x_i)<2x_i\le 2^{i+1}$ and so we must have $f(2x_i)=2^i.$ From our original claim we see that $x_{i+1}=x_i$ or $x_i+2^i.$ As before we see that the second case must occur infinitely many times. Take one such $x_k$ large enough such that $x_{k+1}=x_k+2^k.$ We then have $f(2x_k)=2^k,f(2x_k+2^{k+1})=2^{k+1}.$ We have $cx-z<f(x)<cx+z.$ First if $c<\frac12$ we see $2^k=f(2x_k)>2cx_k-z$ and $2^{k+1}=f(2x_k+2^{k+1})<2cx_k+c2^{k+1}+z$ and subtracting these gives $c2^{k+1}+2z>2^k,$ contradiction for large enough $k.$ Similarly, if $c>\frac12$ we see $2^k=f(2x_k)<2cx_k+z$ and $2^{k+1}=f(2x_k+2^{k+1})>2cx_k+c2^{k+1}-z$ so again subtracting gives $c2^{k+1}-2z<2^k,$ contradiction for large enough $k$ again.

We claim that $c=n+\frac12$ are the only valid solutions, where $n$ is a nonnegative integer Claim: We have $f(x+2^k)-f(x)\equiv 2^{k-1}\pmod{2^k}$ for every $x,k\in\mathbb{N}$. Proof. We induct on $k$. Base case is trivial by first condition taking $a=2$. Note that \[f(x+2^k)-f(x)\equiv 2^{k-1}\equiv f(x+2^{k+1})-f(x+2^k)\pmod{2^k}\Longrightarrow f(x+2^{k+1})-f(x)\equiv2^k\equiv0\pmod{2^k}.\]So, $2^k\mid f(x+2^{k+1})-f(x)$, but $2^{k+1}\nmid f(x+2^{k+1})-f(x)$, which gives $f(x+2^{k+1})-f(x)\equiv 2^k\pmod{2^{k+1}}$. The induction is complete. Note that this means for each $x,k\in\mathbb{N}$, we have $f(x+2^k)-f(x)=2^kq+2^{k-1}=2^{k-1}(2q+1),$ where $q$ is an integer. We have $f(x+2^k)-c(x+2^k)=f(x)-cx+2^{k-1}(2q+1-2c)$. Since $q$ is an integer, for sufficiently large $k$, we have that $|f(x+2^k)-c(x+2^k)|$ is not bounded, unless $2q+1-2c=0$. Hence, $c=q+\frac12$ is forced. So, value of $q$ is same for all sufficiently large $x,k$, and $\{c\}=\frac12$, as claimed. Construction: For $\{c\}=\frac 12$ we have $f(x)=322+\lfloor cx \rfloor$.

I claim $c$ can only be $n+\frac{1}{2}$. When $c$ is $n+\frac{1}{2}$, $f(x)=(c-\frac{1}{2})x+\lfloor\frac{x}{2}\rfloor$ works. Now suppose $c$ is not one of those values. Clearly we can see that if a function $f$ works, $2^n\nmid f(x+2^n)-f(x)$, thus we get by induction that $2^{n-1}\mid f(x+2^n)-f(x)$, now as $c$ is not of any of those forms by taking a large enough power of $2$ we can make it so a value $m$ such that $\nu_2(m)=n-1$ is not within the range of possible values of $f(x+2^n)-f(x)$, thus this is a contradiction.

Condition $(b)$ is equivalent to $f$ being bounded (Only hint I took from #2). Observe that $f(x)=\lfloor cx\rfloor+1$ always works. $\textsf{\textbf{Claim.}}$ $\nu_2(f(x+2^k)-f(x))=k-1$

In condition $(b)$ we replace $x\to x+2^k$ (motivation[hide]this is also what we do in the induction of the above claim, that is why it is motivated[/hide]) to get the $|f(x+2^k)-c(x+2^k)|<2023$, subtracting it with $|f(x)-cx|<2023$ we get (motivation

)$$-4046<\underbrace{f(x+2^k)-f(x)-c\cdot 2^k}_{\nu_2\;\text{of this will be}\; k-1}<4046$$As $k$ gets sufficiently large we get $(2n+1)-2c=0\implies c=\tfrac{2n+1}{2}$, where $n\in \mathbb{N}$.