Sole Survivor: 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:
http://www2.nzmaths.co.nz/frames/brightsparks/solesurvivor.asp?applet
http://www2.nzmaths.co.nz/frames/brightsparks/solesurvivor.asp?applet
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 Sole Survivor problem for specific blocks of stones, you won’t need to go through all of these phases. The problem is certainly set up for you to find more than a strategy for reducing a few specific blocks to their sole survivor.
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 an example of a solitaire game. There are many of these commercially available that involve removing all but one peg from a board. The other pegs are taken from the board after a peg has jumped over them
This game of Sole Survivor then, gives you a chance to analyse the game and produce a strategy that will work for different sized blocks of stones. To do this you will need to experiment until the game is understood. This provides an opportunity for systematic experimentation and the application of logic.
Hint 1
The first thing you should try is to experiment with a few small blocks. The game suggests that you first try the ‘standard sizes’ of 2 x 2, 2 x 3, 2 x 7, 3 x 7 and 4 x 7 blocks.
Hint 2
To move a stone you click on it and then click on the free space on the other side of a neighbouring stone. The stone will then move to that space and the neighbour will be removed.
Hint 3
In the 2 x 2 case if your first jump is any jump except a diagonal one and you only use one stone for jumping you should get a sole survivor. Make three jumps back to where you started.
Hint 4
With the 2 x 3 block, try starting by making a couple of jumps with a middle stone before using a corner stone.
Hint 5
With the 2 x 7, and indeed with all of the bigger blocks, it’s useful to either try to reduce it to a smaller block that you can do or find a pattern of moves that you can repeat until you have produced something smaller that you can already do.
Hint 6
Try to reduce the the 3 x 7 block down to a 3 x 4 block.
Hint 7
What smaller, rectangular block can you get this down to? Or is there a better way?
This problem is one which is likely to require a lot of experimenting before you can solve all of the blocks. The following hints suggest an order in which to explore the problem. If you need more help, you could look at the information on the Sole Survivor proof page.
Phase 2: Generalising
In this section we are looking to make some conjectures about what blocks we think may be able to be reduced to a sole survivor that is sitting in the same cell at the end as it was in the beginning.
Hint 8
It’s not necessary to start first with 2 x n blocks and then do 3 x n blocks and then do 4 x n blocks and then larger blocks, but this might be helpful.
Hint 9
Do all values of n lead to a sole survivor in the 2 x n case? Can this be done by using a pattern of moves or by reducing the 2 x n block to a smaller block with two rows?
Hint 10
What do you think of this conjecture?
Conjecture 1: Any 2 x n block with n ≥ 2 can be reduced to a sole survivor.
What’s wrong with n = 1?
Hint 11
Do all values of n lead to a sole survivor in the 3 x n case? Can this be done by using a pattern of moves or by reducing the 3 x n block to a smaller block with two rows?
Hint 12
What do you think of this conjecture?
Conjecture 2: Any 3 x n block with n ≥ 3 can be reduced to a sole survivor.
Note that if n = 2 then the block is included in Conjecture 2.
Hint 13
Do all values of n lead to a sole survivor in the 4 x n case? Can this be done by using a pattern of moves or by reducing the 4 x n block to a smaller block with two rows?
Hint 14
What do you think of this conjecture?
Conjecture 3: Any 4 x n block with n ≥ 4 can be reduced to a sole survivor.
Note that if n = 2 or 3 then the block is included in Conjecture 2 or 3.
Hint 15
Do all values of n lead to a sole survivor in the m x n case? Can this be done by using a pattern of moves or by reducing the m x n block to a smaller block with two rows?
Hint 16
What do you think of this conjecture?
Conjecture 4: Any m x n block with m ≥ 2 and m ≥ 2 can be reduced to a sole survivor.
Phase 3: Proving
At this point we need to find proofs for all of these conjectures.
Hint 17
What reductions have you found to reduce a 2 × n block? Do they lead to 2 × n’ blocks where n’ < n?
Hint 18
Do you have to look at some special cases? Are their some values of n that have to be done on their own?
Hint 19
We suggest that you look for a way to reduce the 3 x n block to a 3 x (n – 3) block. But there are possibly other ways to prove Conjecture 3.
Hint 20
Do you have to look at some special cases? Are their some values of n that have to be done on their own?
Hint 21
We suggest that you look for a way to reduce the 4 x n block to a 4 x (n – 3) block. But there are possibly other ways to prove Conjecture 3.
Hint 22
Do you have to look at some special cases? Are their some values of n that have to be done on their own?
Hint 23
We suggest that you look for a way to reduce the m x n block to a m x (n – 3) block. But there are possibly other ways to prove Conjecture 3.
Hint 24
Do you have to look at some special cases? Are their some values of n that have to be done on their own?
Hint 25
So you should have been looking in each case for (i) some small cases that you could easily reduce to sole survivors and then (ii) some ways of reducing every block to those special small cases.
Phase 4: Extending
The question now is can we take the problem any further. What Sole Survivor-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 stones can be the last survivor? (Do they all have to be in a corner of the block?)
- What can be said about the game on a ‘triangular’ board?
- What can be said about the game in 3d?
