This is a problem in an Olympiad contest:
Let $F$ be the set of all functions $f\colon \mathbb{Z} \backslash \{0\} \to \mathbb{N}$ with the property: if $a, b\in \mathbb{Z} \backslash \{0\}$ and $b$ does not divide $a$, then there exists $r, s \in \mathbb{Z} \backslash \{0\}$ such that $a = br+s$ and $f(s) < f(b)$. Find the least function $f_0$ in $F$, i.e, $f_0(n) \le f(n)$ for all $n\in \mathbb{Z} \backslash \{0\}$ and for all $f\in F$.
Of course, the function defined by $$f_0(n) = \min_{f\in F} f(n), \quad \forall n\in \mathbb{Z} \backslash \{0\}$$
is the desired function, but the solution also gives the explicit form of $f_0$, which is $$f_0(n) = \lfloor \log_2 |n| \rfloor + 1, \quad \forall n \in \mathbb{Z} \backslash \{0\}.$$
Thus we have to prove that $$\min_{f\in F} f(n) = \lfloor \log_2 |n| \rfloor + 1, \quad \forall n\in \mathbb{Z} \backslash \{0\},$$
or there is no $n$ such that $\displaystyle \min_{f\in F} f(n) < \lfloor \log_2 |n| \rfloor + 1$. However, I'm stuck with this.
Thank you for any help.
Denote $f_0(n)=\min_{f\in F}f(n)$ and $f_1(n)=\lfloor\log_2|n|\rfloor+1$; directly can be checked that $f_0,f_1\in F$ and clearly $f_0(n)\leqslant f_1(n)$. It suffices to prove the claim: $f_0(n)\leqslant k$ iff $|n|<2^k$; then $f_0(n)=k+1$ exactly when $2^k\leqslant|n|<2^{k+1}$, i.e. exactly when $\lfloor\log_2|n|\rfloor= k$, so $f_0(n)=f_1(n)$.
The claim we can prove by induction on $k$. For $k=1$, we should prove $f_0(n)=1$ iff $n=\pm 1$. The ($\Leftarrow$) part follows since $f_0(n)\leqslant f_1(n)$ (I presume that we assume that $0\notin\mathbb N$; otherwise, the function $\lfloor\log_2|n|\rfloor$ is the smallest). For ($\Rightarrow$), since we cannot write $1=qn+r$ with $f_0(r)<f_0(n)$ because $f_0(n)=1$, $n$ must divide $1$.
Assume that $f_0(n)\leqslant k$ iff $|n|<2^k$ holds, and we prove $f_0(n)\leqslant k+1$ iff $|n|<2^{k+1}$. Again ($\Leftarrow$) follows since $f_0(n)\leqslant f_1(n)$. For $(\Rightarrow)$, by inductive hypothesis, we may assume $f_0(n)=k+1$. Write $2^k=qn+r$ with $f_0(r)<f_0(n)=k+1$, which by induction hypothesis implies $|r|<2^k$. So $0<2^k-r<2^{k+1}$, i.e. $0<qn<2^{k+1}$, which implies $|n|<2^{k+1}$.