Delta mi!

Dawno, dawno temu żył sobie beztrosko król wraz ze swoją piękną córką. Jak to czasem w zbyt szczęśliwych królestwach bywa, pewnego razu czarnoksiężnik przybył na dwór, żeby porwać królewnę i uwięzić ją w swojej upiornej wieży. Zgodnie z zasadami dobrego wychowania mrocznych czarodziei, do których należał, musiał dać mieszkańcom królestwa możliwość ocalenia królewny przed swoim niecnym planem...

Tzw. zagadnienie Fermata to pytanie o to, gdzie wewnątrz danego trójkąta należy umieścić punkt aby suma długości odcinków i przyjęła najmniejszą wartość.

W geometrii dyskretnej przyjęło się mówić, że wielokąt jest wpisany w inny wielokąt, gdy ma wierzchołki na prostych zawierających boki tego drugiego wielokąta. Od czasu Hilberta tego zwrotu używa się i w przypadku "zwyczajnej" geometrii.

Na obrazku widać przenumerowanie szesnastu z 17 równo rozmieszczonych punktów na okręgu. Obok "normalnych" czarnych numerków podano dziwnie rozmieszczone czerwone. Zrobiono to w ten sposób, że nawinięto na ten okrąg półprostą, na której zaznaczono punkty odpowiadające kolejnym potęgom 3.

Czy Czytelnik zna grę w przeciąganie liny? Dwie drużyny ciągną dwa końce liny w przeciwne strony, a wygrywa ta, której uda się przeciągnąć linę na swoją stronę. Ściślej, gra kończy się w momencie wyjścia środka liny (zazwyczaj oznaczonego wstążką) z umówionego pola gry. Matematycy przypisują tę samą nazwę podobnej grze rozgrywającej się w dwóch (i więcej) wymiarach, w której to środek liny może poruszać się w wielu kierunkach, a nie tylko lewo-prawo. Trudno sobie jednak takie przeciąganie wyobrazić, dlatego przyjąłem termin gra w sumo.

Czy zastanawialiście się kiedyś nad tym, czym jest inteligencja? Większość definicji zakłada posiadanie zdolności do rozumowania, uczenia się, adaptacji do zmieniającego się otoczenia. Najczęściej mówi się o inteligencji ludzi i zwierząt - organizmów mających mózg, a więc organ biologiczny. Czy inteligencja musi być jednak domeną jedynie istot, które uważamy obecnie za żywe? Wielu Czytelników słyszało zapewne również o inteligencji "sztucznej", określanej tak dlatego, że nie występuje ona w sposób naturalny w przyrodzie, ale w emergentny sposób pojawia się w maszynach i algorytmach tworzonych dzięki innej inteligencji, np. człowieka.

Jednym z ważniejszych osiągnięć informatyki opartej o komputer kwantowy, które zresztą eksponujemy w tym numerze Delty, jest opracowanie efektywnego (wielomianowego od rozmiaru danych) algorytmu na rozkład dużych liczb na czynniki pierwsze. Wspaniały, budzący zachwyt wynik. Nie dość, że przepiękny, korzystający z bardzo ładnego fragmentu matematyki, to jeszcze pozwalający wierzyć, że komputer kwantowy złożony z kubitów jest istotnie lepszy od komputera klasycznego, zawierającego pamięć o bitach. Albo inaczej: że (też prezentowany w tym numerze) model obliczeń komputera kwantowego ma istotnie większą siłę wyrazu (przy założeniu wielomianowego czasu działania) niż klasyczny model Turinga czy inne równoważne.

W 1994 roku Peter Shor, pracujący wówczas w Bell Labs w New Jersey, pokazał, jak przy użyciu hipotetycznego komputera kwantowego rozłożyć w czasie wielomianowym dowolną liczbę naturalną na czynniki pierwsze. W tamtym czasie algorytmy kwantowe dopiero raczkowały. To właśnie odkrycie Shora spowodowało wielki rozwój tej dziedziny. Społeczność informatyków zrozumiała, że gdyby udało się zbudować komputer kwantowy rozsądnej wielkości, to świat stałby się istotnie inny. Nie jest bowiem znany żaden algorytm dla problemu faktoryzacji, czyli rozkładu na dzielniki pierwsze, który działa w czasie wielomianowym na komputerze klasycznym. Co więcej, nawet nie znaleziono algorytmu losowego, który z dużym prawdopodobieństwem w zazwyczaj niedługim czasie faktoryzuje liczbę: nie jest po prostu znana zupełnie żadna rozsądna heurystyka...

Jeżeli określimy dodawanie i mnożenie punktów płaszczyzny, z wyróżnionymi punktami 0 i 1, w sposób przedstawiony na rysunku, to otrzymamy liczby zespolone...

...z których żadne dwie nie są równoległe, a żadne trzy nie mają punktu wspólnego... tworzą cztery trójkąty - to każdy widzi i nikt się nie dziwi.

Oto kilka zadań związanych z istnieniem i własnościami pewnych krzywych lub łamanych na płaszczyźnie i w przestrzeni trójwymiarowej.

- Lolek, chodź, pokażę Ci jedną stronę w Internecie...

Ustalenie wspólnego stanowiska przez grupę ludzi wymaga często w pierwszym kroku wyboru metody podjęcia zbiorowej decyzji. Kluczowe stają się wówczas pytania: Jaka metoda jest sprawiedliwa? Jaka metoda najlepiej odzwierciedli preferencje członków grupy?

Poniższa opowieść była na tyle ważna dla młodego, zaledwie dwudziestoletniego, matematyka Évariste'a Galois, że poświęcił ostatni dzień przed pojedynkiem, aby spisać ją w liście do przyjaciela. Niestety, nie dostał od losu szansy na kontynuowanie swoich prac, ale jakiś czas po jego śmierci matematycy zrozumieli znaczenie jego pomysłów. Ślady teorii, z której zarysem Czytelnik zapoznać się może w dalszej części artykułu, odnaleźć można w wielu gałęziach współczesnej matematyki. Jej bezpośrednim następstwem jest wiele efektownych rozwiązań problemów, których ludzkość szukała przez setki lat: nierozwiązalność (przez pierwiastniki) równań wielomianowych stopnia 5 lub wyższego, niekonstruowalność pewnych wielokątów foremnych (cyrklem i linijką), a także niewykonalność klasycznych konstrukcji geometrycznych, czyli podwojenia sześcianu, trysekcji kąta i kwadratury koła.

Odcinek widać z punktu pod kątem , gdy Z twierdzenia o kątach wpisanych wynika, że jeśli punkty i leżą na okręgu po tej samej stronie jego cięciwy to widać ją z i pod tym samym kątem (Rys. 1).

W Delcie 7/2017 przedstawiliśmy kilka "olimpijskich" zastosowań twierdzenia Combinatorial Nullstellensatz. Okazuje się, że zamiast "zwykłych" wielomianów wielu zmiennych możemy rozważać wielomiany o współczynnikach będących resztami z dzielenia przez pewną liczbę pierwszą z dodawaniem i mnożeniem modulo Poniżej przedstawimy trzy klasyczne twierdzenia, których proste dowody są oparte na Combinatorial Nullstellensatz w wersji "resztowej". Twierdzenia te są szczególnie bliskie zastosowaniom olimpijskim.

Astrofizycy ostatnio twierdzą, że "Wszechświat jest płaski", co w ich żargonie oznacza, iż średnia krzywizna Wszechświata jest równa zeru (i tylko lokalnie jest zakłócana przez grawitację). Jeśli mają rację, to matematyka dowodzi, że Wszechświat przyjmuje jeden z 18 możliwych kształtów.

Doświadczenie, polegające na wielokrotnym rzucaniu monetą (symetryczną lub nie) ma tę zaletę, że każdy ma jakieś wyobrażenia dotyczące wyników. Nietrudno na przykład uwierzyć, że stosunek liczby orłów do liczby rzutów nie będzie się wiele różnił od - prawdopodobieństwa otrzymania orła w pojedynczym rzucie.

Każdy zna twierdzenie o kącie zewnętrznym trójkąta: jest on równy sumie kątów wewnętrznych do niego nie przyległych (Rys. 1), co bierze się z faktu, że suma kątów przyległych jest równa sumie kątów trójkąta. Z twierdzenia tego wynika nietrudno twierdzenie o kącie wpisanym i środkowym: kąt wpisany jest równy kąta środkowego opartego na tym samym łuku.