Dowód przez przypadki: jak dzielić na scenariusze, by nic nie pominąć

Po co w ogóle dzielić dowód na przypadki?

Intencja: zapanować nad złożonością

Dowód przez przypadki to logiczna wersja zasady „dziel i rządź”. Zamiast próbować udowodnić stwierdzenie w jednej, skomplikowanej linii rozumowania, rozbija się sytuację na kilka prostszych scenariuszy, które wspólnie obejmują wszystkie możliwości. W każdym scenariuszu dowód jest łatwiejszy, bardziej lokalny, mniej obciążony technicznymi szczegółami.

Taka technika naturalnie pojawia się, gdy:

• warunki zadania zależą od znaku, parzystości lub położenia punktu,
• część wzorów lub definicji zmienia się skokowo (np. wartość bezwzględna, funkcje „odcinkami”),
• różne konfiguracje obiektów prowadzą do różnych dróg rozumowania.

Intencja czytelnika zwykle jest prosta: zbudować schemat dowodu przez przypadki tak, by mieć gwarancję, że niczego nie pominął i nie policzył dwa razy. To jest dokładnie kwestia dobrej taksonomii – sensownego podziału na scenariusze.

Dowód ogólny kontra dowód przez przypadki

W dowodzie „ogólnym” próbuje się znaleźć jedno rozumowanie obejmujące cały zakres zmiennych. Umysłowo wygląda to jak patrzenie z lotu ptaka: jedna perspektywa, ale za to dość złożona. W dowodzie przez przypadki działa się bardziej jak analityk: rozkłada się zagadnienie na podkategorie i każdą rozpracowuje osobno.

Porównując oba podejścia:

W zadaniach szkolnych i olimpijskich dowód przez przypadki jest często bardziej naturalny, szczególnie wtedy, gdy problem w sposób oczywisty „rozpada się” na kilka wariantów: liczba dodatnia/ujemna, punkt wewnątrz/na/zewnątrz figury, liczba o danej reszcie z dzielenia itp.

Powiązanie z logiką: alternatywa „A lub B”

Logiczny schemat dowodu przez przypadki opiera się na prostym wzorcu:

• jeśli A, to P,
• jeśli B, to P,
• wiadomo, że zachodzi A lub B,
• wniosek: jeśli A lub B, to P.

W bardziej ogólnej wersji mamy przypadki A₁, A₂, …, Aₙ; ważne jest, by:

• każdy przypadek Aᵢ prowadził do tego samego wniosku P,
• zachodziła alternatywa: A₁ lub A₂ lub … lub Aₙ dla każdej możliwej sytuacji.

Całe zadanie z dowodem przez przypadki sprowadza się wtedy do dwóch pytań:

1. Jak zbudować zbiór przypadków, który obejmie wszystko i się nie będzie nachodzić?
2. Jak w każdym przypadku doprowadzić do tego samego twierdzenia P możliwie najprostszą drogą?

Fundament logiczny: rozłączność i zupełność przypadków

Rozłączność: przypadki nie mogą się dublować

Rozłączność oznacza, że żadna konkretna sytuacja nie należy do dwóch różnych przypadków naraz. Jeśli definiujesz przypadki:

• Przypadek 1: x > 0,
• Przypadek 2: x ≤ 0,

to żadna liczba rzeczywista nie może mieć jednocześnie własności x > 0 i x ≤ 0. Przypadki są więc rozłączne. Kontrast:

• Przypadek 1: x > 0,
• Przypadek 2: x ≥ 0.

Tutaj liczba x > 0 należy do obu przypadków. Dowód „przez przypadki” przestaje być przejrzysty, bo można tę samą sytuację rozpatrywać dwa razy, dojść do dwóch różnych przekształceń i nie mieć pewności, czy wynik nie zależy od drogi.

Rozłączność przypadków jest szczególnie ważna, gdy przypadki są rozbudowane. Nachodzenie się scenariuszy rodzi wtedy konflikty: w jednym przypadku wyprowadzisz inną postać wzoru niż w drugim, dostaniesz pozornie sprzeczne wnioski i nie będzie jasne, czy problem leży w rachunkach, czy w samym podziale.

Zupełność: żaden scenariusz nie może zniknąć

Zupełność oznacza, że każda dopuszczalna sytuacja podpada pod jeden z rozważonych przypadków. Tu kontrast jest inny:

• Podział 1: x > 0 lub x ≤ 0 – zupełny.
• Podział 2: x > 0 lub x ≥ 0 – też zupełny (każda liczba jest <0, 0 lub >0, więc ma własność >0 lub ≥0), ale nierołączny.
• Podział 3: x > 0 lub x ≥ 1 – ani rozłączny, ani zupełny (np. x = 0,5 nie spełnia żadnego warunku).

W dowodzie przez przypadki brak zupełności jest groźniejszy niż brak rozłączności, bo możesz pominąć całe klasy przykładów. Twierdzenie wyjdzie „prawie poprawne”, ale nie dla wszystkich wartości, dla których miało być dowiedzione.

