Standing on One Vertex

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.

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 one¹. This means that if we label two adjacent vertices with stones, we can learn that they are adjacent with probability one².

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).

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:

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:

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

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 3D³.

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