# Math Help - Sticks!

1. ## Sticks!

This one’s fun and a challenge for a bright mind:

15 sticks are arranged as so.
2 Player’s take turns in crossing through any number (at least 1) of adjacent sticks (so long as they haven’t been crossed through before).
The person left with the last stick looses.

A typical game may play out in the following manner:

The question:
- Is there a strategy?

2. I would say that the player going second has a better chance of winning. For example if there are only 6 sticks, like this

$\begin{tabular}{ccccc}
{} & {} & A & {} & {}\\
{} & B & {} & C & {}\\
D & {} & E & {} & F\end{tabular}$

the second player always wins:

$\begin{tabular}{c|c}
If Player 1 crosses & Player 2 crosses\\
\hline
A & D or F\\
B or C & D+E or E+F\\
E or D+E+F & B+C
\end{tabular}$

And vice versa (e.g. if Player 1 crosses D+E, Player 2 crosses B or C). The trick is to force your opponent into (i) an odd number of non-adjacent single sticks, or (ii) two non-adjacent rows of two adjacent sticks.

The game looks more complicated with two more rows added but I think the basic idea is the same. Note that (ii) can be generalized to: an even number of non-adjacent sets of n adjacent sticks.

PS: If there are 10 sticks (four rows), the first player will always wins – he just needs to cancel the whole of the last row and force the second player to make the first move in the 6-stick situation. So I think it’s because there are an odd number of rows that the second player is favoured.

3. I’ve just been thinking about this problem again – and I’ve realized that I was wrong! For the 15-stick game, the first player can always win. Indeed, the first player will win if by crossing out the either the extreme-left or the extreme-right stick on the bottom row.

The trick is for the first player to “lose” the bottom of half of the game, so as to force the second player to make the first move in the top half of the game (the one involving 6 sticks). By crossing out either the extreme-left or the extreme-right stick on the bottom row, the first player leaves the two rows each with 4 sticks. I claim that the first player can then go on and be the last player to cancel out all these 8 sticks.

Proof: There are 5 possibilities for the second player. The first player simply copies the actions of the second player.

(i) The second player cancels all 4 sticks in one row.
The first player then simply cancels all the sticks in the other row.

(ii) The second player cancels 3 adjacent sticks in one row.
Then the first player cancels 3 adjacent sticks in the other row.

(iii) The second player cancels two middle adjacent sticks in one row.
The first player can do the same in the other row – or cancel all the sticks in the other row.

(iv) The second player cancels two non-middle adjacent sticks in one row.
When the first player does the same in the other row, he leaves two rows of 2 sticks. The second player can cancel 1 or 2 sticks next. The first player then cancels 1 or 2 sticks respectively.

(v) The second player cancels a single stick anywhere.
If that stick is an end stick, the first player cancels one of the two middle sticks in the other row – and vice versa. This should leave 3 adjacent sticks in one row, and 2 adjacent sticks and 1 single stick in the other row. Notice that this is an identical scenario to the 6-stick game, with the second player being forced to make the next move. Only this time, the first player controls the game in such a way that he “loses” instead of winning!

Indeed, the game has essentially been divided into two sub-games: a 6-stick top-half sub-game, and a 9-stick bottom-half sub-game. Note that you don’t have to finish one sub-game before starting the other – the moves for the two sub-games can be “interlaced”.