W praktyce szkolnej i olimpijskiej dobry nawyk to krótka refleksja: „Czy istnieje przykład, który nie pasuje do żadnego przypadku?”. Jeśli tak – podział nie jest zupełny. Jeśli nie – jesteś na dobrej drodze.

Tercjum non datur: logika „albo tak, albo nie”

Zasada tertium non datur (nie ma trzeciej możliwości) mówi: dla dowolnego zdania P zachodzi „P lub nie-P”. W najprostszym dowodzie przez przypadki dzieli się więc na:

• Przypadek 1: założenie P jest prawdziwe,
• Przypadek 2: założenie ¬P (nie-P) jest prawdziwe.

Ten binarny podział jest automatycznie rozłączny i zupełny. W zadaniach rachunkowych przybiera on formę:

• x ≥ 0 lub x < 0,
• liczba jest parzysta lub nieparzysta,
• punkt leży wewnątrz figury lub poza nią (czasem uwzględnia się też trzeci wariant: na brzegu).

Często bardziej szczegółowy podział (np. na trzy przypadki) jest po prostu rozszerzeniem zasady tercjum non datur: zamiast „parzysta lub nieparzysta” bierze się „reszta 0, 1, 2 przy dzieleniu przez 3”.

Przykład z życia: frekwencja i typy obecności

Dobry model intuicyjny da się zobaczyć w codziennym systemie szkolnym. Rozważ dwa sposoby klasyfikacji uczniów na lekcji:

• Wariant A: obecny / nieobecny.
• Wariant B: obecny / spóźniony / nieobecny.

W wariancie A podział jest rozłączny i zupełny względem prostej własności „jest go na lekcji”. Jeśli liczy się frekwencję w procentach, dwa przypadki całkowicie wystarczają. Wariant B rozbija „obecny” na dwa scenariusze, gdy istotne są spóźnienia. Zupełność zostaje, ale rośnie liczba kategorii.

Matematycznie sytuacja wygląda podobnie: im więcej informacji chcesz wydobyć z zadania, tym bardziej szczegółowego (ale nadal rozłącznego i zupełnego) podziału potrzebujesz. Zbyt gruby podział nie daje wystarczających danych; zbyt drobny generuje mnóstwo niepotrzebnej pracy.

Jak zaplanować podział na przypadki: trzy podstawowe strategie

Strategia 1: podział według znaku

Najpopularniejszy wariant w zadaniach algebraicznych to podział według znaku:

• x > 0,
• x = 0,
• x < 0.

Taki schemat jest:

• rozłączny – żadna liczba nie może mieć dwóch różnych znaków naraz,
• zupełny – każda liczba rzeczywista jest dodatnia, zero lub ujemna.

Sprawdza się szczególnie, gdy:

• definicja obiektu zależy od znaku (wartość bezwzględna, pierwiastek, logarytm),
• w zadaniu pojawia się „sgn(x)”, „większe z liczb x, y” lub inne funkcje określane kawałkami,
• przy przejściu przez zero zmienia się rodzaj rozumowania (np. inny wzór na pole, inne ograniczenia).

Można też stosować nieco uproszczony podział x ≥ 0 / x < 0, jeśli przypadek x = 0 nie wymaga oddzielnego traktowania. To dobry przykład, gdzie minimalna liczba przypadków jest sensownym kryterium: jeśli zero „nie psuje” rachunków, nie ma potrzeby wydzielać go osobno.

Strategia 2: podział według reszty z dzielenia (modulo)

W arytmetyce bardzo wygodny jest podział według reszty z dzielenia przez stałą liczbę:

• modulo 2: parzyste / nieparzyste,
• modulo 3: reszta 0, 1, 2,
• modulo 4: reszta 0, 1, 2, 3 itd.

Schemat jest mechaniczny:

• przypadki są rozłączne, bo liczba ma tylko jedną resztę z dzielenia,
• przypadki są zupełne, bo każda liczba ma jakąś resztę w ustalonym przedziale (np. 0–2 dla mod 3).

Ten rodzaj podziału dobrze służy w zadaniach typu:

• „dla każdej liczby naturalnej n wykaż, że wyrażenie ma pewną własność”,
• „pokaż, że liczba o takiej postaci nigdy nie jest podzielna przez 3”,
• „wszakże dla każdej klasy reszt wynik zachowuje się inaczej”.

Częsty błąd polega na wybieraniu zbyt mocnego modułu: np. rozbijanie wszystkiego na 6 przypadków według reszty mod 6 tam, gdzie wystarczyłoby parzyste/nieparzyste. Dużo rachunków, mało nowej treści.

Strategia 3: podział według konfiguracji i porządku

W geometrii i kombinatoryce kluczowy jest układ obiektów, a nie ich wartości liczbowe. Naturalne przypadki tworzy się wtedy z konfiguracji:

• punkt względem figury: wewnątrz / na brzegu / na zewnątrz,
• kolejność punktów na prostej: A-B-C, A-C-B, B-A-C itd.,
• typ trójkąta: ostrokątny / prostokątny / rozwartokątny.

Tu pojawia się nowe wyzwanie: liczba możliwych konfiguracji rośnie szybko. Trzeba więc:

• zidentyfikować konfiguracje różne istotnie (tzn. wymagające innego rozumowania),
• zgrupować konfiguracje równoważne (np. przez symetrię) w jeden przypadek,
• upewnić się, że nie pominęło się którejś klasy ustawień.

W takiej sytuacji bardzo pomaga rysunek lub drzewko przypadków. Najpierw ustala się główny podział (np. punkt wewnątrz / na / na zewnątrz), a dopiero potem ewentualnie rozbija poszczególne gałęzie na podprzypadki.

Kiedy wystarczą 2 przypadki, a kiedy potrzeba 3 lub więcej

Kiedy wystarczą 2 przypadki, a kiedy potrzeba 3 lub więcej – praktyczne kryteria

Dwa przypadki („albo – albo”) kuszą prostotą, ale nie zawsze dostarczają tego, co potrzebne, by domknąć rozumowanie. Decyzję da się oprzeć na kilku prostych pytaniach kontrolnych.

Pierwsze pytanie: czy w każdym z przypadków prowadzisz zasadniczo inne rozumowanie? Jeśli:

• w przypadkach x > 0 i x < 0 robisz dokładnie te same przekształcenia,
• a tylko w x = 0 trzeba coś osobno sprawdzić (np. czy wyrażenie jest zdefiniowane),

to wygodniejszy będzie podział na dwa przypadki: x = 0 oraz x ≠ 0. Przypadek „niezerowy” obejmie i dodatnie, i ujemne, ale rachunkowo nic na tym nie tracisz.

Drugie pytanie: czy kluczowa własność zmienia się skokowo tylko w jednym punkcie, czy w kilku? Najczęstsza sytuacja:

• jeśli jedynym „miejscem krytycznym” jest 0 – dwa przypadki zwykle wystarczą: x ≥ 0 / x < 0 albo x = 0 / x ≠ 0,
• jeśli pojawia się więcej punktów przełomu (np. x = -1, x = 2), naturalny staje się podział na 3–4 przedziały: x < -1, -1 ≤ x < 2, x ≥ 2.

Trzecie pytanie: czy dodatkowy przypadek wnosi nową informację, czy tylko mnoży rachunki? Porównanie:

• Podział A: x ≥ 0, x < 0 – w obu przypadkach inne wzory na wartość bezwzględną, oba są naprawdę użyte.
• Podział B: x > 0, x = 0, x < 0 – jeśli w środku piszesz jedną linijkę „dla x=0 teza jest oczywista”, a reszta dowodu kopiuje się z A, to trzeci przypadek jest tylko kosmetycznym rozdrobnieniem.

Ogólne kryterium: tyle przypadków, ile naprawdę różnych mechanizmów rozumowania. Gdy zaczynasz w trzech przypadkach wykonywać identyczne ruchy, to sygnał, że podział jest zbyt drobny.

Jak redukować liczbę przypadków bez utraty ścisłości

Czasem z zadania „bije w oczy” kilka możliwych podziałów. Jeden prowadzi do czterech gałęzi, inny do dwóch. Zamiast wybierać na ślepo, można świadomie uprościć drzewko.

Typowy zabieg to grupowanie przypadków równoważnych. Jeśli dla liczb naturalnych:

• dla n parzystych stosuje się identyczną argumentację,
• a dla wszystkich nieparzystych – inną, ale także identyczną w obrębie tej klasy,

to dzielenie jeszcze na „n ≡ 1 (mod 4)” i „n ≡ 3 (mod 4)” niewiele daje. Dwa przypadki „parzyste / nieparzyste” są logicznie pełne i rachunkowo lżejsze.

Druga technika to wykorzystanie symetrii. W geometrii:

• gdy zadanie jest symetryczne względem osi lub przekątnej,
• często wystarczy przeanalizować jedną „ćwiartkę” konfiguracji,

a pozostałe trzy opisać słownie jako analogiczne. Zamiast czterech obrazków i czterech podobnych rachunków zostaje jeden przypadek, ale argumenty są nadal kompletne.

Trzeci pomysł to mądre dobranie parametrów. W dowodach z funkcjami część przypadków znika po niewielkiej zmianie zapisu. Przykładowo, zamiast:

• Przypadek 1: x > 0,
• Przypadek 2: x < 0,

można wprowadzić parametr t = |x| i rozpatrywać tylko t ≥ 0. Informacja o znaku często przestaje być wtedy potrzebna, bo wyrażenia upraszczają się do funkcji t.

Przykład krok po kroku: wartość bezwzględna jako klasyczny trening przypadków

Definicja wartości bezwzględnej jako podział na dwa scenariusze

Wartość bezwzględna jest w zasadzie wbudowanym w analizę przykładem dowodu przez przypadki. Definicja:

• jeśli x ≥ 0, to |x| = x,
• jeśli x < 0, to |x| = -x.

To nie tylko definicja funkcji, ale też szablon dowodowy: za każdym razem, gdy pojawia się |x|, logicznie zaszyty jest w środku podział na dwa przypadki.

