c4countdown

|
| |
| | |
| | | |
| | | | |

This is a game for two players (my maths teacher showed us this during wet break)

Draw 5 lines of sticks like above (1,2,3,4,5).
Players take it in turns to move. Each move consists of striking through at least one stick. You can strike through as many sticks as you like, but they must be on a single row and continuous (i.e. no stick already crossed in the middle of them). The loser is the person who crosses out the last stick.

Can you work out a strategy for the game? Can either player guarantee success?

There's a technique for analysing games like this where you assign each position a score for if you reach it at the end of your turn. If there's just 1 stick left then your opponent takes that and loses, so we'll assign that (and all other winning positions) a score of 0.

Then you gradually work outwards, assigning each position the lowest score that your opponent can't reach from that position. So 2 sticks in a row gets a score of 1, as your opponent could take 1 stick and get a score of 0. 3 sticks in a row gets a score of 2, as your opponent could take 1 stick and get 1 or 2 sticks and get 0. 2 lines of 1 stick each gets a score of 1, similarly. The first interesting one is 3 lines of 1 stick, which also gets a score of 0 as you can't reach another position with a score of 0 in a single move.

The aim is therefore to move to a 0-score position. From there your opponent will move to a non-zero score, you move back to 0, etc. If I have time later I may work out the relevant scores for this game.

It's not raining.

Gavin Chipper wrote:It's not raining.

That's the game.

Jon Corby wrote:

Gavin Chipper wrote:It's not raining.

That's the game.

So are you saying that I win?

Gavin Chipper wrote:

Jon Corby wrote:

Gavin Chipper wrote:It's not raining.

That's the game.

So are you saying that I win?

No. The winner is the one who doesn't cross out the last stick, the pretence that its raining is unconnected to the result.

I think the following is a list of winning positions (ones where your next move can get you back to a winning position no matter what your opponent does). If you strike one or more sticks from the middle of a line you effectively split it into 2 lines, hence some positions involving more than 5.

As 4, 4, 3, 2, 1 is a winning position, the correct first move is to take 1 stick from the 5 line.

1
2,2
3,3
4,4
1,1,1
3,2,1
5,4,1
2,2,1,1
2,2,2,2
3,3,1,1
3,3,2,2
3,3,3,3
4,4,1,1
4,4,2,2
1,1,1,1,1
3,2,1,1,1
3,2,2,2,1
4,4,3,2,1
2,2,1,1,1,1
2,2,2,2,1,1
2,2,2,2,2,2
3,3,1,1,1,1
3,3,2,2,1,1
4,4,1,1,1,1
1,1,1,1,1,1,1
3,2,1,1,1,1,1
3,2,2,2,1,1,1
2,2,1,1,1,1,1,1
2,2,2,2,1,1,1,1
1,1,1,1,1,1,1,1,1

Very nice. There's some missing, but the conclusion that the player who goes first wins is correct. (You can also take the lone 1 instead of 1 from the 5, so 5,4,3,2 should be on your list, for example).

I had it down to a few winning positions that are obvious (2,2) & (3,2,1) for example, plus an even number of ones, but never actually followed it all the way to the end to see whether you should be player 1 or 2. Until last night.

Yeah, I stopped once I found a winning move, so probably a few missing, in particular ones that don't touch the 5 immediately.

Would you like to play a game?

Jon Corby wrote:Would you like to play a game?

Not really. And it's not raining here either.