Dowodzenie oczywistości

Rys 1.

Niniejszy wpis należy rozpatrywać jako zabawę i ćwiczenie dla umysłu. Będzie to taka pop-matematyka, lekka i rozrywkowa. W efekcie udowodnimy rzecz niesłychanie oczywistą, ale przy okazji potrenujemy trochę umysł. Powyższy rysunek, którego wykonanie zawdzięczam mojej siostrze, wyjaśni się w odpowiednim momencie jak i zasadnicza treść tego wpisu. Chciałbym opisać wszystko zgodnie z chronologią mojego procesu myślowego, aby pewne oczywistości okazały się dla was taką samą niespodzianką jak dla mnie. Proszę się nie obawiać, że zwięzłość wpisu na tym ucierpi – nie będę dowodził dwa razy tego samego.

Wszystko zaczęło się od następującego problemu. Wyobraźmy sobie pewien ciąg złożony tylko z jedynek i minus jedynek \{u_n\}_{n=1}^\infty i rozważmy jego sumę

\displaystyle s_n=\sum_{i=1}^n u_n.

Interesowało mnie kiedy taka suma się zeruje. Mając konkretny ciąg u_n dany poprzez pewne zależności rekurencyjne udało mi się łatwo wykluczyć, że zeruje się dla nieparzystych wyrazów. Trochę za bardzo skupiłem się na tych wzorach rekurencyjnych, a zapomniałem czym jest taki ciąg. Gdy sobie to już przypomniałem,  zorientowałem się, że ta suma nie zeruje się dla wyrazów nieparzystych z powodów bardziej ogólnych i bardziej oczywistych.

Zauważmy, że jeśli

\displaystyle \sum_{i=1}^n u_n=0

Oznacza to, że wszystkie jedynki i minus jedynki się „kasują” w powyższej sumie. Inaczej – każda jedynka ma do pary minus jedynkę. Zatem łącznie jest ich parzysta ilość, czyli n jest parzyste. Przeciwnie, gdy n będzie nieparzyste, to w naszej sumie wystąpi jedynka bądź minus jedynka nie do pary i suma nie będzie mogła się wyzerować. Rozumowanie jak najbardziej w porządku, normalnym ludziom pewnie by ono wystarczyło, ale ja stwierdziłem, że skoro to takie oczywiste to na pewno łatwo można je sformalizować. No ale przecież nie będę dowodził jakiegoś szczególnego przypadku, tylko postaram się to jeszcze uogólnić i ująć w jakiejś schludnej formie…

Zabrałem się więc za ciągi \{ h_n\}_{n=0}^\infty o wartościach całkowitych, które spełniają następujący warunek

\forall n: |h_{n+1}-h_n|=1

czyli jak poprzednio kolejne wartości różnią o jeden lub minus jeden.

Zauważmy, że możemy go zapisać jako sumę pewnego ciągu jedynek lub minus jedynek plus pewna wartość początkowa, gdyż

\displaystyle h_n-h_0=\sum_{i=0}^{n-1}(h_{i+1}-h_i)

czyli

\displaystyle h_n=\sum_{i=0}^{n-1}(h_{i+1}-h_i)+h_0

Będziemy jednak korzystali częściej z wcześniejszej równości, gdyż wtedy mamy sytuację jak na początku – sumę ciągu jedynek i minus jedynek.

Tak czy owak wykres przykładowej funkcji h_n wygląda tak

wykr1

gdzie czerwone punkty to wartości h_n, a strzałki obrazują skok o jeden lub o minus jeden.  Pojawia się, więc nowy sposób patrzenia na h_n związany z poruszaniem się, ale chwilowo go zostawmy. Docelowo interesowała nas parzystość liczby kroków, która prowadzi do osiągnięcia zerowej wysokości przez h_n, ale po co się ograniczać do jakieś wybranej wartości? Lepiej zbadać tę zależność dla dowolnej wysokości h. Zatem interesuje nas parzystość n dla h_n=h. Tylko po co wprowadzać jakąś dodatkową zmienną? To jest po prostu h_n. Sformułuję teraz własność w takiej postaci do jakiej doszedłem z wyliczeń, która miała być już tą ogólną i schludnie przedstawioną.

Własność.

Dla każdego n naturalnego zachodzi

2|n wtedy i tylko wtedy, gdy 2|h_n-h_0.

Zanim ją dowiedziemy spróbujmy ją zinterpretować. Mówi ona, że jaką ścieżką by h_n nie tworzyło, odległość którą przebywa w poziomie musi być tej samej parzystości , co odległość przebyta w pionie (mam na myśli, że obie są parzyste albo obie nieparzyste). Na przykład na poprzednim wykresie mieliśmy

wykr22

