I love games that require no special equipment because they can be played at a moment’s notice. This is one of my favourite pen-and-paper games. It is played on the complete graph K6. In other words, a board with six dots where each dot is connected to every other dot by a line.
Although the game-board can be drawn up for each game, I like to have pre-printed boards which can be put inside plastic sleeves for use with erasable marker pens.
To play, two players each choose a different colour. They take turns colouring any uncoloured lines between two dots. The first player to complete a triangle made solely of their colour loses.
A natural question to ask when playing games is whether or not there will always be a winner (or loser), or if the game can end in a draw. (We are also often interested in whether there is an advantage in being the first (or second) player.) Play a few times. What do you think?
What I like about this game is that the reasoning required to determine if there will always be a winner is accessible by many children and adults, but it is also the entry point into a rich area of mathematics called Ramsey theory.
Warning: the rest of this post contains mathematical spoilers.
The game described earlier is called Sim, after the mathematician Gustavus Simmons who was the first to propose it. It is also equivalent to a puzzle posed in The American Mathematical Monthly in 1958. ‘Prove that at a gathering of any six people, some three of them are either mutual acquaintances or complete strangers to each other.’ That is, we can represent the six people by six dots. We can colour the lines between two acquaintances in red and the lines between two strangers in blue. The problem now is to prove that no matter how the lines are coloured, we can not avoid producing either a red triangle (between three acquaintances) or a blue triangle (between three strangers).
So, if we can prove that we cannot avoid producing a triangle of either colour, then we have proven that the game can never end in a draw. (In fact, computer search has verified that the second player can win with perfect play.)
Consider the diagram below. There are five edges leaving node A. In a completed game, they will be coloured red or blue. At least three of them must be of the same colour, say red. Now, in triangle ABC, edge BC must be blue (else we have a red triangle). Similarly, in triangle ABD, edge BD must be blue. And, in triangle ACD, edge CD must be blue. But, we have just formed a blue triangle: BCD!
We could have posed this question in reverse, that is, what is the minimum number of guests that must be invited to a party so that at least three guests will be acquaintances or at least three guests will be strangers.
The game of Sim shows that it is possible to invite six people to a party and have either at least three guests as acquaintances or at at least three guests as strangers. We can show that this is the minimum number of guests by considering a party with five people and showing that it is possible to have no triangle of the same colour between any three people.
Sim is a demonstration of the Ramsey number R(3,3) = 6. In the language of parties, the Ramsey number R(m,n) = p says that p is the minimum number of guests required at a party so that at least m guests are acquaintances or at least n guests are strangers.
There is a lot written about Ramsey numbers; I’ve barely scratched the surface here. (I first read about them in Martin Gardner’s Colossal Book of Mathematics.) Finding Ramsey numbers is an active area of mathematical research, partly because they are fiendishly hard to calculate. At present, only a handful are known. The last word is for Paul Erdös, the great Hungarian mathematician. (The extract is from The Australian newspaper on Wednesday 21 April 1993 when Australian mathematician Brendan McKay and American colleague Stanislaw Radziszowski found R(4,5)=25).
If an evil demon threatened to destroy the Earth in two years unless we could tell him the value of R(5,5), our correct response, said Erdös, should be to devote all mankind’s resources to the problem — we could probably solve it in two years. But if the demon instead asked us to tell him the value of R(6,6) — then, said Erdös, we should devote all our resources to finding a way to kill the demon.
Wonder in Mathematics 