W niektórych zadaniach nie trzeba sprawdzać wszystkich kolejności ruchów. Wystarczy znaleźć cechę, która nie zmienia się po żadnym dozwolonym ruchu, i porównać początek z celem. Taką cechę nazywamy niezmiennikiem. Jednym z najprostszych przykładów jest parzystość.
Najpierw zbadaj pojedynczy ruch
Na tablicy widnieje liczba 7. W jednym kroku wolno dodać lub odjąć 2. Czy można uzyskać 100? Nie: liczba nieparzysta po dodaniu lub odjęciu 2 pozostaje nieparzysta, a 100 jest parzyste. Nie potrzebujemy listy 7, 9, 11 i kolejnych wyników.
Dowód ma dwie części: wykazanie zachowania własności po dowolnym dozwolonym ruchu i wskazanie różnicy między stanem początkowym a docelowym. Samo zauważenie, że kilka pierwszych liczb jest nieparzystych, nie wystarcza.
Suma zamiast poszczególnych liczb
Mamy pięć żetonów, każdy z jedną jasną i jedną ciemną stroną. W jednym ruchu odwracamy dokładnie dwa żetony. Czy od ustawienia wszystkich jasną stroną w górę można przejść do dokładnie jednego ciemnego? Nie. Liczba widocznych ciemnych stron zmienia się o −2, 0 lub 2, więc pozostaje parzysta.
Zmiana o 0 występuje, gdy jeden jasny staje się ciemny, a jeden ciemny jasny. Warto uwzględnić wszystkie przypadki, zamiast założyć, że każdy ruch zwiększa liczbę ciemnych o 2.
Kolorowanie szachownicy
Z szachownicy 8 × 8 usunięto dwa przeciwległe narożniki. Czy resztę można pokryć prostokątnymi kostkami domina 1 × 2, bez nakładania i wystawania? Każde domino przykrywa jedno pole każdego koloru. Narożniki przeciwległe mają ten sam kolor, więc po ich usunięciu zostaje 30 pól jednego i 32 drugiego koloru. Pokrycie jest niemożliwe.
Obszar ma 62 pola, a więc parzystą powierzchnię. To konieczny, ale niewystarczający warunek. Kolorowanie daje mocniejszą informację niż samo dzielenie pola przez dwa. Podobnie liczenie możliwości wymaga rozpoznania ograniczeń, nie tylko wstawienia liczby do wzoru.
- Wypisz, jak zmienia się wybrana cecha w każdym rodzaju ruchu.
- Szukaj sumy, parzystości lub różnicy liczebności, jeśli pojedyncze elementy się zmieniają.
- Nie wnioskuj o możliwości tylko dlatego, że niezmiennik jej nie wyklucza.
Niezmiennik mówi „nie”, lecz nie zawsze mówi „tak”
Z liczby 7 przez kroki ±2 można dojść do każdej liczby nieparzystej, ale w innych grach zgodna parzystość nie gwarantuje osiągalności. Mogą istnieć dodatkowe bariery. Potrzebna jest konstrukcja ruchów lub osobny argument.
Zadanie do samodzielnej próby: startujesz z 4 i możesz dodawać lub odejmować 6. Czy dojdziesz do 16 albo 18? Liczba 16 jest osiągalna: 4 + 6 + 6. Liczba 18 nie jest: wszystkie wyniki dają resztę 4 przy dzieleniu przez 6. Parzystość sama nie odróżnia tych dwóch celów. Dalej prowadzą reszty z dzielenia w dowodach. Przy zapisywaniu niemożliwości przyda się również schemat dowodu nie wprost.