Diamonds: Teachers' Notes
Introduction
This problem provides an introduction to the world of combinatorial games. This is a rapidly developing area of pure mathematics that may well have some important applications in the real world. A combinatorial game is a game between two people such that both have complete knowledge of the game situation. So games like chess and go are combinatorial games because they are between two people and both players know where all the pieces are and what moves are possible. Poker is not a combinatorial game as neither player knows exactly the order in which the cards will be dealt. Similarly, when two players are playing Monopoly, Snakes and Ladders or any other dice game, they don’t know what numbers are going to come up next so neither of the players has full knowledge of the game.
One of the simplest combinatorial games is Noughts and Crosses. Both players know which squares are available and what moves the other player can make. Bearing this in mind, there is a strategy for the first player. If she plays in a given way she will not lose and may even win. On the other hand, if the second player plays optimally as well, the game must end in a draw.
The aim of mathematicians analysing combinatorial games is to decide if there is a best strategy for either player such that they must be able to force a win no matter what their opponent does. This is the student’s goal in playing this game. Can they see how to manipulate the moves so that their opponent, the computer, has to lose? In other words can the student discover whether they should play first or second in order to beat the computer?
This game of Diamonds then, gives the student a chance to analyse the game and produce a winning strategy for some values of s the number of slots. To do this the student will need to experiment until the game is understood. This provides an opportunity for systematic experimentation and the application of logic.
These notes are not intended to be a sequential description of how to use this activity with students but they should provide you with further information that may help you to better understand the problem and how it might be used to provide a rich mathematical experience for your students. You should also read the Students’ notes for this problem, as they provide specific hints on completing the Bright Sparks activity online.
The one very important thing to note here is that mathematicians have not yet been able to determine for which values of s the student should go first in order to win or for which values of s the computer should go first in order for the student to win. We say more about this later. However, we feel students should know that problems exist that are very easy to state that so far no one has been able to solve. Maybe solving this large problem is a challenge that some students might like to take up.
About the problem
It’s probably a good idea to start by doing some examples to give you an idea of what this problem is all about. Clearly there is no point looking at the situations where the number of slots is less than 4. We’ll leave 4 to you and go straight on to 5. Below we’ll completely analyse the 5 slot game.
The 5 slot game: Notice that by symmetry, slots 1 and 5 are the same, as are slots 2 and 4. This means that the first player can choose 1 or 5 and the end result will be the same. Similarly it doesn’t matter whether the first player chooses 2 or 4.
|
1
|
2
|
3
|
4
|
5
|
This means that the first player (Player A) has 3 choices: slot 1; slot 2; or slot 3. We’ll be systematic.
Case 1: Player A chooses slot 1.
|
X
|
2
|
3
|
4
|
5
|
Player B would be silly to choose slots 2 or 3 because Player A would win immediately. (And remember both players are playing as well as it is possible to play.) So Player B will choose 4 or 5. If Player B chooses either of these, then she must win. Whatever A does next, B will be able to put three diamonds in a line.
So if A chooses slot 1 first, then B will win.
Case 2: Player A chooses slot 2.
|
1
|
X
|
3
|
4
|
5
|
Player B would be silly to choose slots 1, 3 or 4 because Player A would win immediately. (And remember both players are playing as well as it is possible to play.) So Player B will choose 5. Whatever A does next, B will be able to put three diamonds in a line.
So if A chooses slot 2 first, then B will win.
Case 3: Player A chooses slot 3.
|
1
|
2
|
X
|
4
|
5
|
Player B would be silly to choose slots 2 or 4 because Player A would win immediately. But B doesn’t fare any better by choosing slots 1 or 5.
So if A chooses slot 3 first, then A will win.
Looking back over the three cases it is clear that A will choose slot 3 and then be guaranteed a win. So if your student is playing against the computer, in this case the student will choose to play first.
But it isn’t logical to ever play second, is it? Surely in every case the first player has an advantage that can’t be beaten?
So far we have learnt two things about playing and analysing a game like this. First, we are not just looking for a win, we are looking for the best possible result. What we mean by this is that in playing between two friends one may make an error and allow the other to win. But in combinatorial games we assume that no player makes an error. So a win must be achieved no matter how the other player plays.
And second, at least in the early stages, we have to look at every possible case to make sure that we haven’t missed anything. So we have to work systematically through all possible cases. Hopefully we can find some general techniques or some nice ideas or else we won’t be able to tackle any general cases. After all with 1000 slots it looks as if we will need to look at 500 cases. That’s just not practical.
Some possible solutions
We now delve further into the problem to see if we can start to see any patterns. This means trying some more cases
The 6 slot game: In this case, choosing slot 1 is the same as choosing slot 6; slot 2 as slot 5; and slot 3 as slot 4. So we have three cases again.
|
1
|
2
|
3
|
4
|
5
|
6
|
Case 1: Player A chooses slot 1.
|
X
|
2
|
3
|
4
|
5
|
6
|
Slots 4, 5 and 6 are the only choices for B. But Slot 4 corners the market doesn’t it? If B plays 4, A must lose.
Case 2: Player A chooses slot 2.
|
1
|
X
|
3
|
4
|
5
|
6
|
Surely B will choose slot 5.
Case 3: Player A chooses slot 3.
|
1
|
2
|
X
|
4
|
5
|
6
|
Surely B will choose slot 6.
Here we see that B has to win no matter what A does. So this is a second player win game. How about that for a surprise? Your student should let the computer go first here.
The 7 slot game: In this case, choosing slot 1 is the same as choosing slot 7; slot 2 as slot 6; slot 3 as slot 5; and slot 4 is different to them all. So we have four cases this time.
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
Case 1: Player A chooses slot 1.
|
X
|
2
|
3
|
4
|
5
|
6
|
7
|
B avoids 2 and 3 but can win with 4, 5 or 6.
Case 2: Player A chooses slot 2.
|
1
|
X
|
3
|
4
|
5
|
6
|
7
|
B avoids 1, 3 and 4 but can win with 5, 6 or 7.
Case 3: Player A chooses slot 3.
|
1
|
2
|
X
|
4
|
5
|
6
|
7
|
B avoids 1, 2, 4 and 5 but can win with 6 or 7.
Case 4: Player A chooses slot 4.
|
1
|
2
|
3
|
X
|
5
|
6
|
7
|
B avoids 2, 3, 5 and 6. So she has to play 1 (or equivalently 7). A’s only non-losing move is 7. This takes the game to the stage below.
|
X
|
2
|
3
|
X
|
5
|
6
|
X
|
No matter where B goes A will win.
If there are 7 slots then, A’s winning strategy is to take the centre spot.
There is still a lot to be learnt about this game so your students would do well to try several more examples. (We have done the 8 slot game in the Students’ Notes.) In the process they will be able to find results that can be put in a table such as the one below.
|
No of slots
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
|
A wins
|
wins
|
wins
|
|
wins
|
wins
|
wins
|
wins
|
wins
|
|
wins
|
wins
|
|
B wins
|
|
|
wins
|
|
|
|
|
|
wins
|
|
|
It’s about now that students should start to conjecture but do they need more information? Perhaps there is just one conjecture that stands out.
Conjecture: A will win if and only if the number of slots is not a multiple of 6.
At this point we would like to give you the current state of knowledge on this game. We know by computer simulations that for s < 1,000,000, B will win if the number of slots is
6, 12, 22, 30, 32, 44, 54, 64, 76, 86, 98, 110, 118, 132, 134, 162, 170, 184, 194, 202, 282, 290, 302, 356, 1046, 2502, 2752, 2912, 3052, 3076, 7250, 7356, 7866, 16168.
Apparently all values of s for a B win are known up to 225.
From the numbers that we have just given, it can be seen that the conjecture above is false. In fact very little is known about this problem apart from the results above. The one general result that we know is given below.
Theorem: If there are an odd number of slots, A will win.
Click for a proof of this theorem.
We hope that some students will try to find a way to solve some general cases other than s odd.
Extension
The question now is can we take the problem any further. What Diamond-like problems can we build around this one? It’s very important to have this discussion with students at all levels. Extending problems is a fundamental way of working for mathematicians and students should know that. Let us suggest some related problems.
- Which player must win if the number of cells is even?
- What can be said about the game where 4 diamonds must be in a row to win?
- What can be said about the game where d diamonds must be in a row to win?
- What can be said about the game with n diamonds if the squares are in an r x s rectangle?
- What can be said about the 3 diamonds in a row game if there is one 1 by 6 board and one 1 by 8 board? (The winner is the first to get 3 diamonds in a row on either board.)
- What can be said about the 3 diamonds in a row game if there is one 1 by p board and one 1 by q board? (The winner is the first to get 3 diamonds in a row on either board.)
- What can be said about the d diamonds in a row game if there are b boards each of which is a 1 by p board?
