Since the mathematicians didn't know which side and at what distance their destination was, they should adopt the following strategy: walk $a_1$ blocks on one side (say, left), then go back to the starting point and walk $a_2$ blocks to the right, then go back again and walk $a_3$ blocks to the left, and so on, with $a_1 < a_3 < a_5 < \dots$ and $a_2 < a_4 < a_6 < \dots$ until they find their destination. The worst cases happen when the destination is $a_{2k+1} + 1$ blocks to the left or $a_{2k} + 1$ blocks to the right.
In these cases, there are $a_n + 1$ blocks between the starting point and the destination and the mathematicians walk a total of $2a_1 + 2a_2 + \dots + 2a_n + 2a_{n+1} + a_n + 1$ blocks until they reach their destination. So $2a_1 + 2a_2 + \dots + 2a_n + 2a_{n+1} + a_n \le k(a_n + 1)$ or $s_{n+1} \le \left(\frac{k-1}{2}\right)(a_n + 1)$ for all naturals $n$, where $s_t = a_1 + a_2 + \dots + a_t$.
For $k=9$ there are strategies satisfying the conditions of the problem: for example, consider $a_m = 2^m$. Notice that $s_{n+1} = 2^1 + 2^2 + \dots + 2^{n+1} = 2^{n+2} - 2 < 4(2^n + 1) = \left(\frac{k-1}{2}\right)(a_n + 1)$ for all naturals $n$.
Now we prove that $k$ cannot be less than 9. If $k < 9$ then $c = \frac{k-1}{2} < 4$. Since $a_n = s_n - s_{n-1}$ we have $s_{n+1} \le c(s_n - s_{n-1} + 1)$ for all naturals $n$. Let $u_n = s_n - c$ so that $u_{n+1} \le c(u_n - u_{n-1})$. Since $c < 4$, $u_n > 0$ for all $n \ge 3$ and if $v_n = \frac{u_{n+1}}{u_n}$ for $n \ge 3$, $v_n \le c\left(1 - \frac{1}{v_{n-1}}\right)$ for all $n \ge 4$ and $v_n - v_{n-1} \le c\left(1 - \frac{1}{v_{n-1}}\right) - v_{n-1} = \frac{cv_{n-1} - c - v_{n-1}^2 - 1}{v_{n-1}} = \frac{c^2/4 - c - (c/2 - v_{n-1})^2}{v_{n-1}} \le \frac{c(c-4)}{4v_{n-1}} < 0$, from which $v_n < v_{n-1}$ for all $n \ge 4$. On the other hand, for all $n \ge 4$ we have $v_n - v_{n-1} \le \frac{c(c-4)}{v_{n-1}} \implies v_n - v_{n-1} \le \frac{c(c-4)}{4v_3}$ for $n \ge 4$ and so $v_n \le v_3 + \frac{(n-3)c(c-4)}{4v_3}$ for all $n \ge 4$, a contradiction because the right hand side is negative for $n > 3 + \frac{4v_3^2}{c(4-c)}$.