Rozłączność i zupełność są wbudowane:

• nie ma liczby, która byłaby jednocześnie ≥ 0 i < 0,
• każda liczba rzeczywista jest albo ≥ 0, albo < 0.

Dlatego wszystkie twierdzenia o wartości bezwzględnej właściwie wymuszają rozumowanie „osobno dla dodatnich (i zera), osobno dla ujemnych”.

Ćwiczenie 1: dowód nierówności |x| ≥ 0

Jedno z pierwszych zadań: pokazać, że |x| ≥ 0 dla każdego x ∈ ℝ. Dowód przez przypadki jest tu niemal mechaniczny:

• Przypadek 1: x ≥ 0. Wtedy |x| = x z definicji, więc |x| = x ≥ 0.
• Przypadek 2: x < 0. Wtedy |x| = -x, a ponieważ x < 0, to -x > 0, zatem |x| > 0.

Oba przypadki razem pokrywają wszystkie liczby. Argumenty są krótkie, ale ilustrują typową strukturę:

1. podział dziedziny na dwa scenariusze wynikające z definicji,
2. w każdym scenariuszu zamiana symbolu |x| na odpowiedni wzór,
3. dalsze proste przekształcenia bez wartości bezwzględnej.

Ćwiczenie 2: nierówność trójkąta dla liczb rzeczywistych

Klasyczne zadanie: dla wszystkich x, y ∈ ℝ zachodzi |x + y| ≤ |x| + |y|. Jedna z wygodnych dróg dowodu prowadzi przez przypadki, ale nie na „ślepo”, tylko z umiarem.

Pierwszy pomysł – cztery przypadki: znak x (dodatni/ujemny) razy znak y (dodatni/ujemny). Daje to:

• x ≥ 0, y ≥ 0,
• x ≥ 0, y < 0,
• x < 0, y ≥ 0,
• x < 0, y < 0.

Taki podział jest poprawny logicznie, ale męczący rachunkowo, bo wiele przekształceń się powtarza. Można to zrobić sprytniej, w dwóch krokach.

Najpierw wykorzystuje się fakt, że |x| = |-x|. Zamiast rozpatrywać jednocześnie wszystkie kombinacje znaków, można założyć:

• bez straty ogólności, że |x| ≥ |y| (bo jeśli jest odwrotnie, można zamienić rolami x i y),

i zająć się tylko jednym uporządkowaniem. Potem podział na przypadki wygląda inaczej:

• Przypadek 1: x i y mają ten sam znak – wtedy |x + y| = |x| + |y| i nierówność staje się równością,
• Przypadek 2: x i y mają przeciwne znaki – wtedy jedno z nich „odciąga” drugie, więc |x + y| = ||x| – |y|| ≤ |x| + |y|.

Widać różnicę: zamiast czterech kombinacji znaków, wystarczy rozróżnić dwa scenariusze „zgodne znaki” / „przeciwne znaki”. To ten sam pomysł co przy frekwencji: zamiast rozbijać obecność na wiele podkategorii, grupuje się zachowania według tego, co naprawdę wpływa na wynik (tu: sposób „dodawania się” wartości bezwzględnych).

Typowe pułapki przy pracy z wartością bezwzględną

Najczęstsze problemy pojawiają się, gdy podział na przypadki jest wymuszony przez samą definicję, ale zostaje wykonany niekonsekwentnie.

• Pominięcie jednego przypadku. Rozpatrzenie tylko x ≥ 0 „bo tak jest łatwiej”, bez powrotu do x < 0, prowadzi do twierdzeń prawdziwych tylko „dla połowy osi liczbowej”.
• Przypadki nierołączne. Ustawienie: „x ≥ 0 lub x ≥ 1” jako dwa osobne scenariusze przy dowodzeniu równości z wartością bezwzględną to gwarantowana niespójność. Część x ≥ 1 nakłada się na x ≥ 0, więc te same liczby pojawiają się w dwóch gałęziach.
• Brak wykorzystania założeń. Czasami w zadaniu wprost stoi: „x ≥ 0”. Wtedy w dowodzie nie trzeba już rozbijać się na „x ≥ 0 lub x < 0”. Cała część „ujemna” jest z góry wykluczona.

Porównanie dwóch stylów pracy z |x| dobrze pokazuje balans:

• „Mechaniczne” podejście: zawsze dzielić na wszystkie możliwe znaki. Bezpieczne, ale szybko rośnie liczba przypadków.
• „Świadome” podejście: dzielić tylko tam, gdzie znak naprawdę zmienia wzór lub argument. Mniej gałęzi, więcej myślenia na początku.

Dowody w arytmetyce: parzystość, podzielność, reszty z dzielenia

Parzystość jako najprostszy przykład dwóch rozłącznych przypadków

W arytmetyce liczby naturalne naturalnie dzielą się na dwa zbiory:

• parzyste: n = 2k,
• nieparzyste: n = 2k + 1.

