Wielościany w wielościanach, czyli matematyka eksperymentalna

Czy istnieje coś takiego jak matematyka eksperymentalna? Zobaczmy. Ten tekst zaczniemy od prostego zadania z geometrii, następnie użyjemy komputera, aby rozwiązać je w przybliżeniu, a na koniec z tego przybliżenia zgadniemy dokładny wynik. Będzie też wiele szczegółów do uzupełnienia dla Czytelników. Programy użyte do eksperymentów można znaleźć w [3].

Zadanie z geometrii

Skoro tak dobrze nam poszło, możemy zwiększyć odrobinę stopień trudności:

Za szybko? W takim razie wróćmy do podstaw i spróbujmy powoli uogólnić nasz oryginalny problem w dwóch wymiarach. Kolejnymi kandydatami na uogólnienia są zadania o "Kwadracie w Kwadracie" (mhm...), "Kwadracie w Pięciokącie foremnym" i tak dalej. Moglibyśmy też zapytać o dowolny " $N$ -kąt foremny w $M |$ -kącie foremnym". W przypadku najbardziej ogólnego płaskiego problemu:

Możemy już chyba tylko pomarzyć o eleganckim rozwiązaniu i zdać się na komputer. W ten właśnie sposób dochodzimy do pytania: jak wyrazić nasze zadania w języku zrozumiałym dla komputera?

Programowanie liniowe

Programowanie liniowe pojawiało się niejednokrotnie w Delcie (np.: Kiljan Delta 3/2018, Adamaszek Delta 2/2019, Kowalik Delta 7/2013, Kowalik Delta 2/2020, Wójcik Delta 2/2018). W szkole uczymy się o układach równań liniowych i sposobach ich rozwiązywania. Problem liniowy dopuszcza bardziej ogólnie ograniczenia w postaci równań i nierówności liniowych. Taki układ może mieć zero, jedno lub wiele rozwiązań, a zadaniem programowania liniowego jest znalezienie takiego rozwiązania, które maksymalizuje zadaną funkcję liniową danych zmiennych.

Dla przykładu rozważmy problem liniowy:

zmaksymalizuj 2x + 3y przy założeniach x + y⩽ 2, y ⩽ 1.

Zbiór punktów spełniających założenia tego problemu jest pokazany na rysunku 1 Łatwo sprawdzić, że w tym zbiorze wyrażenie $2x + 3y$ przyjmuje największą wartość 5 w punkcie $(x,y) = (1,1),$ a więc ten punkt jest rozwiązaniem (w tym przypadku jedynym). Problemy liniowe pojawiają się w wielu praktycznych zastosowaniach i, co ważne, można je efektywnie rozwiązywać na komputerze. Procedury do programowania liniowego można znaleźć w większości popularnych pakietów do obliczeń numerycznych, a wyspecjalizowane programy rozwiązują z dużą dokładnością problemy liniowe z milionami zmiennych i ograniczeń.

Wyrazimy teraz zadanie o "Kwadracie w Trójkącie" w tym języku. Ustalmy trójkąt $T$ o wierzchołkach $√ -- v1 = (0,0),v2 = (1,0),v3 = (1 , 1 3) 2 2$ (Rys. 2). Po pierwsze zauważamy, że w języku problemów liniowych możemy opisać postulat "punkt $|x = (x1,x2)$ należy do $|T$ ". Rzeczywiście, są na to nawet dwa sposoby. W sposobie pierwszym wyrażamy fakt, iż punkt $|(x1,x2)$ leży po właściwej stronie każdej z prostych zawierających boki trójkąta:

√ -- x2⩽ 3x1, (x1,x2) ∈T x2⩾ 0,√ -- √ -- x2⩽ − 3 x1 + 3.

Jeżeli nie chcemy pracowicie wyznaczać równań boków trójkąta, możemy użyć innego sposobu. Zapiszemy w nim, że punkt $x$ należy do otoczki wypukłej wierzchołków trójkąta:

x = t1v1 + t2v2 + t3v3, x ∈ T t1 + t2 + t3 = 1, t1,t2,t3⩾ 0.

Ponieważ współrzędne punktów $vi$ uważamy za stałe, powyższe zależności są liniowe w zmiennych $|x1,x2,t1,t2,t3,$ a więc również definiują problem liniowy. Zauważamy też, że obydwa sposoby nadają się do opisania zupełnie dowolnego wielokąta wypukłego $|Q$ (Dlaczego tylko wypukłego?). Jedyne, czego potrzebujemy, to współrzędne wierzchołków $|Q$ lub równania prostych zawierających boki $|Q.$

Potrafimy już zapisać przynależność jednego punktu do ustalonego wielokąta wypukłego $Q.$ Teraz możemy wreszcie wyrazić zadanie "Kwadrat w $Q$ ". Gdyby interesowały nas tylko kwadraty o bokach równoległych do osi współrzędnych, to ułożylibyśmy problem liniowy:

zmaksymalizuj r przy założeniach (x1,x2)∈ Q, (x1 + r,x2)∈ Q, (x1,x2 + r)∈ Q, (x + r,x + r)∈ Q. 1 2

(1)

Faktycznie, jeśli $(x1,x2)$ jest lewym dolnym wierzchołkiem szukanego kwadratu, zaś $|r$ jest długością boku (Rys. 3), to cztery podane założenia wyrażają przynależność wszystkich czterech wierzchołków kwadratu do wielokąta $|Q.$ Optymalne rozwiązanie tego problemu liniowego maksymalizuje długość boku $r,$ a zatem i pole kwadratu.

Jeżeli teraz uwzględnimy w jakiś sposób wszystkie możliwe obroty kwadratu wewnątrz wielokąta, to zadanie będzie rozwiązane! Jesteśmy już bardzo blisko. Dla $|α ∈[0,π/2)$ oznaczmy przez $Qα$ wielokąt $Q$ obrócony na płaszczyźnie o kąt $α .$ Jeżeli wielokąt $Q$ był dany np. poprzez współrzędne wierzchołków, to możemy bardzo łatwo obliczyć wierzchołki wielokąta $|Qα$ i zapisać problem liniowy:

zmaksymalizuj r przy zał o żeniach (x1,x2) ∈Qα , (x1 +r,x2) ∈Qα , (x ,x +r) ∈Q, 1 2 α (x1 +r,x2 + r) ∈ Qα .

(2)

Oznaczmy rozwiązanie problemu (2) przez $r . α$ Jest to długość boku największego kwadratu o bokach równoległych do osi, zawartego w $Qα ,$ a więc i długość boku największego kwadratu zawartego w $Q$ i pochylonego pod kątem $|− α.$ W takim razie $r = max{r α α ∈ [0,π/2)}$ wyznacza długość boku kwadratu, który rozwiązuje zadanie "Kwadrat w $Q$ ". (Dlaczego wystarczy ograniczyć się do $α ⩽ π/2?$ )

Eksperymenty

Oczywiście w praktyce nie możemy rozwiązać problemu (2) dla wszystkich wartości $α,$ ale możemy wziąć ich wystarczająco wiele, aby naszkicować wykres funkcji $|rα$ i przybliżyć maksimum z dużą dokładnością. Wróćmy do zadania "Kwadrat w Trójkącie", od którego zaczęliśmy ten tekst. Wykres $rα$ dla tego problemu znajduje się na rysunku 4 Odczytujemy z niego, że maksimum przypada dla obrotu o $α = 0$ (oraz, oczywiście!, $|α∈ {π/6,π /3}$ ), tak jak początkowo przypuszczaliśmy. Otrzymujemy też przybliżoną wartość $r0≈ 0,464101616,$ która zgadza się z dokładnym wynikiem do 8. miejsca po przecinku. Jako eksperymentatorzy, jesteśmy usatysfakcjonowani zgodnością teorii z praktyką.

Przejdźmy do zadania "Sześcian w Dwudziestościanie". Wprawdzie rozważania w tekście prowadziliśmy na płaszczyźnie, ale wszystko można powtórzyć w trzech wymiarach z nieznacznymi zmianami. W problemie (2) zamiast czterech wierzchołków kwadratu musimy uwzględnić osiem wierzchołków sześcianu, a zamiast $Qα$ musimy rozważyć wszystkie obroty $|Q α,β,γ$ oryginalnej bryły $Q$ w trzech wymiarach. Po tych poprawkach wciąż mamy serię problemów liniowych obliczających poszczególne wartości $|rα ,β,γ .$

Wierzchołki dwudziestościanu foremnego możemy odszukać w literaturze. Przy oznaczeniu $1√ -- 1 τ = 4 5 + 4$ następujące punkty

v1 = (0, 12 ,τ), v2 = (0,− 12 ,τ), v3 = (12 ,τ ,0), 1 1 1 v4 = ( 2 ,−τ,0) , v5 = (τ ,0, 2), v6 = (τ,0,− 2), v = (− 1,τ ,0) , v = (− 1 ,−τ,0), v = (−τ,0, 1), 7 2 8 2 9 2 v10 = (0, 12 ,−τ) , v11 = (0,− 12 ,−τ), v12 = (−τ,0, −21)

stanowią wierzchołki dwudziestościanu foremnego $|D$ o krawędzi długości 1 i objętości $5 √ -- 5 |12- 5 + 4 .$ Implementujemy więc trójwymiarową wersję problemu liniowego (2), rozwiązujemy ją w pętli dla kilkuset wartości $|α,β,γ ∈[0,π /2)$ i... czekamy. Po dłuższym czasie otrzymujemy wynik: krawędź sześcianu ma długość w przybliżeniu

0,93869735489196.

(3)

Otrzymujemy także kąty obrotu dające maksymalny sześcian. Możemy to wszystko narysować. Kilka rzutów największego sześcianu wpisanego w dwudziestościan zostało przedstawionych na rysunkach 5-7.

Rys. 5 Rys. 5	Rys. 6 Rys. 6
Rys. 7 Rys. 7	Rys. 8 Rys. 8

Tak jak poprzednio, domyślamy się, że wynik uzyskany za pomocą komputera nie jest dokładny i że optymalna konfiguracja jakościowo wygląda następująco: dwa wierzchołki $,B A$ sześcianu leżą symetrycznie na dwóch sąsiednich krawędziach dwudziestościanu, dwa inne wierzchołki $,DC$ na antypodycznych krawędziach, a pozostałe leżą wewnątrz ścian dwudziestościanu. Czy możemy stąd pokusić się o obliczenie dokładnych wartości? Otóż tak (Rys. 8). Najpierw znajdujemy końce krawędzi dwudziestościanu, na których leżą punkty $A |$ i $B.$ Okazuje się, że bez straty ogólności można w tym celu wybrać $v1,v2,v3,$ które są w pozycji pokazanej na rysunku. Będziemy zakładać, że

=tv1+(1−t)v2,B=tv1+(1−t)v3,C=−A,D=−B, A

dla pewnego $|t∈ (0,1).$ Jak znaleźć $t,$ dla którego punkty $,B,C,D |A$ są wierzchołkami sześcianu? Jest wiele sposobów, na przykład spełnione musi być równanie

√ C =3 AB .A

Po podstawieniu współrzędnych punktów $,B,C,v1,v2 A$ dostajemy równanie kwadratowe w zmiennej $t,$ które po nieco uciążliwych przekształceniach (może je wykonać za nas komputer, np. pakiet SAGE), przyjmuje postać:

√ -- √ -- √ -- (−3 5− -1) t2 + (3 5 + 5) t− ( 5 +2) = 0. 2 2

Pierwiastkiem tego równania w przedziale $(0,1)$ jest $√ -- |t = ( 5 +7) /22.$ Stąd możemy obliczyć dokładne współrzędne punktów $A$ i $|B,$ a ostatecznie też długość krawędzi sześcianu

75+5 B =22≈0,93874890 A

(porównaj z (3)) i stosunek objętości sześcianu do dwudziestościanu:

- --SA-BS3---= 219-5+15-≈ 0,3791877. 5~12 5+5~4 1331

Reasumując: przybliżenie uzyskane przy użyciu programowania liniowego okazało się wystarczająco dobre, aby odgadnąć dokładny wynik. Czy to rozumowanie jest pełnym dowodem? Niekoniecznie, ale niedaleko mu do dowodu [?]. Czy to rozumowanie stanowi przekonujące rozwiązanie? Raczej tak. Czy istnieje coś takiego jak matematyka eksperymentalna? Zdecydowanie!