The Sperner Game Resize


Text IV

We have just seen that, if there is a path going into the right-hand side of the large triangle and not going out through that side, then that path necessarily comes to a halt inside a small triangle. Furthermore, we have already seen that a path can only end inside of a small triangle if that triangle is tricolored.

Hence, to conclude that there must always be a small tricolored triangle, it is enough to show that there is always a path coming from the right-hand side of the large triangle but not going out through that side.

Let us look more carefully at the color changes (red to green and vice-versa) as we go through the right-hand side of the triangle along the direction we chose in the beginning (the counter-clockwise orientation which, in the particular case of the right-hand side of the triangle, corresponds to going upwards and to the left). As we always start out with a red vertex, the first change that can occur must be from red to green and the second one must be the opposite (from green to red). Thus the color changes alternate from red to green and green to red.

In these two images, the numbers in parentheses refer to the color changes in the opposite direction. As the first disk is always red and the last one is always green, overall there is one more change in color in the right direction than there is in the wrong direction.

Now:

  1. whenever there is a change in color in the right direction, there is a path that starts, and
  2. of these paths, the ones that go out of the triangle (necessarily through that same side) do so between a red and a green disk, but this change in color, as the path goes out, is in the wrong direction.

The conclusion is: since there are more color changes in the right direction than in the wrong one, not all paths can go outside of the large triangle. So, there is at least one path that comes to a halt inside of a small tricolored triangle, i.e., there is always such a triangle, and, thus, there can never be a tie!


All of our paths originated from the same side (the red-green side). A similar reasoning could have been carried out for any of the other two sides of the large triangle.

If, in the game, you click on the tip of each arrow of the small triangle in the upper left-hand corner, you can have all paths appear or disappear. Experiment a bit and observe the outcomes. Here are a few examples we have produced: