Każde pole szachownicy
pomalowane jest na biało lub czarno.
W jednym ruchu możemy w dowolnej podszachownicy wymiaru
lub
zamienić kolory na przeciwne. Czy dla dowolnego początkowego
pokolorowania istnieje sekwencja ruchów dająca w efekcie całą białą
szachownicę?
Rozwiązanie
Skoro jest
podszachownic wymiaru
i
podszachownic wymiaru
to istnieje
pojedynczych
ruchów możliwych do wykonania. Zauważmy, że wykonanie ruchu
a następnie ruchu
prowadzi do tego samego kolorowania
szachownicy, co wykonanie najpierw ruchu
a potem ruchu
Ponadto wykonanie tego samego ruchu parzystą liczbę razy nie zmienia
kolorowania szachownicy. Zatem każda sekwencja ruchów jest jednoznacznie
opisana przez podanie ruchów występujących w niej nieparzystą liczbę razy. Jest
więc nie więcej niż
nierównoważnych sekwencji ruchów
(sekwencje uznajemy za równoważne, jeśli dają ten sam efekt). Startując
z ustalonego kolorowania szachownicy, otrzymamy zatem co najwyżej
innych kolorowań. Ale wszystkich możliwych pokolorowań
szachownicy jest
Znajdzie się więc takie, którego nie otrzymamy
żadną sekwencją ruchów z całej białej szachownicy. Równoważnie, znajdzie
się takie pokolorowanie, którego żadną sekwencją ruchów nie sprowadzimy
do całej białej szachownicy.