Diamonds: Students' Notes
Introduction
These notes are designed to provide you with hints to help you while you work towards solving this problem and also to help you see a much larger picture of both the problem and of mathematics itself. The activity is available online at:
The notes below are split into four phases:
- Understanding and solving specific problems
- Generalising
- Proving
- Extending
The four phases are the same as those used by mathematicians when they are working on research problems. Of course, if you only want to go as far as solving the diamonds problem for a specific number of slots, you won’t need to go through all of these phases. However, the problem is certainly set up for you to do more than just find a strategy for beating the computer in one or two situations.
Below we have provided a number of hints for you to use if you need help. Try to do as much of the problem as you can yourself, and only use the hints if you get stuck.
Phase 1: Understanding and solving specific problems
This activity is about a game that you play against the computer. You have to take it in turns to place diamonds in slots and try to be the first to put three diamonds in a row. It is kind of like Noughts and Crosses, except that all of the slots are in a row instead of on a 3 x 3 grid and both players use diamonds rather than separately use Noughts and Crosses. The playing space can be any number of slots long and you get to choose whether you want to go first or whether you want the computer to.
This problem is an example of a combinatorial game. A combinatorial game is a game between two players such that both have complete knowledge of the game situation. So games like chess and go are combinatorial games because they are between two players, both of whom know where all the pieces are and what moves are possible. Dice and card games are not combinatorial games because neither player knows what number will be rolled or card will be drawn next.
The aim of mathematicians analysing combinatorial games is to decide if there is a best strategy for either player such that they can force a win no matter what their opponent does. This is your goal in playing this game because you presumably want to beat the computer. Can you see how to manipulate the moves so that your opponent, the computer, has to lose? In other words can you discover for what size boards you should play first and when you should let the computer play first?
Hint 1
The first thing you should try is playing a few games against the computer. Try playing first with a fixed number of slots but vary whether you or the computer goes first and vary the way you play your diamonds. Are there any strategies that you notice working?
Hint 2
You should have noticed that the player who places a diamond beside one that is already there, or only leaves one slot between two diamonds, loses because the other player can then make three in a row.
Hint 3
If you leave either two, three or four slots between two diamonds, the computer cannot place another diamond between them without letting you win. If you leave five or more slots between two diamonds, the computer can safely put one between them.
Hint 4
Can you find any numbers of slots where you can always beat the computer?
Hint 5
Can you find a strategy that works for a lot of different numbers of starting slots?
Hint 6
Is there a strategy that lets you always win if there are an odd number of slots and you go first?
Hint 7
For an odd number of slots, if you go first, place the first diamond in the middle slot. How can you then be sure that you will win?
Hint 8
If, for an odd number of slots, you place your first diamond in the middle slot and then mirror the computer’s moves (place your diamond in the same slot, but on the opposite side of the centre) then the computer will always need to give you a chance to win before you give it a chance.
Hint 9
Can you always win for even numbers of slots?
Hint 10
How can you always win the game if there are six slots?
Hint 11
If there are six slots you can always win the game if you make the computer go first. No matter where the computer places their first diamond, you can place yours in the furthest away slot from theirs. There will then be no safe slot left for the computer. Does this mean that to win with an even numbers of slots you should always let the computer go first?
Hint 12
With eight slots, if you place your first diamond in either of the two middle slots then there is only room to place one diamond safely on each side. The computer will play in one of them and you can play in the other. So with eight slots you should start. So for even numbers of slots sometimes you should go first and sometimes you should make the computer go first. Can you work out any rules or strategies to guarantee that you will win?
Phase 2: Generalising
In generalising a problem we are trying to find a set of rules that always work for that particular problem. Suppose that you are using a board with s slots. For which values of s should you play first in order to win and for which values of s should you let the computer go first?
Hint 13
How might you display data to provide evidence for a conjecture?
Hint 14
What seems to be special about the case where s is a multiple of 6?
Hint 15
What can you say about s odd?
Hint 16
For an odd number of slots, if you go first, place the first diamond in the middle slot. How can you then be sure that you will win?
Hint 17
If, for an odd number of slots, you place your first diamond in the middle slot and then mirror the computer’s moves (place your diamond in the same slot, but on the opposite side of the centre) then the computer will always need to give you a chance to win before you give it a chance.
Can you find justifications for any other general values of s? Please email us at derek@nzmaths.co.nz if you can. The point is that mathematicians so far have been unable to completely solve this problem. This makes it difficult to find more results but very well worth while if you do. Solving anything else here would be a step forward for combinatorial game theory.
Phase 3: Proving
It is important to realize that there are some problems that are relatively easy to state and to understand that mathematicians cannot solve. So if you are wondering what problems some mathematicians are working on, this kind of problem is one of them. For what values of s will you be able to win by playing first and for what values of s is it better to play second? When s is odd the situation is clear. But can you do any better than that? Can you find some general values of s that playing first (or second) is best? There is a good chance that you can settle this problem for s odd but what about other infinite sets of values of s?
As far as we can find out, for s less than a million, the second player will win positions for s equal to
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.
For all other values less than a million, the first player will win. What is so special about these numbers of slots? It certainly seems to be a weird list.
Hint 18
Can you prove that the first player will always win the game if s is odd?
Hint 19
Can you find a strategy for any other infinite values of s?
Phase 4: Extending
The question now is can we take the problem any further? What Diamond-like problems can we build around this one? Extending problems is a fundamental way of working for mathematicians and students should know that. What’s more thinking up these extensions is a lot of fun and requires very little hard work. 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?
Some of these questions are more interesting than others. Many of them use similar techniques to the ones that we have used above. However, where the numbers are increased, there is usually more work required without introducing any new ideas.
