5. Zadatak

Neka je $a_n$ mjesto na kojem se skakavac nalazi nakon $n$-tog skoka, odnosno

$$a_1=1,\qquad a_n=1+k+\cdots+k^{n-1},\quad n\ge2.$$

Tražimo sve prirodne brojeve $k$ takve da $2015\nmid a_n$ za sve $n=1,\ldots,2015$.

Pretpostavimo da je $M(k,2015)=d>1$. Tada svaki $a_n$ pri dijeljenju s $d$ daje ostatak 1, a kako je 2015 djeljivo s $d$ vrijedi $2015\nmid a_n$ za sve $n$. Dakle, svi prirodni brojevi koji nisu relativno prosti s 2015 odgovaraju uvjetima zadatka.

Ako je $M(k,2015)=1$, promatramo ostatke pri dijeljenju brojeva $a_1,\ldots,a_{2015}$ s 2015. Ako je neki od njih djeljiv s 2015, takav $k$ ne odgovara. U suprotnom, budući da imamo 2014 mogućih ostataka, dva broja daju isti ostatak. Neka su to $a_l$ i $a_m$, $m>l$. Tada je njihova razlika djeljiva s 2015. S druge strane, vrijedi

$$a_m-a_l=k^l+\cdots+k^{m-1}=k^l(1+\cdots+k^{m-l-1})=k^l\cdot a_{m-l}.$$

Iz $2015\mid k^l\cdot a_{m-l}$ i $M(k,2015)=1$, slijedi $2015\mid a_{m-l}$, što je suprotno pretpostavci da nijedan od brojeva $a_1,\ldots,a_{2015}$ nije djeljiv s 2015. Dakle, ako je $M(k,2015)=1$, skakavac će uskočiti u rupu.

Prema tome, jedini prirodni brojevi koji odgovaraju uvjetima zadatka su oni koji nisu relativno prosti s 2015.