Własność ta też oznacza, że nie dojdziemy idąc w prawo i do góry lub na dół w parzystej liczbie kroków na nieparzystą wysokość (i vice versa).  W tym momencie jeszcze nie zadałem sobie pytania, które zaraz postawię, wtedy był czas na dowód.

Obserwacja.

Jeśli 2|n, to 2|h_n-h_0.

Dowód.  Zakładamy, że 2|n, to znaczy n=2l dla pewnego l. Wtedy

\displaystyle h_n-h_0=h_{2l}-h_0=\sum_{i=0}^{l-1}(h_{2i+2}-h_{2i})

ale zauważmy, że

h_{2i+2}-h_{2i}=(h_{2i+2}-h_{2i+1})+(h_{2i+1}-h_{2i}) \in \{-2,0,2\}

co oznacza, że każdy składnik sumy dzieli się przez 2, stąd również cała suma. OK.

Dowód Własności. Obserwacja załatwia nam implikację w jedną stronę. Załóżmy więc teraz, że 2|h_n-h_0 i przypuśćmy, że jednak n jest nieparzyste, czyli przedstawia się jako n=2l+1. Wtedy

2|h_n-h_0=h_{2l+1}-h_0=(h_{2l+1}-h_{2l})+(h_{2l}-h_0).

Z Obserwacji

2|h_{2l}-h_0,

ale nie jest prawdą, że

2| h_{2l+1}-h_{2l}=\pm 1

co daje sprzeczność. OK.

Mamy zatem prosto udowodnioną nieco ogólniejszą własność niż początkowo była potrzeba. Zwróćmy uwagę, zupełnie dla bajeru, że z przechodniości przystawania modulo 2 prawdziwe też jest

2|n-m wtedy i tylko wtedy, gdy 2|h_n-h_m.

Jednak skoro początkowo własność była intuicyjnie oczywista to czy ta ogólniejsza też nie jest? Zaczęło mnie więc nurtować pytanie:

Czy to jest oczywiste?

Patrząc na liczby –  tak, bo h_n-h_0 to suma jedynek i minus jedynek. Gdy 2|n to jak w dowodzie – grupując w pary każde dwa elementy sumy widzimy, że dostajemy liczbę parzystą. Gdy n jest nieparzyste , to zostaje jakaś jedynka lub minus jedynka bez pary. W tym pytaniu o oczywistość chodzi mi o graficzną interpretację, tzn. o to,  że nie znajdziemy ścieżki zgodnej z naszymi zasadami poruszania się, która poprowadzi nas w nieparzystej liczbie kroków w poziomie o parzystą odległość w pionie i  na odwrót. Odpowiedź jest taka sama, to też oczywiste. Ale że jestem zbytnim „wolnomyślicielem”, żeby to zauważyć od razu, zorientowałem się dopiero podczas pewnej czynności sprzyjającej namysłowi filozoficznemu, mając przed oczami posadzkę ułożoną w szachownice. Wróćmy do wcześniejszego wykresu, ale odpowiednio przesuniętego i pokolorowanego.

wykres3

Teraz widać bez liczenia czegokolwiek. Figura szachowa, która porusza się po skosie nazywa się laufrem lub gońcem. Jeśli stała na białym polu, to nigdy nie wejdzie na czarne i vice versa. Zwróćmy uwagę, że tego w pełni nie dowodzi nasza własność, gdyż kierunek ruchu jest ograniczony, po skosie, ale zawsze w prawo. Niewiele jednak trzeba, by uwolnić się od tego ograniczenia. Praktycznie nic nowego nie będziemy dowodzili. Potrzebujemy rozważyć tylko ciąg punktów, który potrafi iść w dowolnym kierunku po skosie.

Przenieśmy się więc na chwilę w N– ty wymiar. Teraz będziemy zakładali, że nasz ciąg ma N współrzędnych

h_k=(h_k^1, h_k^2, \dots, h_k^N)

o takich samych własnościach jak h_n, które rozważaliśmy wcześniej, tzn.

\forall k: \forall i \in \{1,2,\dots N\}: |h_{k+1}^i-h_k^i|=1

i współrzędne są o wartościach całkowitych. Ogólnie różnica

h_{n+1}-h_n

może mieć na współrzędnych tylko jedynki i minus jedynki. Zobaczmy o co chodzi na płaszczyźnie.

 

chwykr

W trójwymiarze też da się wyobrazić jak zachowuje się nasz ciąg punktów. Udowodnimy teraz (bez wysiłku) uogólnienie Własności i stąd już będzie wynikać własność laufra.

Stwierdzenie 1.

Dla N-wymiarowego ciągu h_n dla każdego k następujące warunki są równoważne 

  1. 2|k
  2. \forall i \in \{1,2,\dots N\}: 2|h^i_k-h^i_0
  3. \exists i \in \{1,2,\dots N\}: 2|h^i_k-h_0^i

