# Putnam game theory question

There are $n\ge1$ boxes in a line where $n$ is an odd integer. Two players, Connor and Andrew, are playing a game. On a turn, you can place a stone in a box OR take a stone out of a box and place a stone in the nearest empty box to the left AND the right if they exist. A move is permitted if resulting player position has not occured previously in the game. A player loses if they can't move.

What moves can Connor make on his $1^{st}$ turn to play most optimally. Anyone able to solve this? Note: $1$ stone per box.

• A preliminary observation: If a player is the first one to place a stone that results in an arrangement of n-1 stones, that player loses. To prove this, see that: 1) From an arrangement consisting of n-1 stones, you can move to any other arrangement consisting of n-1 stones or the arrangement with all n stones filled, but no others. 2) From the arrangement with all n stones filled, you can move to any arrangement with n-1 stones, but no others. 3) There are an even number of arrangements with either n-1 or n stones, so the first player to start their turn on such an arrangement wins. – Alex Zorn Oct 1 '14 at 20:41
• Can you clarify the rules? What do you mean by "Do X OR Y and W and Z if one exists"? – Steve Kass Oct 2 '14 at 17:26
• @SteveKass Sure. A player has two options. He may 1) Put a stone in an empty box. 2) Remove a stone from a box and then put a stone in the left AND right nearest boxes. A player loses if he/she is unable to make any moves. – lynom Oct 2 '14 at 20:21
• @AlexZorn: Here's another observation. If there $k<n$ stones on the board, the next move will leave $k$ or $k+1$ stones on the board. In other words, the number of stones in play cannot go down if there is at least one empty box. If both end boxes are empty before a move, the move must add a stone to the number of stones in play. Connor can (for a while) safely force Andrew to increase the number of boxes on each of Andrew's moves by keeping the end boxes empty, so that no more than two positions for a given number of stones in play are ever reached, avoiding the worry of illegal moves. – Steve Kass Oct 3 '14 at 4:13
• To prove this: Making a play which keeps the number of stones constant will always strictly decrease the length of the leftmost block while keeping the rightmost block the same length, or the opposite. – Alex Zorn Oct 5 '14 at 3:29