Taki podział jest wygodny, bo „wzór” na każdą z klas jest bardzo prosty. Każdy dowód typu „dla każdej liczby naturalnej n zachodzi …” można spróbować oprzeć na dwóch przypadkach: „n parzyste” oraz „n nieparzyste”.

Przykład: pokaż, że n² i n mają tę samą parzystość. Dowód:

• Przypadek 1: n = 2k. Wtedy n² = 4k² = 2(2k²) – liczba parzysta.
• Przypadek 2: n = 2k + 1. Wtedy n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1 – liczba nieparzysta.

W obu gałęziach ten sam schemat: zamiast „tajemniczego” n piszemy konkretną postać 2k lub 2k + 1, a dalej wszystko rozstrzyga się rachunkowo.

Podzielność a wybór modułu: kiedy mod 2, a kiedy mod 3 lub 4

Gdy w zadaniu pojawia się podzielność, do dyspozycji jest kilka poziomów szczegółowości:

• Parzystość (mod 2). Dwa przypadki, minimum pracy. Wystarcza, gdy własność zależy wyłącznie od „podzielne przez 2 / niepodzielne przez 2”.
• Reszty mod 3. Trzy przypadki: 3k, 3k + 1, 3k + 2. Przydaje się, gdy we wzorze występują potęgi i chcemy badać podzielność przez 3.
• Wyższe moduły (4, 6, 8…) – liczba przypadków rośnie, ale czasem daje to lepsze rozróżnienie (np. przy badaniu kwadratów modulo 4).

Porównanie: szukamy dowodu, że n² nigdy nie daje reszty 2 mod 4. Można:

• podejść „miękko” i rozpatrywać tylko parzyste/nieparzyste,

Rozsądny wybór modułu a liczba przypadków

Wróćmy do przykładu z resztami kwadratów mod 4. Można iść dwiema drogami.

• Podział „minimalny” – parzyste/nieparzyste. Zakładamy:
  • n = 2k – wtedy n² = 4k², więc reszta z dzielenia przez 4 to 0,
  • n = 2k + 1 – wtedy n² = 4k² + 4k + 1 = 4(k² + k) + 1, więc reszta to 1.

  Wniosek: kwadraty modulo 4 przyjmują tylko reszty 0 i 1, nigdy 2 ani 3.

• Podział „dokładny” – wszystkie reszty mod 4. Rozpisujemy:
  • n = 4k,
  • n = 4k + 1,
  • n = 4k + 2,
  • n = 4k + 3.

  Po podniesieniu do kwadratu i zredukowaniu modulo 4 i tak dostaje się tylko 0 lub 1, ale rachunków jest więcej.

Oba podejścia są logicznie poprawne. Różnica jest w gęstości informacji na przypadek. Podział na mod 4 daje pełną charakterystykę reszt kwadratów, ale kosztuje cztery gałęzie. Podział na parzyste/nieparzyste jest krótszy, a jednocześnie wystarcza, jeśli celem jest tylko wykluczenie reszty 2.

Te dwa style dobrze kontrastują, gdy pojawiają się bardziej złożone moduły:

• dla mod 6 – sześć przypadków; sensowne, gdy własność naprawdę zależy na przykład osobno od parzystości i podzielności przez 3,
• dla mod 8 – osiem przypadków; użyteczne, gdy bada się własności potęg dwójki lub kwadratów w kontekście liczb pierwszych w pewnych postaciach.

Gdy liczba przypadków rośnie lawinowo, warto się zastanowić, czy nie można:

• połączyć części z nich przez symetrię (np. 3k + 1 i 3k + 2 często zachowują się podobnie),
• zamiast mod 12 pracować oddzielnie mod 3 i mod 4, a potem „złożyć” wyniki.

Reszty z dzielenia jako gotowy szablon podziału na przypadki

Klasyczny schemat: badamy wyrażenie f(n) i chcemy stwierdzić, czy jest zawsze podzielne przez pewną liczbę m. Naturalny podział:

• n = mq,
• n = mq + 1,
• …
• n = mq + (m – 1).

Każdy przypadek odpowiada jednej reszcie modulo m. Zysk jest jasny: w każdej gałęzi n zastępuje się prostym wzorem, a wyrażenia takie jak n², n³ czy 2n + 1 redukują się do stałych reszt mod m.

Dla kontrastu można spojrzeć na dwa przykłady:

• Prosty podział – mod 3. Przy zadaniu „pokaż, że wśród trzech kolejnych liczb naturalnych dokładnie jedna jest podzielna przez 3”:
  • rozpatruje się n = 3k, 3k + 1, 3k + 2,
  • w każdej gałęzi patrzy, które z n, n + 1, n + 2 są wielokrotnościami 3.
• Cięższy podział – mod 12. Przy zadaniu „zbadaj, jakie reszty z dzielenia przez 12 mogą mieć kwadraty liczb całkowitych” – pełny podział na 12 reszt ma sens, bo wynik ma być właśnie „pełną tabelką”.

Różnica jest podobna jak między szczegółowym raportem a krótką notatką: pełne modulo daje bogatszy obraz, ale jeśli twierdzenie wymaga tylko paru wniosków, często wystarczy mod 2 lub mod 3.

