Školsko natjecanje 2023., 3. razred SŠ, A varijanta, 6. Zadatak
Na početku je zadan prirodan broj . Jurica odabire dva prirodna broja i čiji je umnožak broj , a zatim ponavlja postupak s brojem umjesto .
Odredi, u ovisnosti o broju , najmanji mogući prirodan broj koji Jurica može dobiti kao rezultat nakon konačno mnogo koraka.
Rješenje
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 postoje takvi da je , te vrijedi . No, prema A–G nejednakosti imamo
č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 , ), mijenjamo ga brojem ; ako se na ploči nalazi neparan broj (oblika , ), mijenjamo ga brojem , a zatim brojem .
Ako je broj paran, vrijedi uz , pa je
Ako je broj neparan, vrijedi uz , pa je
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 , najmanji prirodan broj koji Jurica može dobiti na ploči je 5.
Pogledajmo što se događa u slučaju kada je .
Ako je u nekom koraku na ploči broj na ploči prost ili jednak 1, broj koji će biti zapisan u sljedećem koraku nužno je jednak .
Zato ako je , 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 , u prvom koraku možemo dobiti broj ili . 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 , u prvom koraku možemo dobiti samo broj . 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 .
Zato konačno imamo:
- ako je : najmanji broj koji može pisati na ploči iznosi ;
- ako je : najmanji broj koji može pisati na ploči iznosi 4;
- ako je : najmanji broj koji može pisati na ploči iznosi 5.
Napomena: Analiza slučajeva ne može biti potpuna bez dokaza tvrdnje da ako se na ploči nađe broj veći od da se na ploči više nikad neće naći broj manji od (ili neke slične tvrdnje). Zato nepotpuna rješenja treba bodovati na sljedeći način:
- slutnja točnih rješenja za slučajeve bez ikojeg dijela dokaza nosi bod (odgovara zadnjem bodu gornje bodovne sheme);
- slutnja točnih rješenja za slučajeve uz analizu da će Jurica u tim slučajevima na ploči u nekom trenutku dobiti broj , nakon kojeg može dobiti ili nosi boda (koji odgovaraju zadnjim dvama bodovima bodovne sheme);
- iskazana tvrdnja da broj veći od nikad neće moći biti zamijenjen brojem manjim od , te potpun dokaz za slučajeve nosi boda (odgovaraju prvom bodu te zadnjim dvama bodovima gornje bodovne sheme).