5. Zadatak

Prvo rješenje.

Žana se zaustavila na udaljenosti $(m-n)n$ od ishodišta.

Kako su $m$ i $n$ relativno prosti, Žana će prvi put čuti obje zapovijedi odjednom nakon $mn$ koraka.

Nazovimo periodom Žanine korake između $i$-te i $(i+1)$-te Linine zapovijedi (za neki prirodan broj $i$). Kako je $m>n$, u svakom periodu bit će izdana najviše jedna Dinina zapovijed.

Za neki $k$ promotrimo periode u kojima je Dina dala $k$-tu i $(n-k)$-tu zapovijed.

Do Dinine $k$-te zapovijedi prošlo je $mk$ koraka od početka, dok je njezina $(n-k)$-ta zapovijed bila izdana $mk$ koraka prije kraja Žaninog putovanja. Dakle, te dvije zapovijedi bile su izdane simetrično u odnosu na Žanino putovanje.

Slično, ako je Dinina $k$-ta zapovijed izdana nakon $i$-te Linine zapovijedi, Dinina $(n-k)$-ta zapovijed izdana je prije $(m-i)$-te Linine zapovijedi. Zaključujemo da su Žanini koraci izvršeni u periodima u kojima su izvršene $k$-ta i $(n-k)$-ta Dinina zapovijed simetrični, pa se ukupno dokidaju: u ta dva perioda Žana je napravila ukupno $n$ koraka ulijevo i $n$ koraka udesno.

Stoga je Žanina udaljenost od ishodišta određena isključivo periodima u kojima nema Dininih zapovijedi.

Prije zaustavljanja proći će $(m-1)$ period u kojima će Dina dati $(n-1)$ zapovijed (ne brojeći zapovijedi u $(mn)$-tom koraku). U svakom periodu Dina je izdala najviše jednu zapovijed. Zaključujemo da je u $n-1$ perioda izdala jednu zapovijed, a u $m-n$ perioda nije izdala nijednu zapovijed.

U svakom od tih $m-n$ perioda bez Dinine zapovijedi Žana je napravila $n$ koraka ulijevo, pa je konačna Žanina udaljenost od ishodišta jednaka $(m-n)n$.

Drugo rješenje.

Kao u prošlom rješenju tvrdimo da je odgovor $(m-n)n$, te zaključujemo da Žana staje nakon $mn$ koraka.

Za prirodne brojeve $a$ i $b$ neka $o(a,b)$ označava ostatak pri dijeljenju broja $a$ brojem $b$.

Tvrdimo da je svaki broj $k$ iz skupa koraka $S:=\{0,1,\ldots,nm-1\}$ na jedinstven način određen uređenim parom ostataka tog broja pri dijeljenju s $n$ i $m$:

$$(o(k,n),o(k,m))\in S_2:=\{0,1,\ldots,n-1\}\times\{0,1,\ldots,m-1\}.$$

Kako je veličina skupa $S$ jednaka broju veličini skupa $S_2$, dovoljno je pokazati da ne postoje dva različita broja $k_1$, $k_2$ iz $S$ koja daju isti uređeni par iz $S_2$. U suprotnom, njihova razlika $k_1-k_2$ davala bi ostatak $0$ pri dijeljenju i s $m$ i s $n$, pa bi bila djeljiva s $mn$, no najveća apsolutna razlika dvaju elemenata iz skupa $S$ je $mn-1$.

Dokazat ćemo sljedeću tvrdnju: nakon $k$-tog koraka, Žana ostaje na mjestu ako je $o(k,m)=o(k,n)$, Žana se pomiče ulijevo ako je $o(k,n)<o(k,m)$, te se pomiče udesno ako je $o(k,n)>o(k,m)$.

Ako se brojevi $o(k,n)$ i $o(k,m)$ razlikuju, Žana se pomiče prema onoj zapovijedi koju je čula prije manjeg broja koraka. Lininu naredbu čula je prije $o(k,n)$ koraka, a Dininu naredbu čula je prije $o(k,m)$ koraka, što dokazuje gornju tvrdnju u slučaju kada je $o(k,n)$ i $o(k,m)$ razlikuju.

Žana stoji na mjestu prvih $n$ koraka. Za tih prvih $n$ koraka vrijedi $o(k,n)=o(k,m)$ (gdje je $k\in\{0,\ldots,n-1\}$). S druge strane broj brojeva $k$ koji zadovoljavaju $o(k,n)=o(k,m)$ je točno $n$. Zaključujemo da oni odgovaraju točno prvih $n$ koraka, pa je i taj dio tvrdnje dokazan.

Zato je konačna udaljenost Žane od ishodišta jednaka apsolutnoj razlici broja uređenih parova iz $S_2$ u kojima je prva koordinata veća od druge i broj parova u kojima je druga koordinata veća od druge.

Svi uređeni parovi $(i,j)\in S_2$ takvi da je $j<i$ posebno zadovoljavaju da su obje koordinate manje od $n$, stoga je broj takvih parova jednak broju uređenih parova $(j,i)\in S_2$ takvih da je $j<i<n$.

Zato je tražena apsolutna razlika jednaka broju uređenih parova $(i,j)\in S_2$ takvih da je $i<j$, te $j\geq n$. U tom slučaju $i$ može poprimiti bilo koju vrijednost iz skupa $\{0,1,\ldots,n-1\}$, a $j$ bilo koju vrijednost iz skupa $\{n,n+1,\ldots,m-1\}$. Takvih parova je $(m-n)n$, pa toliko iznosi i konačna Žanina udaljenost od ishodišta.