Łączenie parzystości i innych modułów

Czasami dwa niezależne podziały – np. według parzystości i według reszty mod 3 – dają łącznie zbyt wiele przypadków (2 × 3 = 6). Istnieją wtedy dwie strategie:

• Rozbić tylko jeden wymiar. Skupić się np. na mod 6 zamiast na osobnych mod 2 i mod 3. Jeden dłuższy podział zamiast dwóch nakładających się.
• Rozbić „warstwowo”. Najpierw wybrać ważniejszy podział (np. parzystość), a w drugiej kolejności w niektórych gałęziach wprowadzić dodatkowy podział mod 3, ale tylko tam, gdzie to rzeczywiście potrzebne.

Jeśli celem jest np. pokazanie, że pewne wyrażenie nigdy nie jest równe 2, często wystarczy:

1. podzielić na parzyste/nieparzyste,
2. w jednej z gałęzi użyć jeszcze jednego modułu (np. mod 4),
3. w drugiej zakończyć już po pierwszym kroku.

Taki „asymetryczny” podział wydaje się na pierwszy rzut oka mniej elegancki niż jedna rozpiska na wszystkie reszty, ale rachunkowo zwykle jest lżejszy. Zamiast sześciu identycznych schematów dostaje się 2–3 naprawdę różne scenariusze.

Przypadki w geometrii i kombinatoryce: konfiguracje zamiast liczb

Geometria: podział według położenia figur

W geometrii klasyczny podział na przypadki nie kręci się wokół liczb, lecz wokół konfiguracji:

• punkt leży wewnątrz trójkąta, na boku, lub na zewnątrz,
• prosta przecina okrąg w dwóch punktach, styka się z nim lub nie przecina go wcale,
• dwa odcinki się przecinają, są równoległe lub położone „schodkowo”.

W odróżnieniu od arytmetyki, zamiast prostego wzoru typu n = 2k + 1 trzeba tu zwykle sięgnąć po rysunek i zobaczyć, jakie scenariusze są naprawdę różne. Dwa kroki są kluczowe:

1. zidentyfikowanie niezmienników – co w konfiguracji jest „sztywne” (np. równoległość, równość odcinków),
2. zobaczenie, w których ustawieniach te własności się zmieniają jakościowo, a w których pozostają identyczne.

Przykład z praktyki: przy dowodzeniu własności odcinków łączących środki boków w trójkącie można rozważać:

• trójkąt ostrokątny,
• trójkąt prostokątny,
• trójkąt rozwartokątny.

Na początku często wydaje się, że te trzy przypadki wymagają osobnych argumentów. Po kilku przekształceniach okazuje się jednak, że długości i równoległość odcinków środkowych nie zależą od rodzaju trójkąta: jedna konstrukcja wektorowa lub podobieństwo trójkątów załatwia wszystko naraz. W efekcie „trzy przypadki” kurczą się do jednego – ale trzeba to świadomie zauważyć.

Rozłączność przypadków geometrycznych: ostrożność przy rysunkach

W geometrii szczególnie łatwo niechcący „podwójnie policzyć” ten sam scenariusz. Typowe potknięcie:

• przypadek 1: punkt na boku AB,
• przypadek 2: punkt na boku BC,
• przypadek 3: punkt na boku CA,

a narożniki – czyli sam wierzchołek B – zaliczają się jednocześnie do dwóch boków. Gdy twierdzenie jest ostre (np. „odległość jest ściśle większa od czegoś”), trzeba osobno zdecydować, czy wierzchołki pojawiają się:

• jako czwarty przypadek („punkt jest wierzchołkiem”),
• czy są wyłączone z rozważań przez sformułowanie zadania.

Różnica między „x ≥ 0 lub x > 1” a „x ≥ 0 lub x ≤ -1” ma tu swój geometryczny odpowiednik: źle ułożone przypadki nachodzą na siebie w okolicach granic (narożników, punktów styku).

Kombinatoryka: przypadki według strategii liczenia

W zadaniach z liczenia obiektów (kombinatoryka) podział na przypadki najczęściej dotyczy sposobu konstruowania obiektu, a nie jego pojedynczych cech liczbowych. Typowe warianty:

• liczymy ciągi znaków według liczby wystąpień jakiegoś symbolu,
• liczymy grafy według liczby krawędzi wychodzących z wybranego wierzchołka,
• liczymy ustawienia osób przy stole według tego, kto siedzi obok kogo.

Kontrastują tu dwa podejścia do podziału:

• Podział „od definicji”. Wszystkie możliwe wartości parametru traktuje się osobno (np. liczba liter „A” w słowie od 0 do długości słowa).
• Podział „zgrubny”. Parametry grupuje się w kilka klas, które zachowują się podobnie (np. „brak litery A”, „dokładnie jedna A”, „co najmniej dwie A”).

Drugi wariant jest często wygodniejszy, bo liczba przypadków nie rośnie liniowo z rozmiarem problemu. Zamiast np. dziesięciu rozłącznych wariantów wystarczą trzy – każdy z trochę innym typem liczenia.

