Vietnamese Mathematical Competitions

We will prove that the required function $f_0$ is $g(n) = \lceil \log_2 |n| \rceil + 1$.

(1) We prove that if $g(n) = \lceil \log_2 |n| \rceil + 1$ then $g(n) \in F$.
Consider numbers $a, b \in \mathbb{Z} \setminus \{0\}$ and $a$ is not divisible by $b$. Assume that $r', s'$ are integers such that $a = br' + s'$ with $0 < s' < |b|$.
If $s' < \frac{|b|}{2}$ then we choose $r = r', s = s'$.
If $s' \ge \frac{|b|}{2}$ then we choose $r = r' \pm 1, s = s' - |b|$.
Therefore for all $a, b$ we always have $a = br + s$ with $|s| \le \frac{|b|}{2}$. In this case $g(s) \le g(b) - 1$.
It means that we have $a = br + s$ with $g(b) > g(s)$, which satisfies the required condition.

(2) Let $f_0(n) = \min f(n)$ for all $n$; We prove that $f_0 \in F$.
For all $a, b$ there exists $f$ such that $f_0(b) = f(b)$. We write $a$ in the form $a = br + s$.
Since $f(s) < f(b)$ we have $f_0(s) \le f(s) < f(b) = f_0(b)$, therefore $f_0 \in F$.

(3) We will prove that $f_0(n) = g(n)$.
For $n = \pm 1$, we have $g(n) \ge f_0(n) \ge 1 = g(1) \Rightarrow g(n) = f_0(n)$.
Assume that there exists $n$ for which $f_0(n) < g(n)$. We choose such $n$ for which $f_0(n)$ is minimum and $f_0(n) < g(n)$. It is clear that $n \ne \pm 1$.
Assume that $r, s$ are integers such that $f_0(s) < f_0(n)$ and $a = br + s$. Since $f_0(s) < f_0(n)$ then $f_0(s) = g(s)$ for all $s$ with $|s| > \lfloor \frac{|n|}{2} \rfloor$, $g(s) \ge g(n) - 1$, therefore $g(n) > f_0(n) > g(n) - 1$, which is absurd.
So, the required function $f_0$ is $f_0(n) = \lceil \log_2 |n| \rceil + 1$.