Ragnarok. The fabled end of the world, when giants, monsters, and Norse gods battle for the future.
Ragnarok: o lendário fim dos tempos, quando gigantes, monstros e deuses nórdicos batalham pelo futuro.
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.
Os deuses venciam com facilidade, até que surgiu a grande serpente Jörmundgander. Ela engoliu Valhalla, se contorceu ao longo de todo o território e então tornou-se um só corpo contínuo, sem cauda ou cabeça. Enquanto a serpente digere Valhalla, Odin, exausto, explica que ele só tem poder para atacar a criatura com um último raio. Se você amplificar o raio utilizando seu martelo lendário, Mjölnir,
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.
o impacto pode perfurar a serpente. Você correrá com uma supervelocidade ao longo do corpo da serpente. Ao erguer seu martelo, Odin o atingirá com o raio e partirá Jörmundgander naquele ponto. Depois, você continuará correndo ao longo do corpo dela até que cada parte seja destruída. Você não pode correr sobre a mesma seção duas vezes ou cairá em uma parte já atingida. Mas é permitido passar várias vezes sobre os pontos em que a criatura intersecta seu próprio corpo. Se algum ponto não for partido, Jörmundgander se regenerará magicamente,
What path can you take to destroy the serpent?
o último raio de Odin terá sido gasto, e Valhalla cairá para sempre.
Pause now to figure it out yourself!
Qual caminho destruirá a serpente?
Answer in 3 2 1
Pause e tente descobrir! Resposta em três, Resposta em dois, Resposta em um.
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.
Uma forma poderosa de resolver problemas é simplificar. Nesse caso, focaremos duas coisas importantes para o nosso caminho: as interseções e os trechos da serpente entre eles. Ou, como são referidos na teoria dos grafos: vértices e arestas. As arestas são importantes, porque é por elas que vamos nos deslocar. Os vértices são importantes, porque conectam as arestas, e é neles que faremos a escolha de vértice para vértice. Essa forma simplificada em vértices e arestas nos deixa com um objeto matemático importante e universal conhecido como grafo, ou rede. É só descobrir a solução de um Caminho Euleriano, que traça cada aresta uma única vez. Em vez de analisar o caminho por completo, vamos ampliar um único vértice.
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.
Em algum momento do percurso, você entrará e sairá por este vértice, o que dá conta de duas arestas. Se você entrar de novo, precisará sair novamente, o que requer mais um par de arestas. Cada vértice do percurso terá pares de arestas. Uma aresta para a entrada e outra para a saída. Isso significa que o número de arestas que saem de cada vértice deve ser par. Mas existem duas exceções: os pontos de início e fim,
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.
nos quais você pode sair sem entrar, e vice-versa. Se olharmos novamente para a rede, e numerarmos quantas arestas emergem de cada vértice, teremos um padrão, confirmando o nosso raciocínio. Cada vértice tem um número par de arestas que saem dele, exceto por dois. Dessa forma, um desses dois deve ser o início, e o outro, o fim do percurso. Curiosamente, qualquer rede que tenha exatamente dois vértices
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.
com um número ímpar de arestas também terá um Caminho Euleriano. Isso também vale se não existem vértices com um número ímpar de arestas. Nesse caso, o caminho começa e termina no mesmo ponto. Sabendo de tudo isso, voltemos ao nosso grafo.
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.
Podemos começar com essa aresta aqui. Agora, fazemos um ziguezague ao longo de toda a serpente até alcançarmos o fim. Essa é apenas uma solução, e é bom ser sistemático, mas você provavelmente encontrará muitas outras uma vez que você saiba onde começar e onde terminar. Você levanta o martelo no momento certo,
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.
e Odin atira o raio que salvará o mundo. E aí você corre, como nunca correu antes. Se isso funcionar, certamente nada poderá deter o poder dos deuses nórdicos. Se algo assim existisse, e estivesse se arrastando em sua direção... bem, essa história fica para outro dia.