Library · Amusements in Mathematics · Chapter 21
Puzzle Games
Agame is a contest, Dudeney says, and a puzzle is something to be solved; a game whose winning play is fully known stops being a game and becomes a puzzle. He points to noughts and crosses, which between two players who understand it should always be drawn. Each game in this chapter looks like a contest between two players, but he shows in every case how one of them can win by playing correctly, so they are really puzzles, and the interest lies in finding the winning method.
That makes them well suited to a program. A game with a limited number of positions can be solved completely by working backwards from its end. A position is lost for the player to move if every move leads to a position won for the other player, and won if at least one move leads to a position lost for the other player. Positions that never become either are draws. Where Dudeney names a winner, and the number of moves the win takes, that analysis confirms or corrects him.
No. 392. The Pebble Game
Two players place an odd number of pebbles, say fifteen, between them, and each in turn takes one, two or three. When all are gone, the one who holds an odd number wins: seven against eight wins, six against nine loses. Should the first or the second player win, and how? Then try it with thirteen.
No. 393. The Two Rooks
Each player has a single rook. The first places his rook on any square, then the second, and they then move in turn, each trying to take the other’s rook. A rook may not pass through a line of attack without being taken: in the diagram, with Black to play, he cannot go to g8 or h8, because he would cross the line of fire at f8, nor to a2 or a1. The game can never be drawn; sooner or later one rook must fall. The trick of winning is ridiculously simple when you know it. What is it?
No. 394. Puss in the Corner
One player puts a counter on 6, the other on 55, and they move alternately, each moving his counter to any other number on a line through it. If your opponent at any time moves on to one of the lines you occupy, or even crosses one of them, you capture him and win. In an illustrative game A moves from 55 to 52, B from 6 to 13, A to 23, B to 15, A back to 26, B back to 13, A to 21, B back to 2, A to 7, B to 3, A to 6, B must go to 4, A settles at 11, and B must be captured next move, since he is compelled to cross a line on which A stands. Which player should win, and in how many moves?
No. 395. A War Puzzle Game
The British general places his counter at B and the enemy his at E. The Britisher moves first, along a road to the next town; then the enemy moves to one of his neighbouring towns, and so on in turn, until the British general reaches the town where the enemy is and captures him. Each must always move along a road to the next town only, and the enemy may do his utmost to avoid capture, yet the British general must infallibly win. How?
No. 396. A Match Mystery
Mr Stubbs counts out thirty matches and divides them into three unequal heaps, 14, 11 and 5. The players draw alternately any number from any one heap, and whoever draws the last match loses; since Stubbs formed the heaps, Wilson draws first. When Wilson takes the whole 14, Stubbs takes 6 from the 11, and two equal heaps are a certain win, except 1 and 1, since whatever Wilson does in one heap Stubbs repeats in the other. They begin again. Wilson leaves 8, 11, 5; Stubbs 8, 11, 3; Wilson 8, 5, 3; Stubbs 6, 5, 3; Wilson 4, 5, 3; Stubbs 4, 5, 1; Wilson 4, 3, 1; Stubbs 2, 3, 1; Wilson 2, 1, 1; and Stubbs reduces it to 1, 1, 1. Wilson never had a chance. There are just thirteen ways of grouping the thirty matches at the start for a certain win. What are they?
No. 397. The Montenegrin Dice Game
Two players each choose a different pair of odd numbers, all higher than 3, and toss three dice in turn. Whoever first throws a total equal to one of his numbers wins; if both succeed in successive throws it is a draw, and they try again. Which two pairs give both players an exactly even chance?
No. 398. The Cigar Puzzle
Two men sit at a square table. One places an ordinary cigar, flat at one end and pointed at the other, on the table, then the other does the same, and so on alternately, no cigar being allowed to touch another. Which player should place the last cigar, if both play in the best possible manner? The table is at least two feet square and the cigar no more than four and a half inches long, and all the cigars are exactly alike. Should the first player or the second win?
The Pebble Game
With fifteen pebbles the first player wins by taking two. After that, when he holds an odd number he should leave 1, 8 or 9 pebbles, and when he holds an even number, 4, 5 or 12; he can always do one or the other until the end. With thirteen the first player loses against correct play. In general the first player loses only when the number is 5, or 5 more than a multiple of 8: 13, 21, 29 and so on.
A program settles every position of the game, counting the pebbles left and whether each player holds an odd or even number. With fifteen, taking two is the only winning first move. The numbers worth leaving are exactly Dudeney’s, 1, 8 and 9 holding an odd number and 4, 5 and 12 holding an even one, apart from the end of the game and the first move itself. The first player loses with 5, 13, 21 and so on, and with no other odd number up to 101.
Answer The first player, taking two first
The Two Rooks
The second player always wins. He must place his rook, and afterwards always move it, on the same diagonal as his opponent’s rook. In the diagram, if Black had placed his rook first, White would place his at A, or anywhere on the diagonal from A to H, and win next move, since the Black rook has no safe square left. If White had placed first, Black should place his rook at B (F gives White more room). Then if White goes to C, Black goes to D; White to E, Black to F; White to G, Black to C; White to H, Black to I; and White has no safe move.
A program worked through all 3,136 positions in which the rooks do not already attack each other, and found that none is drawn and that the player to move loses in exactly the positions where the two rooks stand on a common diagonal. Dudeney’s rule is therefore the whole truth about the game: whatever square the first rook takes, the second player has a square on its diagonal, and he can keep the rooks diagonal until the other is cornered. His line of play from the diagram was also replayed, and every move is legal.
Answer The second player, keeping on the same diagonal
Puss in the Corner
Dudeney’s answer is that A, starting at 55, must win whether he plays first or second: moving first he can always capture B on his twelfth move, and moving second on his fourteenth. His point is always to get diagonally in line with his opponent, and moving first he goes to 33. Two good games, A’s move before the hyphen and B’s after it:
A first: 33–8, 32–15, 31–22, 30–21, 29–14, 22–7, 15–6, 14–2, 7–3, 6–4, 11, and A must capture on his twelfth move.
A second: –13, 54–20, 53–27, 52–34, 51–41, 50–34, 42–27, 35–20, 28–13, 21–6, 14–2, 7–3, 6–4, 11, and A must capture on his fourteenth move.
That is right for a board with a line joining 48 and 49, and wrong for the board as it is printed:
In the diagram, 48 is not joined to 49, though each of the other three corners has the matching line: 5–6, 11–12 and 55–56. A program modelled both boards, with every line as drawn, a counter moving to any point of one of its lines, and capture for moving on to or across the enemy’s lines. It then worked through every position of the game. On the board as printed, 1,956 of the 2,828 positions are draws, and A cannot force a win at all. B escapes to the left-hand column through 1, 5, 48 and 57, which only the lines through 1, 5 and 57 cross; for instance, he can answer A’s first move 33 with 5 instead of 8. With the line 48–49 drawn in, as dashed above, there are no draws. A wins from either start, capturing on his twelfth move when he moves first and on his fourteenth when he moves second, with best play on both sides, exactly as Dudeney says. His two games and the illustrative game are sound on both boards. The line was almost certainly meant to be there.
Answer A, on his twelfth move if first, his fourteenth if second, with 48 joined to 49
A War Puzzle Game
The British general can always catch the enemy, but only after a visit to town 1, going in by 3 and leaving by 2, or the other way round.
The reason is a matter of colouring, which Dudeney compares to the opposition in chess. Take town 1 away, and the towns can be coloured in two colours so that every road joins towns of different colours. B and E then have the same colour. After the general’s move the two are on different colours, and after the enemy’s reply on the same colour again, so the general, who can only capture by moving into a neighbouring town, never gets the chance. The triangle of roads between 1, 2 and 3 is the only place where a road joins two towns of the same colour, and passing round it changes the general’s colour and the whole situation. The three shaded towns never matter: the general need not enter them, and the enemy cannot be forced into them and would be foolish to go.
Dudeney’s play is to visit 24, 20, 19, 15, 11, 7, 3, 1 and 2, whatever the enemy does, and then to go for him, driving him away from the north-west corner. The general then needs at most eight more moves, seventeen in all. In this example the enemy holds out as long as he can, the general’s moves above and the enemy’s below:
| 24 | 20 | 19 | 15 | 11 | 7 | 3 | 1 | 2 | 6 | 10 | 14 | 18 | 19 | 20 | 24 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 13 | 9 | 13 | 17 | 21 | 20 | 24 | 23 | 19 | 15 | 19 | 23 | 24 | 25 | 27 |
The enemy must now go to 25 or B, and is caught in either.
A program read the map from Dudeney’s answer and worked backwards through every pair of positions. It confirms each point. The general can force the capture in seventeen moves and no fewer. Without town 1 the map does colour in two colours and the enemy escapes for ever. The example game is legal and ends as he says. As for the nine opening moves, the program followed every possible reply by the enemy, letting the general take him at once if he ever stood next to him. From every town the enemy can then be in, the general needs at most eight more moves. Dudeney lists those towns as 5, 8, 11, 13, 14, 16, 19, 21, 24 and 27, besides 3 and 6 where the enemy is caught at once. The enemy can also be at 22, or in the shaded town beside 4, but from these too eight moves are enough.
Answer Visit town 1 first; seventeen moves at most
A Match Mystery
If you form the heaps, and so draw second, any of these thirteen groupings wins with correct play: 15, 14, 1; 15, 13, 2; 15, 12, 3; 15, 11, 4; 15, 10, 5; 15, 9, 6; 15, 8, 7; 14, 13, 3; 14, 11, 5; 14, 9, 7; 13, 11, 6; 13, 10, 7; 12, 11, 7.
Dudeney’s general method is to write each heap as a sum of different powers of two and leave the heaps so that every power appears an even number of times. For 12, 11, 7:
| 12 | 8 | 4 | – | – |
| 11 | 8 | – | 2 | 1 |
| 7 | – | 4 | 2 | 1 |
| 2 | 2 | 2 | 2 |
If the opponent takes 7 from the 12, leaving 5, 11, 7, the powers are no longer even, but taking 9 from the 11 restores them: 5, 2, 7. Why it works takes two lines. A move changes one heap only, and changes at least one of its powers, so from an even position every move leaves some power odd. From a position with some power odd, find the largest such power; a heap that contains it can be cut so as to flip exactly the odd powers, because removing that largest power more than pays for adding any smaller ones, and the position is even again. So the player who always leaves an even position keeps control: his opponent can never leave him one. Since here the last match loses, one change is needed at the very end, described below. The same holds for any number of heaps and matches. Dudeney credits the game to W. M. F. Mellor, on a correspondent’s word.
A program that works through every position of three heaps confirms that exactly these thirteen groupings of thirty into unequal heaps are wins, and that every position Mr Stubbs leaves in the story is a win for him. It also tested the rule of even powers against every position with no heap larger than fifteen. The rule is right everywhere except at the very end of the game, when no heap holds more than one match. There the powers do not decide it: the player who leaves an odd number of single matches wins, so 1 or 1, 1, 1 is a good thing to leave and 1, 1 a bad one, whatever the powers say. That is the exception of 1 and 1 that Mr Stubbs mentions.
Answer The thirteen groupings above
The Montenegrin Dice Game
5 and 9 against 13 and 15. Three dice fall in 216 ways; they total 5 in 6 ways and 9 in 25, 31 in all, and 13 in 21 ways and 15 in 10, again 31. Each player then succeeds on a throw with the same chance, and the game is fair. A program that lists every throw confirms the counts and finds that no other two pairs of odd numbers above 3 have equal chances.
Answer 5 and 9 against 13 and 15
The Cigar Puzzle
The first player wins. He stands his first cigar on end at the exact centre of the table, and then answers every cigar with its copy turned half round about the centre: A with AA, B with BB, and so on.
As long as the second player can find a place, the first player can too, so the first player places the last cigar. Dudeney insists that this is a matter of theory, the players being assumed to play perfectly, and that the first cigar must stand on end: a cigar lying across the centre is not carried on to itself by the half turn, because its flat and pointed ends change places, so the copying breaks down.
One step needs saying that Dudeney leaves out: why the copy never touches the cigar it copies. Suppose it did. A point where they met, and the point opposite it across the centre, would both lie in the second player’s cigar. A cigar is a convex solid, so the point halfway between them would lie in it too. That point is on the upright through the centre of the table, at the same height, so inside the cigar standing on end: the second player’s cigar would have touched it, which is not allowed. The copy cannot touch any other cigar either, since if it touched one, the second player’s cigar would touch that one’s opposite number.
Answer The first player