Learn / Library / Brainteasers

Bottles in a row

BrainteasersHard

$15$ bottles stand in a row at positions $1$ to $15$ . $2$ players alternate; a move knocks down either $1$ standing bottle or $2$ standing bottles at neighbouring positions. Bottles never move, so a fallen bottle leaves a gap that splits the row. The player who knocks down the last bottle wins. You move first and both players play optimally. A first move is the set of bottles it knocks down. How many different first moves guarantee you a win?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

A mirror reply works after a central move, but other first moves may win too: give each segment of the row a value and combine the values.

Solution

Knocking down the bottle at position $8$ leaves $2$ rows of $7$ , and copying every opponent move on the other side then wins, so a winning move exists.
To count all winning moves, give each row of $n$ bottles a value $g (n)$ : the smallest non-negative whole number not among the XORs of the values of the pieces its moves leave.
This gives $g (0)$ to $g (14)$ as $0$ , $1$ , $2$ , $3$ , $1$ , $4$ , $3$ , $2$ , $1$ , $4$ , $2$ , $6$ , $4$ , $1$ , $2$ , and a first move wins exactly when the XOR of the values of the rows it leaves is $0$ .
No move that removes $2$ bottles works, but removing $1$ bottle wins when it leaves rows of $1$ and $13$ , $5$ and $9$ , or $7$ and $7$ , in either order.
These are the bottles at positions $2$ , $6$ , $8$ , $10$ and $14$ , so the answer is $5$ .

Answer: $5$

Next question Back to the library