Przykład kombinatoryczny: podział po „pierwszej decyzji”

Rozważmy schemat: ile jest binarnych ciągów długości n, w których nie występują dwie jedynki obok siebie? Zamiast budować skomplikowane wzory rekurencyjne, można zacząć od podziału na przypadki według pierwszego symbolu:

• Przypadek 1: ciąg zaczyna się od 0. Wtedy pozostałe n – 1 znaków to dowolny dopuszczalny ciąg długości n – 1.
• Przypadek 2: ciąg zaczyna się od 1. Wtedy drugi znak musi być 0, a dalej mamy dowolny dopuszczalny ciąg długości n – 2.

Każdy ciąg spełniający warunek zaczyna się od 0 lub od 1, więc przypadki są kompletne. Jednocześnie są rozłączne: żaden ciąg nie zaczyna się jednocześnie od 0 i od 1. Podział jest krótki, bo opiera się na pierwszej decyzji, która rzeczywiście „rozwidla” wszystkie późniejsze możliwości.

Inne możliwe podejście – dzielić według liczby jedynek w ciągu – prowadzi do znacznie większej liczby przypadków, choć teoria za nimi stojąca jest ta sama. Z punktu widzenia ergonomii dowodu, podział „po pierwszej decyzji” bywa po prostu tańszy.

Symetria w kombinatoryce: redukcja liczby przypadków

Przy liczeniu rozmieszczeń identycznych obiektów podział na przypadki często można skrócić, wykorzystując symetrię. Dwa przykłady:

• przy ustawianiu osób przy okrągłym stole można naprawić nadmiarowy podział, „zamrażając” miejsce jednej osoby, aby obroty stołu nie tworzyły sztucznie wielu scenariuszy,
• przy kolorowaniu krawędzi wielokąta rozróżnia się przypadki według liczby „bloków” przy sąsiednich krawędziach, ale pary kolorów można traktować tak samo, niezależnie od ich nazw.

Zestawienie dwóch stylów:

• Liczby bez symetrii. Każdą konfigurację traktujemy osobno, podział na przypadki odzwierciedla wszystkie możliwe różnice.
• Liczby z symetrią. Konfiguracje, które można przekształcić jedną w drugą przez obrót, odbicie lub zamianę etykiet, lądują w jednym przypadku, bo mają tę samą liczbę instancji.

Pierwszy wariant jest bezpieczny, ale kosztowny. Drugi wymaga więcej zaufania do wyczucia struktury, ale odpłaca się krótszymi dowodami, w których każdy przypadek ma realnie różny charakter, zamiast różnić się tylko nazwami obiektów.

Niedoszacowanie liczby przypadków: „dziury” w konfiguracjach

W geometrii i kombinatoryce łatwiej niż w arytmetyce przeoczyć całe „wyspy” konfiguracji. Gdy pracuje się tylko na jednym rysunku lub jednym typie ustawienia, zupełnie inne sytuacje mogą w ogóle nie wejść do dowodu.

Typowa sytuacja:

• przypadek 1: prosta przecina odcinek wewnątrz,
• przypadek 2: prosta przechodzi przez jeden z końców odcinka.

Najczęściej zadawane pytania (FAQ)

Na czym dokładnie polega dowód przez przypadki?

Dowód przez przypadki polega na rozbiciu ogólnej sytuacji na kilka rozłącznych scenariuszy (przypadków), które razem obejmują wszystkie możliwości. W każdym z nich pokazuje się osobno, że zachodzi to samo twierdzenie P. Na końcu łączy się te wyniki: skoro w każdym dopuszczalnym przypadku P jest prawdziwe, to jest prawdziwe „w ogóle”.

W przeciwieństwie do dowodu „jednym ciągiem” nie szuka się jednej uniwersalnej sztuczki, tylko kilku lokalnych, prostszych rozumowań. To szczególnie pomaga, gdy definicje lub warunki zmieniają się skokowo, np. przy wartości bezwzględnej, znaku liczby, resztach z dzielenia czy różnych położeniach punktu względem figury.

Kiedy lepiej użyć dowodu przez przypadki niż dowodu ogólnego?

Dowód przez przypadki sprawdza się najlepiej, gdy problem sam „prosi się” o podział: pojawia się znak liczby (x>0, x=0, x<0), parzystość, reszta z dzielenia, różne obszary w geometrii (wewnątrz, na, na zewnątrz figury) albo gdy wzory definiowane są kawałkami. W takich sytuacjach jeden ogólny argument często staje się nieczytelny lub wymaga wielu technicznych wyjątków w trakcie rachunków.

Dowód ogólny jest zwykle lepszy, gdy problem jest „gładki”: nie ma progów, warunków typu „jeśli… to…”, a zmienne zachowują się podobnie w całym zakresie. Tam jedna, dobrze przemyślana idea daje krótsze i elegantsze rozwiązanie niż rozbijanie na wiele podobnych przypadków.

Jak sprawdzić, czy mój podział na przypadki jest poprawny?

