3. Zadatak

Odgovor je $3001$.

Prvo dokažimo da muha u $3001$ skokova može obići sve točke. Označimo točke u smjeru kazaljke na satu s $0,1,2,\ldots,2999$ tako da je početna točka $0$. Tada možemo prvo $999$ puta skočiti za $3$ mjesta od $0$ do $3$, od $3$ do $6$, $\ldots$, od $2994$ do $2997$. Zatim skočimo za $2$ mjesta od $2997$ do $2999$.

Nakon toga $999$ puta skočimo za $3$ mjesta od $2999$ do $2$, od $2$ do $5$, $\ldots$, od $2993$ do $2996$. Zatim skočimo za $2$ mjesta od $2996$ do $2998$.

Nakon toga $999$ puta skočimo za $3$ mjesta od $2998$ do $1$, od $1$ do $4$, $\ldots$, od $2992$ do $2995$. Zatim u sljedeća dva skoka skočimo do $2997$ pa do $0$.

Ukupno smo skočili

$$999+1+999+1+999+2=3001$$

puta.

Dokažimo da ne možemo u $3000$ ili manje skokova obići svaku točku i vratiti se u početnu. U svakom slučaju trebamo barem $3000$ skokova jer u svakoj točki treba završiti barem jedan skok.

Pretpostavimo da možemo u točno $3000$ skokova obići svaku točku i vratiti se. Neka je $a$ broj skokova duljine $2$ i $b$ broj skokova duljine $3$ koje smo napravili. Vrijedi $a+b=3000$.

Brojevi $a$ i $b$ ne mogu biti jednaki $0$ – kad bi bilo $b=0$ tada bi svaki skok bio duljine $2$ i skakali bismo samo po točkama s parnim oznakama, a kad bi bilo $a=0$ tada bi svaki skok bio duljine $3$ i skakali bismo samo po točkama s oznakama djeljivim s $3$.

Neka je $k$ ukupan broj krugova koje smo napravili. Tada je

$$2a+3b=3000k.$$

Kako su $a$ i $b$ veći od $0$, slijedi

$$6000=2\cdot(a+b)<2a+3b=3000k,$$

pa je $k>2$.

S druge strane,

$$9000=3\cdot(a+b)>2a+3b=3000k,$$

pa je $k<3$.

Dakle, $2<k<3$ što je nemoguće.