Standing on One Vertex


a) You are standing on one vertex of an icosahedron. You'd like to reach the opposite vertex by walking along the edges. Unfortunately, every time you reach a vertex, you get turned around and forget which way you were pointing, which makes this difficult. Luckily, you have some stones with distinct colours that you can set down and move as desired to mark vertices (though you can't mark their orientations). You'd like to (with probability 1) reach the vertex opposite your starting point and declare with certainty that you're standing on it. How many stones do you need?

b) What about the same problem on a dodecahedron?

c) Again, same problem, but on an infinite square grid, and you want to reach one of the four (±100, ±100) points.

Partial solution


We’re going to prove that we can do question (a), the icosahedron, with 4 stones.

Here’s a graph of an icosahedron. Imagine replacing all the edges of the icosahedron with something stretchy and then take one face of the icosahedron and stretch it so that everything else lies inside it. It doesn’t look like an icosahedron any more, but we haven’t changed anything about how the vertices and edges are connected, so if we can find our way from one vertex to the opposite vertex on this graph then we can do it on the icosahedron.

Koko90, CC BY-SA 3.0, via Wikimedia Commons

We’ve labelled a pair of opposite vertices A and B (if you stare at an icosahedron, you’ll see that vertices are opposite if and only if the shortest path between them is length 3). The challenge is to get to B, starting from A.

A key fact is that if we randomly walk along the edges of the icosahedron (which is the only way that we can walk around the icosahedron, because we can’t identify the edges), the probability that we eventually hit any given edge is one1. This means that if we label two adjacent vertices with stones, we can learn that they are adjacent with probability one2.

So, here’s how we find our way from A to B. First mark A with a red stone and traverse an edge. Mark the new vertex with a yellow stone. Now traverse another edge. If we’re not back at the red stone, mark the vertex with green. If we are back at the red stone then keep walking until we hit the yellow stone again and take one step away from it again. Repeat this until we find a vertex next to the yellow stone that is not the red stone.

Now, we know that yellow is next to red and that green is next to yellow, so we are in one of the 2 following situations (obviously, the yellow and green stones might not have landed on exactly those vertices, but we can rotate the icosahedron so that things line up).

Koko90, CC BY-SA 3.0, via Wikimedia Commons

Koko90, CC BY-SA 3.0, via Wikimedia Commons

In the first case, the green stone is also a neighbour of the red stone. In the second case, it isn’t. The first case is the case that we want. To determine that we are in the first case, we can do the following:

Randomly walk around the icosahedron; if we ever pass directly between the green stone and the red stone, then we know that we are in Case 1. So we set a threshold, e.g. 100 moves. If we haven’t established that the red and green stones are neighbours in that time, then we think that we are probably in Case 2 (although we are not definitely there - maybe we just got very unlucky with the path that we took). So now we pick up the green stone the next time that we see it; keep walking until we find the yellow stone and then replace the green stone at a vertex next to the yellow stone. We now repeat this process - hopefully we establish that we are in Case 1, but if we haven’t established that the stones are neighbours after 100 moves, we move the green stone again.

It might take a while, but with probability 1, we will eventually find ourselves definitely in Case 1.

What we’ve just done is establish a technique for placing a stone next to 2 other stones. We can re-use this technique to place a purple stone at a vertex next to both the yellow and green stones, but is not already occupied by the red stone. There’s only one such vertex, it’s here:

Koko90, CC BY-SA 3.0, via Wikimedia Commons

Now we pick up the red stone and place it on a non-yellow neighbour of the green and purple stones. Again, this is uniquely determined:

Koko90, CC BY-SA 3.0, via Wikimedia Commons

And finally, we pick up the yellow stone and place it on a non-green neighbour of the purple and red stones:

Koko90, CC BY-SA 3.0, via Wikimedia Commons

Because there was only one choice for the placement of the purple stone and the re-placement of the red and yellow stones, we know that the yellow stone is at vertex B and we can declare victory!

Once you know how to do the icosahedron, the dodecahedron involves very similar arguments (although the required number of stones is different!). For the infinite lattice, we need a theorem that was first proved by George Pólya that says that the probability that we eventually hit any edge is still 1. Interestingly, Polya’s theorem says that this true in 2D, but not in 3D3.

What we have not done here is to prove a lower bound. Is it possible to solve the icosahedron using only 3 stones?

1. Why is this? Well suppose that we just randomly jumped from one edge to another. The probability that we haven’t hit a given edge after n jumps is (29/30)^n and as n gets bigger, this number gets arbitrarily close to zero so the probability that we do hit an edge becomes arbitrarily close to one and so the probability that we hit the edge eventually is one. When we walk around the edges, we’re not randomly jumping, so the probabilities are a bit more complicated, but the idea is the same.

2. The converse is not true -- we can never know that two vertices are not adjacent with probability one, because maybe we were just very unlucky and never took that edge.