## The Sperner Game

### Text I

Remark: In the images marked with , if you move the mouse over them, you will see an animated gif.

Start out by playing a few games, against another player or against the computer. Use the help link to learn about the playing options and how the applet works.

The rules of the game are quite simple: each player, during his/her turn, places a colored disk over an uncolored one, in such a way that:

1. inside the big triangle, any color can be used;
2. along an outside edge of the big triangle, only the two colors that appear on the end vertices of that edge can be used;
3. the first player to complete a small triangle with three disks of all three different colors loses the game.

If you haven't tried it yet, you can now use the game several games, experimenting with different-sized boards. To vary the size of the board, change the value of $$n$$ and press "Enter". You can either play against the computer or against another player.

You may think of the Sperner game just as a game. Still, try to recall whether there was ever a tie in any of the matches you played. In other words, try to remember whether you have ever reached a situation in the game where:

• all disks were colored, yet
• there was no small triangle with all three vertices of a different color.

In such a scenario, there would be no more moves to play, nor would there be a loser.

Below are some of the many possible outcomes of the game in which there was no tie, as a small triangle with vertices of three different colors does occur. Hence, in all of these four examples, the last player to make a move has lost the game.

For each one of these outcomes, by placing the mouse pointer over the corresponding image, you can see the previous configuration of the board, and verify that no other move could have prevented a small triangle with vertices of three different colors from occurring. Notice that on each of the first three examples there were three possible moves, whereas on the fourth example there were seven. But each one of these 16 $$(16=3+3+3+7)$$ possibilities leads to a small triangle with three colors.

In case you have never tied in any of the games you played, you might wonder if a tie is at all possible. Should you be curious about this, start out by trying to "force" a tie. Experiment with boards of different sizes: $$3, 5, 8,$$ etc. and try to place colored disks so that no small triangle with three colors appears. (You don't need two players to follow this plan: simply, do not select "Play against the computer" and instead place the colored disks, one after the other, ignoring the references to players 1 and 2).

A piece of advice: do not consult the pages that follow until you have performed these attempts.

As we have seen, the images above represent four outcomes of the game where no tie was reached: in all of these cases, a small triangle with three colors has emerged. In these examples, we were assuming that each player was alert, i.e., if a player lost the game by completing a small triangle with a third color, it was because there was no other way of placing a colored disk over an uncolored one to avoid a small triangle with three colors being produced. For example, we are excluding situations such as the following:

If you really want to know whether or not a tie is possible, for a board of any size, you can keep following these pages, where you will find a justified answer to the question of the (im)possibility of a tie. This justification is, in fact, a proof of a statement that has important consequences in mathematics. If you don't have much of a mathematical background, don't be alarmed by the term "proof". This is an important instance in which the correct and complete idea of a proof can be fully conveyed to a lay person.