5. Zadatak

Tvrdimo da je odgovor $3001$ skokova.

Označimo točke u smjeru kazaljke na satu brojevima $1,2,\ldots,3000$ krenuvši od točke u kojoj se skakavac nalazi na početku. Skakavac može stati na svaku točku barem jednom i vratiti se u točku iz koje je krenuo u $3001$ skokova ovako:

$$1\xrightarrow{3}4\xrightarrow{3}7\xrightarrow{3}\cdots\xrightarrow{3}2998\xrightarrow{2}3000\xrightarrow{3}3\xrightarrow{3}\cdots\xrightarrow{3}2997\xrightarrow{2}2999\xrightarrow{3}2\xrightarrow{3}\cdots\xrightarrow{3}2999\xrightarrow{2}1.$$

Pokažimo da skakavac to ne može učiniti u manje skokova. Neka je $k$ broj skokova duljine $2$, a $\ell$ broj skokova duljine $3$. Budući da se skakavac mora vratiti u točku iz koje je krenuo, tj. mora napraviti cijeli broj punih krugova, postoji prirodni broj $n$ takav da je

$$2k+3\ell=3000n.$$

Budući da skakavac mora stati na svaku označenu točku barem jednom, vrijedi

$$k+\ell\ge3000.$$

Kada bi vrijedilo $k+\ell=3000$, onda bi iz

$$3000n=2k+3\ell=2(k+\ell)+\ell=6000+\ell$$

slijedilo da $3000$ dijeli $\ell$. Budući da je $k,\ell\ge0$, moralo bi vrijediti $\ell=0$ ili $\ell=3000$. Slučaj $\ell=0$ značio bi da su svi skokovi duljine $2$, no tada skakavac ne bi stao na svaku označenu točku. Slučaj $\ell=3000$ značio bi da su svi skokovi duljine $3$ i tada skakavac također ne bi stao na svaku označenu točku. Dakle, nije moguće $k+\ell=3000$.