Zadanie ma bardzo atrakcyjną warstwę fabularną, gdyż pojawia się w niej nie tylko popularny Bajtek, ale i inny amator gry w karty: Bitek. Obaj panowie pragną rozstrzygnąć, kto jest lepszy w karcianą grę Magiczne Stwory. Co ciekawe, dla ostatecznego wyniku ważniejsze od samej rozgrywki będzie to, co dzieje się jeszcze przed jej rozpoczęciem, a mianowicie wybór talii kart.

Zakładamy, że Bajtek dysponuje zestawem talii kart do gry w Magiczne Stwory, konkretnie taliami Podobnie Bitek ma talie Do gry potrzebne są dwie talie, a więc umówiono się, że jedna z talii pochodzić będzie od Bajtka, a druga - od Bitka. Gdy już ustalimy wybór kart, to sama rozgrywka będzie deterministyczna i łatwo potrafimy z góry powiedzieć (tzn: te informacje podane są jako dane wejściowe), kto wygra, ewentualnie, że będzie remis.

Metoda wyboru talii do gry jest następująca. Naprzemiennie, poczynając od Bajtka, każdy z graczy odrzuca jedną z talii przeciwnika. Prawdziwą rozgrywkę zaczynamy, gdy każdy z graczy ma już tylko po jednej talii. Celem zadania jest stwierdzenie, czy Bajtek ma strategię wygrywającą. Jeśli nie - to, czy chociaż potrafi zapewnić sobie remis.

Zanim przejdziemy do rozwiązania tego zadania, spróbujemy się pokusić o jego redukcję do problemu prostszego. Twierdzę, że jeśli wybór talii byłby inny (prostszy), to nie wpłynęłoby to na szanse Bajtka. Rozważmy więc taką wersję wyboru talii, gdzie najpierw Bajtek po prostu wybiera pewną talię z zestawu Bitka, po czym Bitek dowolnie dobiera do niej jakąś talię z zestawu Bajtka i obaj zaczynają grać kartami

Dlaczego taki wybór talii nie jest istotnie różny od oryginalnego?

Po pierwsze: w obu wersjach to Bajtek decyduje, która z talii Bitka (oznaczmy ją przez ) weźmie udział w rozgrywce. Istotnie, w wersji uproszczonej jest to wprost powiedziane, natomiast w oryginalnej: to Bajtek kolejno odrzuca talie Bitka, a więc to właśnie on kontroluje, która na końcu zostanie.

Nieco trudniej dowieść drugiej własności, to znaczy tej, że Bitek może dowolnie dobrać talię do W wersji uproszczonej dostajemy to wprost z definicji, ale w oryginalnej nie jest to wcale jasne. Oczywiście, to Bitek odrzuca kolejno talie Bajtka, ale nie wie przecież z góry, jakie będzie co niesie ryzyko odrzucenia na jakimś wczesnym etapie procesu wyboru. Wykażemy przez indukcję, że Bitek jest w stanie - mimo wszystko - zachować należytą ostrożność.

Dla nie mamy żadnego wyboru, więc baza indukcji jest trywialna. Załóżmy więc, że oraz że Bajtek zgłasza odrzucenie talii Dodatkowo oznaczmy jako tę talię, którą dobrałby Bitek do Mamy teraz dwa przypadki. Pierwszy jest wtedy, gdy nie byłaby dobrana dla żadnego innego poza Wówczas bez żalu Bitek może odrzucić W przeciwnym przypadku zakładamy, że jest dobrana do więcej niż jednego Oznacza to, że funkcja dobierająca talie do nie jest różnowartościowa, a więc istnieje talia która nigdy nie byłaby dobrana. Tym razem to z tą talią Bitek może się pożegnać i przejść indukcyjnie do problemu rozmiaru

Skoro już uzasadniliśmy równoważność zadania dla znacznie prostszego modelu, możemy bardzo łatwo je rozwiązać. Po pierwsze: jeśli dla każdej talii istnieje taka talia że karty dają zwycięstwo Bitkowi, to Bitek ma strategię wygrywającą. Po drugie: jeśli dla każdej talii istnieje taka talia że karty oznaczają remis, to Bitek może zapewnić sobie remis. Okazuje się więc, że Bajtek wygrywa tylko wtedy, gdy istnieje taka talia która w połączeniu z dowolnym daje zwycięstwo Bajtkowi.

Sprawdzenie, w którym z powyższych przypadków się znajdujemy, jesteśmy w stanie wykonać bardzo prosto, po prostu analizując bezpośrednio (w czasie liniowym) wczytywane dane.