字幕表 動画を再生する
-
Ragnarok. The fabled end of the world,
-
when giants, monsters, and Norse gods battle for the future.
-
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.
-
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.
-
What path can you take to destroy the serpent?
-
Pause now to figure it out yourself!
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.