XX OBM

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+\cdots +2a_n+2a_{n+1}+a_n+1$ blocks until they reach their destination. So $2a_1+2a_2+\cdots +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+\cdots +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+\cdots +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{c{v}_{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}}⟹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)}$.