The Putnam Mathematical Competition’s Unsolved Problem

inside-bigdata.com

2 points·alexyes··3 comments

I think it starts like this:

1) at most nb of stone increase by one each time one player plays

2) nb of stone cannot decrease unless the board is full of stones

3) no one can lose unless the board has been full of stone at least once; this is because until the board has been full of stones it is possible to increase the nb of stone by adding one and this is a new position because of 2)

4) as soon as there are n - 1 stones, the player who puts the last stone wins; because there are n - 1 different positions left with n - 1 stones and n - 1 is even

Now a good strategy for Alice is to first play in the middle, and after that use the following rules:

- if Bob removes one stone and the result is that it adds a stone both on the left and right side of the board, then Alice replays the stone that Bob just removed,

- otherwise whatever Bob plays, Alice plays the same thing on the other side of the board (symmetrically regarding the middle of the board)

This ensures that:

5) the situation is always symmetrical after Alice played

6) when Bob plays once and then Alice plays once, if the nb of stone on the board increased since before Bob just played, then it increased by an even amount

As after Alice first played in the middle, there was just 1 stone, then because of 6):

7) when it's Bob turn to play, the number of stones on the board is always odd

Alice wins because of 7) and 4)!

Reply on news.ycombinator.com