What the heck? This is a well-known problem -_- It's in Amir Hossein's collection of 1220 number theory problems most likely... Instead of regurgitating a proof from memory, I'll go search for the sources where I originally saw this problem to back up this "well-known" claim. EDIT : Aha I am mistaken. However, the problem is extremely similar to a lemma in the chapter about analysis applying to number theory in Problems from the Book, and is a *fairly* well-known result. The proof is essentially identical, so I dislike the CGMO of using this problem...

I'll note that if you just plot the lines $y=\frac{x}{k+1}$ and $y=\frac{x}{k}$ for some $k$ on a coordinate grid, the result becomes blatantly obvious. (You consider the sequence of points $(n, a_n)$ as $n = 1, 2, \dots$.)

My solution: Suppose that such a $s$ doesn't exist.We know $a_k\ge 2.$ (If $a_k=1$ for some $k,$ then $\frac{k}{a_k}=k$ contradicting our assumption) We will now prove by induction to $i$ that $a_{ik}\ge i+1.$ We know this assumption is true for $i=1,$ and we know $a_{ik}\ge i+1.$ Then we know $$a_{(i+1)k}\ge^{1} a_{ik}=i+1,$$(in $1$ we use nondecreasing condition). If$a_{(i+1)k}=i+1\to \frac{(i+1)k}{a_{(i+1)k}}=k$ a contradiction. Then $a_{(i+1)k}\ge i+2.$ as desired. Let $i=a_r,$ then $a_{(a_r)k}\ge a_r+1.$ Also from condition $a_r(k+1)=r,$ then $a_r=a_{(a_r)(k+1)}\ge a_{(a_r)k}\ge a_r+1.$ But this is a contradiction.Then our assumption is wrong.