Zadanie 10 - od czworokątu wpisnego w okrąg do baz Gröbnera

_images/matura2015_r10.png

Rozwiązanie klasyczne

Szkolny sposób rozwiązania tego zadania korzysta z dwóch twierdzeń. Po pierwsze suma kątów naprzeciwległych w czworokącie opisanym na okręgu wynosi \(\pi\). Po drugie można zastosować twierdzenie cosinusów dla trójkątów \(ABC\) i \(ACD\).

Oznaczając dla zwięzłości literami długości boków: \(|AB|=a,|BC|=b,|CD|=c,|DA|=d,|AC|=x\) oraz kąty \(\sphericalangle ABC=\alpha\) i \(\sphericalangle CDA=\pi-\alpha\) możemy w Sage napisać dla powyższych trójkątów dwa równania:

Drugie równanie można uprościć i otrzymamy układ równań z dwoma niewiadomymi:

Ponieważ interesuje nas tylko wartość długości przekątnej \(x\) możemy wyeliminować z powyższych równań \(\cos \alpha\). Wynik otrzymamy natychmiast:

Jak to działa?

Wykonaj powyższe polecenie obcinająć kolejne wyrażenia po „kropkach” od lewej by przekonać się jak to działa krok po kroku:

(eq1*c*d + eq2*a*b)
(eq1*c*d + eq2*a*b).solve(x)
(eq1*c*d + eq2*a*b).solve(x)[1]
(eq1*c*d + eq2*a*b).solve(x)[1].rhs()

Rozwiązanie alternatywne

Przypuścmy jednak, że nie pamiętamy ani twierdzenia cosinusów ani nie znamy własności czworokątów wpisanych w okrąg. Można by pokusić się o napisanie układu równań spełnionych przez współrzędne wszystkich punktów oraz promień okręgu, który jest też nieznany!. W sumie mamy \(8+1=9\) niewiadomych! Wynika z tego, że będziemy potrzebowali dziewięciu równań. Współrzędne każdego z punków spełniają równanie okręgu, co daje nam już cztery zależności. Następnie, ponieważ znamy odleglości pomiędzy kolejnymi wspólrzędnymi to mamy znowu cztery równości. Brakuje jeszcze jednej. Zauważmy, że nasz czworokąt wpisany w okrag możemy obracać o dowolny kąt względem środka okręgu. Wybierzmy tylko jedną orientację - na przykład taką w której pierwszy punkt leży na osi \(X\) - co nam da brakujące równanie \(y_0=0\).

Wszyskie te rówania zapiszemy od razu w Sage:

Pozostaje rozwiązać układ dziewięciu równań wielomianowych i otrzymamy rozwiązanie zadania. Bez pomocy algebry komputerowej powyższy układ równań nie wygląda zachęcająco. Okazuje się, że nawet dla komputera jest on problemem - poniższa komenda potrzebuje okolo pół minuty by podać wynik:

Co gorsza, gdybyśmy inaczej poukładali równania, to komputer „męczył” by się z tym układem jeszcze dłużej. Sugeruje to, że proste zadanie maturalne jest wyczerpujące dla komputera. Hmmm - a może po prostu nieumiejętnie go używamy? Zauważmy, że komenda solve jest procedurą rozwiązującą (a przynajmniej próbującą rozwiązać) dowolny układ równań. My mamy wszystkie równania w postaci wielomianów - niewiadome występują tylko w pierwszej i drugiej potędze w mianowniku. Czy nie ma lepszych - wyspecjalizowanych metod w tym przypadku?

Bazy Gröbnera

Istnieje bardzo potężne narzędzie umożliwiające uproszczenie układu równań wielomianowych zwane Bazą Gröbnera. Okazuje się, że z użyciem algorytmu Buchbergera można doprowadzić układ wielomianów do takiego, w którym znalezienie rozwiązania jest bardzo łatwe. Algorytm ten można traktować jako uogólnienie eliminacji Gaussa dla równań liniowych, na przypadek wielomianów. Przekonajmy się sami:

Teraz, można wykonać podstawienia, lub nawet poprosić solve do rozwiązania układu równań, co zostanie wykonane w bardzo krótkim czasie: