Niezmienniki i półniezmienniki

[mol_ksiazkowy]

Niezmiennik (inwariant) - cecha lub właściwość, która jest stała (nie zmienia się) w trakcie przekształceń, procesów przemiany itp.

Półniezmiennik to zmienna która zawsze rośnie lub maleje i która przyjmuje skończoną ilość wartości.


Przykład (Zadanie o kameleonach)
Na planecie Centauri żyje \(\displaystyle{ 2015}\) kameleonów czerwonych, \(\displaystyle{ 2016}\) zielonych i \(\displaystyle{ 2017}\) żółtych. Jeśli dwa różnokolorowe kameleony spotykają się, to zamieniają swój kolor na kolor trzeci. Czy może dojść do tego że kiedyś wszystkie będą jednokolorowe ?

Rozwiązanie
Niezmiennikiem będzie zbiór reszt z ilości kameleonów każdego koloru modulo \(\displaystyle{ 3}\). Ze względu na konfigurację początkową i regułę zamiany koloru u kameleonów jest nim zbiór \(\displaystyle{ \{ 1, 2, 3 \}}\). (\(\displaystyle{ 3 \equiv 0}\)), co można przedstawić też symbolicznie: \(\displaystyle{ \{1, 2, 3 \} + \{x-1, y-1, z+2 \} \equiv \{1, 2, 3 \}}\). A więc wszystkie kameleony nie mogą być nigdy jednokolorowe, gdyż wtedy zbiór ten byłby jednoelementowym.


Zadanie o rycerzu i smoku
Smok ma 101 głów. Rycerz może mu ściąć jednym cięciem: 31 bądź 26, bądź jedną głowę. Wtedy smokowi odrasta odpowiednio: 43 bądź 8 bądź 67 głów. Czy rycerz może zabić smoka (tj. ściąć mu wszystkie głowy) ?

Rozwiązanie
Niezmiennikiem jest parzystość liczby głów. Jeśli w danej chwili smok ma \(\displaystyle{ m}\) głów, to po kolejnym ścięciu i regeneracji smoka jest ich:
\(\displaystyle{ m-31+ 43 = m+12}\) lub \(\displaystyle{ m-26+ 8 = m-18}\) lub też \(\displaystyle{ m-1+ 67= m+66}\); tj. zawsze nieparzysta ilość.
Smoka zabić się nie da (chyba że innymi metodami... ).

Czy gdyby smok miał 100 głów, to rycerz mógłby go zabić ?


Zadanie
Mamy \(\displaystyle{ X= \{ 3, 4, 12 \}}\) i jeśli jakieś \(\displaystyle{ a , b \in X}\) to można je zamienić na \(\displaystyle{ 0,6a -0,8b}\) i \(\displaystyle{ 0,8a +0,6b}\). Czy można zamienić przez takie zamiany \(\displaystyle{ X}\) na zbiór \(\displaystyle{ Y= \{ 4, 6, 12 \}}\) ?

Rozwiązanie (szkic)
Niezmiennikiem jest suma kwadratów
https://www.matematyka.pl/393381.htm


Zadanie
Na okręgu są rozmieszczone jest \(\displaystyle{ n}\) liczb. Jeśli liczby \(\displaystyle{ a, b, c, d}\) są obok siebie i w tej kolejności, oraz \(\displaystyle{ (a-d)(b-c) >0}\) to liczby \(\displaystyle{ b}\) i \(\displaystyle{ c}\) można zamienić miejscami. Udowodnić, że po skończonej ilości takich zamian następna będzie już niemożliwa.

Rozwiązanie
Półniezmiennikiem jest suma iloczynów trzech sąsiadów, gdyż jeśli (z założenia) \(\displaystyle{ ab+cd > ac+bd}\) to \(\displaystyle{ ab+bc+cd > ac+ cb + bd}\)


Problem
Mamy dane \(\displaystyle{ f (x)=x^2+4x+3}\) i \(\displaystyle{ g(x) = x^2+10x+9}\). Czy poprzez stosowanie przekształcenia \(\displaystyle{ f(x) \mapsto x^2 f(\frac{1}{x}+ 1)}\) lub \(\displaystyle{ f(x) \mapsto (x-1)^2 f( \frac{1}{x-1})}\) można zamienić \(\displaystyle{ f}\) na \(\displaystyle{ g}\) ?

Problem (wiewiórki na drzewach)
Na dziesięciu drzewach, rozmieszczonych współokręgowo jest dziesięć wiewiórek (po jednej na każdym drzewie). Co jakiś czas dwie wiewiórki przeskakują na sąsiednie drzewa. Czy wszystkie wiewiórki mogą zebrać się na jednym drzewie ?

Pytanie: Czy ilość wiewiórek (i drzew) ma znaczenie ?

Problem / Mix dla dociekliwych, zadanie 9
Na tablicy są liczby \(\displaystyle{ 0, 1, \sqrt{2}}\). Ruch polega na dodaniu do jednej z tych liczb różnicy dwóch pozostałych pomnożonej przez dowolną liczbę wymierną. Czy można w ten sposób otrzymać w końcu liczby \(\displaystyle{ 0, 2, \sqrt{2}}\) ?

wsk Każda z liczb jest w formie \(\displaystyle{ a+b\sqrt{2}}\), gdzie \(\displaystyle{ a}\) i \(\displaystyle{ b}\) są wymierne, a więc każdą taką trójkę można utożsamić z trójkątem.
Niezmiennikiem będzie pole takiego trójkąta.


Jest to zaledwie kilka prostych przykładów , które mogą być wprowadzeniem do tematu.
W wątku tym można przedstawiać różne ciekawe przykłady zadań, jakie można rozwiązać takimi metodami.
Niektóre z nich być może są też już na forum...