6. Zadatak

Dokažimo sljedeću tvrdnju: ako se u nekom koraku na ploči nalazi broj koji je veći ili jednak 5, na ploči se nikad neće naći broj manji od 5.

Pretpostavimo suprotno, i promotrimo prvi trenutak u kojem se broj na ploči koji je veći ili jednak od 5 mijenja brojem manjim od 5. Za taj broj $m\ge5$ postoje $a,b\in\mathbb{N}$ takvi da je $ab=m\ge5$, te vrijedi $a+b\le4$. No, prema A–G nejednakosti imamo

$$4\ge a+b\ge2\sqrt{ab}\ge2\sqrt5,$$

čime dobivamo kontradikciju.

S druge strane, ako se na ploči nalazi broj veći od 5, postoji niz koraka kojim se na ploči može naći broj 5.

Algoritam koji provodimo je sljedeći: ako se na ploči nalazi paran broj (oblika $m=2k$, $k\in\mathbb{N}$), mijenjamo ga brojem $2+k$; ako se na ploči nalazi neparan broj (oblika $m=2k+1$, $k\in\mathbb{N}$), mijenjamo ga brojem $m+1=2k+2=2(k+1)$, a zatim brojem $(k+1)+2=k+3$.

Ako je broj $m>5$ paran, vrijedi $m=2k$ uz $k\ge3$, pa je

$$2k=k+k>k+2.$$

Ako je broj $m>5$ neparan, vrijedi $m=2k+1$ uz $k\ge3$, pa je

$$2k+1=k+k+1>k+2+1=k+3.$$

U oba slučaja, broj na ploči strogo veći od 5 u jednom ili dva koraka zamijenili smo brojem strogo manjim od tog broja.

Taj postupak možemo ponavljati dokle god se na ploči nalazi broj veći od 5. Kako time dobivamo sve manje prirodne brojeve, a ne možemo dobiti broj manji od 5, zaključujemo da će u nekom trenutku na ploči pisati broj 5.

Dakle, ako je na početku bio zadan broj $n>5$, najmanji prirodan broj koji Jurica može dobiti na ploči je 5.

Pogledajmo što se događa u slučaju kada je $n\le5$.

Ako je u nekom koraku na ploči broj $m$ na ploči prost ili jednak 1, broj koji će biti zapisan u sljedećem koraku nužno je jednak $m+1$.

Zato ako je $n=5$, u prvom koraku nužno dobivamo broj 6, ali to je broj veći od 5, pa prema gornjem dijelu dokaza najmanji broj koji možemo dobiti na ploči je broj 5.

Ako je $n=4$, u prvom koraku možemo dobiti broj $2+2=4$ ili $1+4=5$. Ako Jurica napiše broj 5, neće moći dobiti broj manji od 5. Stoga je najmanji broj koji Jurica u ovom slučaju može dobiti broj 4.

Ako je $n\le3$, u prvom koraku možemo dobiti samo broj $n+1$. Već u prvom koraku povećavamo broj koji se nalazi na ploči. Povećanje broja na ploči nastavlja se dok ne dođemo do broja 4, nakon kojeg iz gornje analize više ne možemo dobiti broj manji od 4. Zato u ovom slučaju najmanji Juričin rezultat je onaj koji dobije nakon prvog koraka, a to je $n+1$.

Zato konačno imamo:

• ako je $n\in\{1,2,3\}$: najmanji broj koji može pisati na ploči iznosi $n+1$;
• ako je $n=4$: najmanji broj koji može pisati na ploči iznosi 4;
• ako je $n\ge5$: najmanji broj koji može pisati na ploči iznosi 5.