$f(n)= \left\lfloor \frac{an+b}{cn+d} \right\rfloor , \forall n \in \mathbb N$ is surjective

Question

Let $a,b,c,d \in \mathbb N , d \ne 0$ and consider the funtion $f: \mathbb N \rightarrow \mathbb N $ such that : $$f(n)=\left \lfloor \frac{an+b}{cn+d}\right \rfloor , \forall n \in \mathbb N$$ Prove that $(c=0 , b < d , 0 < a \le d) \implies f$ is a surjective function

I tried to solve this Olympiad problem by myself. My solution is totally different from the one presented by the author, so it is difficult for me to self-evaluate. Can you please tell me if the solution below is complete and correct? And if you can give it a score from 0 to 7? Thanks !

My attempt :

Let's consider $c=0, b < d , 0 < a \le d$ , so the function becomes $f(n)=\left \lfloor \frac{an+b}{d}\right \rfloor , \forall n \in \mathbb N$ . Let $k \in \mathbb N$ such that $ f(n)=k \implies$ $$ \implies k = \left\lfloor \frac{an+b}{d}\right \rfloor \implies $$ $$\implies k \le \frac{an+b}{d} < k +1 \implies$$ $$ \implies kd \le an+b < kd + d \implies $$ (we can devide by $a$ since $a > 0$ ) $$\implies \frac{kd-b}{a} \le n < \frac{kd-b+d}{a} $$ Now I will prove that $n = \lfloor \frac{kd-b}{a} \rfloor + 1 $ checks the condition above. First , from the definition of the floor function it is obvious that $\lfloor \frac{kd-b}{a} \rfloor + 1 > \frac{kd-b}{a}$.Second , $\lfloor \frac{kd-b}{a} \rfloor + 1 \le \frac{kd-b}{a}+1 = \frac{kd-b+a}{a} < \frac{kd-b+d}{a}$. (COMMENT the inequality is strict because otherwise we would have $d=a$ and $kd-b$ is divisible by $a$ $\implies$ $b$ is divisible by $a$ but $b \le d = a \implies b = a $ , but $ b < d \implies$ false )

So I proved that for an arbitrarily chosen $k \in \mathbb N$, there is an $n$ such that $f(n)=k \implies \forall k \in \mathbb N , \exists n = \lfloor \frac{kd-b}{a} \rfloor + 1 \in \mathbb N$ such that $f(n)=k \implies f$ is a surjective function.

Answer 1

Your solution is correct but your argument for the strict inequality is a bit unclear. I'd rather say: let $u:=\frac{kd-b}a$ and $n:=\lfloor u\rfloor+1$. Then, $$n\le u+1\le u+\frac da$$ and $n=u+\frac da$ is impossible because if it were the case, we would have $d=a$ and $$\frac bd=k-n+1\in\Bbb Z,$$ which is absurd since $0\le\frac bd<1$.

Edit1. After reading this answer, you improved well your argument for the strict inequality. I still find mine clearer.

Edit2. I won't score your proof.

Answer 2

A clearer, but non-constructive, proof is to show:

1. $f(0)=0,$
2. $f(n+1)\leq f(n)+1,$ and
3. $f(n)$ is unbounded above.

All of these are easy to prove.

Then we can show any function $f:\mathbb N\to\mathbb N$ which satisfies (1.), (2.), and (3.) is surjective.

Assume $m\in\mathbb N.$

If $m=0$ then $f(0)=0.$

If $m>0,$ let $S=\{n\in\mathbb N\mid f(n)\geq m\}.$ By (3.) $f$ is not bounded above, $S$ is not empty.

Let $n$ be the least element of $S.$

Then, since $m>0,$ $n>0,$ and $n-1\notin S,$ since $n$ is the least element of $S.$ So $f(n-1)<m$ and by (2.), $m\leq f(n)\leq f(n-1)+1<m+1.$ So $f(n)=m.$

---

We can make this constructive in your case, because we can construct $n_0$ such that $f(n_0)\geq m$ and then just check all the values $f(n)$ for all $n\leq n_0.$

Here, $n_0=dm$ then $f(n_0)=\left\lfloor ma+\frac{b}d\right\rfloor =ma\geq m.$

So this proof is constructive if property (3.) is constructive - that is, if there is a constructive function $g$ such that $f(g(m))\geq m$ for all $m.$

---

Overkill

We get a stronger result, if $g:\mathbb N\to\mathbb R^{\geq 0}$ is unbounded above such that $0\leq g(0)<1$ and $g(n+1)-g(n)\leq 1$ for all $n,$ then $f(n)=\lfloor g(n)\rfloor$ is a surjective function $\mathbb N\to\mathbb N.$

The well-ordering proof doesn't require $f$ to be increasing, just unbounded above and never increasing by more than $1.$

This is because we can always get bigger than $m,$ and if we can only increase at most by $1$ at a time, we must eventually hit $m.$

---

We can go further, and note if we only know $(2.),$ then if $n_1<n_2$ and $f(n_1)\leq m\leq f(n_2)$ then $m=f(n)$ for some $n_1\leq n\leq n_1.$

If we know $(1.)$ and $(2.),$ we know that the range must be either all natural numbers $\leq M$ for some $M,$ or the range must be all of $\mathbb N.$

But if we add $(3.),$ $f$ is unbounded, then the former case isn't possible, so the range must be all of $\mathbb N.$