Dobry podział na przypadki musi spełniać dwa warunki logiczne: rozłączność i zupełność. Rozłączność oznacza, że żadna konkretna sytuacja nie wpada do więcej niż jednego przypadku; zupełność – że każda dopuszczalna sytuacja wpada do któregoś z nich. Te dwa kryteria są ważniejsze niż „ładne” nazwy przypadków.

Praktyczny test wygląda tak:

• spróbuj znaleźć przykład, który pasuje do dwóch różnych przypadków naraz – jeśli się da, podział nie jest rozłączny,
• spróbuj znaleźć przykład, który nie pasuje do żadnego przypadku – jeśli się da, podział nie jest zupełny.

Jeśli oba takie kontrprzykłady nie istnieją, schemat przypadków jest logicznie w porządku.

Co to znaczy, że przypadki są rozłączne i zupełne? Możesz podać prosty przykład?

Rozłączność: żaden element nie należy do dwóch przypadków jednocześnie. Klasyczne zestawienie:

• Przypadek 1: x > 0,
• Przypadek 2: x ≤ 0.

Nie ma liczby, która byłaby jednocześnie większa od zera i mniejsza lub równa zeru, więc przypadki się nie nachodzą.

Zupełność: każdy dopuszczalny x spełnia warunek któregoś przypadku. Ten sam podział x > 0 / x ≤ 0 jest zupełny, bo każda liczba rzeczywista jest albo dodatnia, albo niedodatnia. Dla kontrastu:

• Podział: x > 0 lub x ≥ 1 – nie jest ani rozłączny (x>1 spełnia oba), ani zupełny (np. x=0,5 nie spełnia żadnego).

Taki podział nadaje się co najwyżej do wstępnej analizy, ale nie do poprawnego dowodu przez przypadki.

Jak wybrać „dobre” przypadki, żeby nie było ich za dużo ani za mało?

Można porównać dwa skrajne podejścia: bardzo gruby podział (mało przypadków, mało informacji) i bardzo drobny (dużo przypadków, dużo pracy). Sensowny wybór zależy od tego, które cechy zadania naprawdę zmieniają tok rozumowania. Jeśli przejście przez zero wymusza inny wzór lub inne ograniczenia, warto oddzielić x>0, x=0, x<0; jeśli zero nie wyróżnia się niczym szczególnym, wystarczy x≥0 i x<0.

Praktyczne kryteria:

• czy w danym zakresie formuła/argument ma wyraźnie inną postać – jeśli tak, wydziel osobny przypadek,
• czy nowy przypadek różni się od sąsiedniego tylko kosmetycznie – jeśli tak, rozważ ich połączenie,
• czy każdy dodatkowy przypadek wnosi nową informację, czy tylko mnoży rachunki.

Dobry podział to kompromis: na tyle szczegółowy, by dowód był prosty lokalnie, ale nie tak rozdrobniony, by gubić się w organizacji.

Jak dowód przez przypadki łączy się z logiką „A lub B” i zasadą tertium non datur?

Logiczny schemat jest prosty: jeśli udowodnisz „jeśli A, to P” oraz „jeśli B, to P”, a dodatkowo wiesz, że zawsze zachodzi „A lub B”, to możesz wnioskować „jeśli A lub B, to P”. W bardziej ogólnej wersji zamiast A, B masz A₁, A₂, …, Aₙ i dowodzisz P w każdym z nich, przy założeniu, że zawsze zachodzi alternatywa „A₁ lub A₂ lub … lub Aₙ”.

Zasada tertium non datur („trzeciej możliwości nie ma”) jest tu szczególnym przypadkiem: dla dowolnego zdania P zawsze mamy „P lub nie-P”. Daje to automatycznie rozłączny i zupełny podział na dwa przypadki:

• Prawda: P jest prawdziwe,
• Fałsz: P jest fałszywe (¬P).

W praktyce szkolnej odpowiada to klasycznym podziałom: liczba jest parzysta lub nieparzysta, x≥0 lub x<0, punkt leży wewnątrz lub na zewnątrz figury (czasem dochodzi trzeci wariant „na brzegu”, który doprecyzowuje podział).

Jakie są typowe błędy przy dowodzie przez przypadki na egzaminach i olimpiadach?

Najczęstsze błędy to:

• pominięcie przypadku (brak zupełności) – na przykład rozważenie tylko x>0 i x<0, gdy zero zachowuje się inaczej, a jest pominięte,
• nakładanie się przypadków (brak rozłączności) – na przykład podział typu x>0 i x≥0, gdzie dodatnie liczby rozpatruje się dwa razy.

Prowadzi to do luk w rozumowaniu albo do sprzecznych przekształceń w różnych częściach dowodu.

Druga grupa błędów to zbyt mechaniczne dzielenie problemu na mnóstwo podobnych wariantów (np. pięć przypadków, które da się sprowadzić do dwóch sensownych). Taki dowód jest formalnie poprawny, ale trudny do sprawdzenia i bardziej narażony na pomyłki rachunkowe, niż dobrze przemyślany podział z minimalną liczbą scenariuszy.