« Vrati se
U nekim se zadacima susrećemo sa sustavom koji se mijenja po određenim pravilima. U takvim je zadacima ćesto korisno potražiti neku veličinu koju ta pravila ne mijenjaju. Takvu veličinu, koju se ne mijenja nikakvom dozvoljenom promjenom sustava, zovemo invarijantp,.
Česti primjeri invarijanti su: ostatak koji suma daje pri djeljenju s n za neki prirodni n ili, primjerice, njihov umnožak.

Primjer zadatka i zapisa rješenja:
Neka su dozvoljeni koraci promjene uređenog para (x,y)
\bullet (x,y) \rightarrow \left( \dfrac{1}{3}x + \dfrac{4}{5}y,\dfrac{2}{3}x+\dfrac{1}{5}y \right)
\bullet (x,y) \rightarrow (y,x)
(Dakle, primjenjujući prvi korak na (2,1) dobivamo \left( \dfrac{1}{3}\cdot 2+\dfrac{4}{5}\cdot 1,\dfrac{2}{3}+\cdot 2\dfrac{1}{5}\cdot 1 \right) što je jednako \left( \dfrac{22}{15},\dfrac{23}{15} \right). Sada možemo, na primjer primjeniti drugi dozvoljeni korak i dobiti \left( \dfrac{23}{15},\dfrac{22}{15} \right), pa opet možemo primjeniti prvi, i tako dalje.)

Pitanje: Možemo li od brojeva (2,7) doći do (4,3)?

Rješenje:
Primjetimo da u oba moguća koraka (promjene) prije i nakon promjene imamo istu sumu uređenog para. To jest primjetimo da:
x+y=\dfrac{1}{3}x+\dfrac{4}{5}y+\dfrac{2}{3}x+\dfrac{1}{5}y
x+y=x+y
i
x+y=y+x

Dakle, što god mi radili, suma uređenog para se neće promijeniti. Suma para od kojeg počinjemo je 2+7=9, a moramo doći do 4+3=7. Kako 7 \neq 9, vidimo da to nije moguće.

Slični zadaci