Rješenja zadatka "1 - Invarijante 10." korisnika "Veki"

Točno

29. listopada 2013. 16:29 (10 godine, 6 mjeseci)
Sakrij rješenje

Korisnik: Veki
Zadatak: 1 - Invarijante 10. (Sakrij tekst zadatka)

Na uređeni par $(x,y)$ možemo primjeniti sljedeće promjene:
$\bullet (x,y) \rightarrow (2x+3y,y-x)$
$\bullet (x,y) \rightarrow (x-5y,6y-9x)$
$\bullet (x,y) \rightarrow (y,x)$
Poševši od para $(3,6)$ , možemo li dobiti $(4,3)$ ?

Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.

Pokusajmo ponovo pronaci $n$ takav da je suma modulo $n$ invarijantna.
$x+y \equiv 2x+3y+y-x \pmod n$
$x+y \equiv x+4y \pmod n$
$3y \equiv 0 \pmod n$
Kako ovo mora vrjediti za sve $y$ , znamo da $n|3$ . Pa promotrimo dali je i druga promjena invarijantna modulo $3$ .
$x+y \equiv x-5y+6y-9x \pmod 3$
$x+y \equiv x - 2y \pmod 3$
$x+y \equiv x+y \pmod 3$
Kako svi moguci koraci ostavljaju sumu invarijantnu mod $3$ , potrebno je jos samo provjeriti pocetni i zavrsni par koji smo dobili. Na pocetku je suma djeljiva s $3$ , a na kraju daje ostatak $1$ pri djeljenju s $3$ . Dakle, nemoguce je.

Ocjene: (1)

Komentari:

helen1c, 18. srpnja 2016. 16:14

Je li se može druga promjena uraditi da se dokaze invarijanta mod9, i onda n|9 i n|3 pa je n=3 ili n=1 , tj. n=3 ? :D

Zadnja promjena: helen1c, 18. srpnja 2016. 16:15

Školjka

Ocjene: (1)

Komentari: