Ragnarok. The fabled end of the world, when giants, monsters, and Norse gods battle for the future.
Ragnarok, legendarny kraniec świata, gdzie giganci, potwory i nordyccy bogowie toczą bój o przyszłość.
The gods were winning handily until the great serpent Jörmungandr emerged. It swallowed Valhalla, contorted itself across the land, and then merged into one continuous body with no head and no tail. As it begins to digest Valhalla, an exhausted Odin explains that he has just enough power to strike the creature with one final bolt of lightning. If you magnify his blast with your fabled hammer, Mjölnir, it should pierce the massive serpent.
Bogowie bez trudu wygrywają aż do chwili, kiedy pojawia się wielki wąż Jormungand. Pożera Walhallę, osacza całą ziemię i łączy się w jedno ciało bez głowy i bez ogona. Kiedy zaczyna trawić Walhallę, wyczerpany Odyn oznajmia, że ma jeszcze dość mocy, żeby uderzyć węża jednym piorunem. Jeśli zwiększysz jego siłę legendarnym młotem Mjölnir, powinno udać się przebić stwora.
You’ll run with super-speed along the serpent’s body. When you hold your hammer high, Odin will strike it with lightning and split Jörmungandr open at that point. Then, you’ll need to continue running along its body until every part of it is destroyed. You can’t run over the same section twice or you’ll fall into the already blasted part of the snake. But you can make multiple passes through points where the creature intersects its own body. If you leave any portion un-zapped, Jörmungandr will magically regenerate, Odin’s last power will be spent, and Valhalla will fall forever.
Będziesz biec z zawrotną prędkością wzdłuż ciała węża. Kiedy podniesiesz młot do góry, Odyn skieruje w niego piorun, który rozerwie w tym miejscu węża. Następnie musisz biec wzdłuż jego ciała, żeby zniszczyć każdą jego część. Jeśli przebiegniesz jakąś część drugi raz, wpadniesz w już zniszczoną część węża. Możesz jednak wielokrotnie przechodzić przez miejsca, gdzie ciało węża się przecina. Jeśli pominiesz jakąś część, wąż magicznie się zregeneruje. Odyn nie ma już więcej mocy, więc Walhalla przepadnie na zawsze.
What path can you take to destroy the serpent?
Jaką drogę trzeba obrać, żeby całkowicie zniszczyć węża?
Pause now to figure it out yourself!
Skup się i pomyśl!
Answer in 3 2 1
One powerful way to solve problems is to simplify. And in this case, we can focus our attention on the two things that are important for our path: intersections and the stretches of snake between them. Or, as they’re referred to in graph theory, nodes and edges. The edges are important because they’re what we need to travel. And the nodes matter because they connect the edges, and are where we may need to make choices as we run from edge to edge. This simplification into nodes and edges leaves us with a ubiquitous and important mathematical object known as a graph, or network. We just need to figure out how to travel what mathematicians call an Eulerian path, which traces every edge exactly once.
Czasami najprostsze sposoby na rozwiązanie są najlepsze. W tym przypadku możemy skupić się na dwóch elementach, które są ważne dla przebiegu trasy, przecięciach i odcinkach węża między nimi. W teorii grafów nazywa się je wierzchołkami i krawędziami. Krawędzie są ważne, bo to po nich będziemy się poruszać. Wierzchołki też mają znaczenie, bo łączą krawędzie i to nimi będziemy kierować się, decydując, w którą stronę pójść. Dzięki podziałowi na wierzchołki i krawędzie otrzymaliśmy ważną i powszechnie spotykaną strukturę matematyczną zwaną grafem czy siecią. Trzeba tylko znaleźć sposób na przejście tego, co matematycy nazywają łańcuchem Eulera, żeby pokonać każdą krawędź tylko raz.
Instead of looking at the path as a whole, let’s zoom in on a single node. During some moment in your run, you’ll enter that node, and then exit it. That takes care of two edges. If you enter again, you’ll need to exit again too, which requires another pair of edges. So every point along your path will have edges that come in pairs. One edge in each pair will function as entrance; the other as exit. And that means that the number of edges coming out of every node must be even.
Zamiast skupiać się na całości, spójrzmy na pojedynczy wierzchołek. W pewnym momencie dotrzesz do tego wierzchołka i z niego wyjdziesz. Tym samym pokonasz dwie krawędzie. Jeśli znowu do niego wejdziesz, trzeba będzie znowu z niego wyjść, a tym samym pokonać kolejną parę krawędzi. Każdy punkt na trasie będzie więc połączony z parami krawędzi. Jedna krawędź z pary będzie wejściem, a druga wyjściem z wierzchołka. To oznacza, że liczba krawędzi wychodząca z każdego wierzchołka musi być taka sama.
There are just two exceptions: the start and end points, where you can exit without entering, or vice versa. If we look at the network formed by the serpent again, and number how many edges emerge from each node, a pattern jumps out that fits what we just saw. Every node has an even number of edges emerging from it, except two. So one of these must be the start of your route, and the other the end.
Są jedynie dwa wyjątki: początek i koniec, skąd można wyjść bez ponownego wchodzenia i odwrotnie. Jeśli ponownie spojrzymy na sieć utworzoną przez węża i policzymy, ile krawędzi wychodzi z każdego wierzchołka, ukaże się schemat pasujący do tego, co przed chwilą widzieliśmy. Każdy wierzchołek ma równą liczbę wychodzących krawędzi z wyjątkiem dwóch. Jeden z nich musi być więc początkiem trasy, a drugi jej końcem.
Interestingly enough, any connected network that has exactly 2 nodes with an odd number of edges will also contain an Eulerian path. The same is true if there are no nodes with an odd number of edges— in that case the path starts and ends in the same spot.
Co ciekawe, każda sieć, która ma dokładnie dwa wierzchołki i nieparzystą liczbę krawędzi, też zawiera łańcuch Eulera. Jest tak też, kiedy nie ma wierzchołków, a liczba krawędzi jest nieparzysta. Wtedy trasa zaczyna się i kończy w tym samym miejscu.
So knowing that, let’s return to our full graph. We can begin by taking care of this edge here. Now we can zig-zag back and forth across the whole snake until we reach the end. And that's just one solution— it helps to be systematic, but you’re likely to happen upon many others once you know where to begin and end your run.
Mając to wszystko w pamięci, wróćmy do naszego grafu. Możemy zacząć od tej krawędzi. Teraz możemy iść zygzakiem w lewo i w prawo wzdłuż całego węża, aż dojdziemy do końca. A to tylko jedno z rozwiązań. Warto być przy tym systematycznym, ale pewnie wpadniesz na inne sposoby przejścia trasy, skoro już wiadomo, gdzie się zacznie i gdzie skończy.
You hold your hammer high at the opportune moment, and Odin sends the world-saving surge of lightning at you. Then you run like you’ve never run before. If you can pull this off, surely nothing could stop the might of the Norse Gods. And if something like that were out there, slouching its way towards you… well, that would be a story for another day.
W odpowiednim momencie trzymaj młot wysoko, a Odyn ześle uderzenie pioruna, które uratuje ludzkość. Potem biegnij co sił, tak szybko jak jeszcze nigdy. Jeśli tego dokonasz, nic nie zatrzyma potęgi nordyckich bogów. A jeśli coś takiego zbliży się w twoim kierunku... to już zupełnie inna historia.