Dowód. Załóżmy 2|k. Stosując Własność do każdej z liczb h^i_k-h^i_0 otrzymujemy żądaną podzielność. Drugi punkt implikuje trzeci w sposób oczywisty. Trójka implikuje jedynkę na mocy Własności zastosowanej do ciągu z i-tej współrzędnej. OK.

Widać więc, że bez żadnego wysiłku dowiedliśmy uogólnienie na N-ty wymiar. Wynikało prawie, że na zasadzie „masło maślane” z Własności, i z faktu, że k było wspólne dla wszystkich współrzędnych. Proszę zwrócić uwagę, że taka trójczęściowa teza pozwala stwierdzić, że zarówno parzysta liczba kroków powoduje parzyste przemieszczenie we wszystkich wymiarach, jak i nieparzysta liczba kroków powoduje nieparzyste przemieszczenia na każdym wymiarze.

Wróćmy teraz na ziemię, przyjmijmy N=2. W takiej sytuacji h_n=(x_n,y_n) jest ciągiem punktów na płaszczyźnie. Zdefiniujmy standardową szachownicę. Jest to zbiór wszystkich par liczb od 1 do 8:

\{1,2,3,4,5,6,7,8\} \times \{1,2,3,4,5,6,7,8\}

Ogólnie dla zabawy możemy za szachownicę uważać iloczyn kartezjański dwóch dowolnych niepustych podzbiorów \mathbb{Z}, oczywiście takich żeby dało się potem poruszać po tej szachownicy.

Zdefiniujmy teraz białe i czarne pola.

Mówimy, że element (i,j) z szachownicy jest polem czarnym, gdy 2|i-j. Białym, gdy przeciwnie.

Mamy więc, że w parzystych rzędach pola są czarne, gdy mają parzyste numery, w nieparzystych rzędach, gdy mają nieparzyste – na zmianę jak to na szachownicy.

Zresztą zauważmy, że po pierwsze a1=(1,1) jest czarne jak w oryginale, po drugie, co istotniejsze, sąsiednie pola (nad, pod, na lewo, na prawo) są odmiennych kolorów:

2|i-j wtedy i tylko wtedy, gdy nie zachodzi 2|i-j\pm1

Możemy więc przystąpić do udowodnienia finalnej oczywistości.

Stwierdzenie (Własność laufra)

Załóżmy, że \{h_n\}_{n=0}^\infty=\{(x_n,y_n)\}_{n=0}^\infty ma wartości w szachownicy. Załóżmy, że |x_{n+1}-x_n|=1=|y_{n+1}-y_n|. W takiej sytuacji dla dowolnego n \geq 0

h_0 jest czarnym polem wtedy i tylko wtedy, gdy h_n jest czarnym polem. 

Dowód.  Zauważmy, że ze Stwierdzenia 1 wynika, że albo obie liczby y_n-y_0, x_n-x_0 są parzyste albo obie nieparzyste. Bo gdy choć jedna jest parzysta, tzn. spełniony jest warunek 3., to dostajemy 2. – parzystość wszystkich. Zatem w obu przypadkach zachodzi

2|(x_n-x_0)-(y_n-y_0)=(x_n-y_n)-(x_0-y_0)

Po przegrupowaniu czynników widzimy, że parzystość jednej z liczb x_n-y_n, x_0-y_0 pociąga parzystość drugiej, a parzystość oznacza u nas bycie czarnym polem. OK.

Z podobną łatwością, z jaką stwierdzamy własność laufra patrząc na szachownicę, dowiedliśmy również jej matematycznego odpowiednika. Gdybyśmy chcieli uogólnić powyższe rozważania na N– ty wymiar, to czarne pola definiujemy analogicznie – jako te (i_1,i_2, \dots i_N), dla których

\displaystyle 2|\sum_{k=1}^N i_k,

białe w przeciwnym wypadku. Ponownie sąsiednie pola są odmiennych kolorów. Problem pojawia się przy definiowaniu gońca. Analogiczna definicja będzie właściwa dla parzystych N, natomiast np. dla N=3, jeśli ktoś potrafi sobie wyobrazić szachownicę w 3D, to zauważy że tam poruszanie się po skosie opisuje trójka ciągów taka, że gdy dwa są równe jeden lub minus jeden, trzeci musi być równy zero. Gdybyśmy przesuwali się o jeden w każdym wymiarze, co drugi ruch zmienialibyśmy kolor pola.

To by było na tyle, ale być może jeszcze coś napiszę w przyszłych wpisach o takich ciągach-laufrach, bo spodobał mi się ich temat. Mam zresztą w zanadrzu już kilka innych geometrycznych własności.