As a data scientist with my roots in the theoretical foundations of the field, I’m always looking for ways to challenge myself and pick up a new mathematical apparatus that could help me in my project work. While reading a past copy of The Tech, MIT’s oldest and largest newspaper, I learned that MIT took first place in the most recent chapter of the William Lowell Putnam Mathematical Competition, the oldest and most prestigious competition of its kind. Over 4,000 students took the Putnam test, but NOT one managed to solve the last question, Problem B6!

I provide you with the dreaded Problem B6 below. Surely if you can solve this, then you’d be in great shape to come up with a new machine learning algorithm that can win the next Kaggle competition for some serious prize money. Good luck!

*Sign up for the free insideBIGDATA newsletter.*

Go in the middle! Assume the base case is a board with one square. Going in the middle is the only available move and Alice wins. Now assume we know the solution for all k < n. Is Alice goes in the middle she then breaks the board into two equally sized boards of (1/2)(2k+1 – 1) = k squares. Since k is less than n we already know the solution. Alice will play on one "half" only, until it is solved and then play on the other board until it is solved. If Bob picks up the center square, Alice can replay it, thus creating two board of size k-1. While Alice is playing optimally on one board bob can be playing optimally on the other board. Since Alice goes first, Bob will solve one half exactly one move before Alice solves the second board, and thus Alice will be able to take the last legal move, insuring the win.

I think it suffice to say that 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 it on the other side of the board. This makes sure that the situation is always symmetrical.

My solution would go 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), when it’s Bob turn to play, there are an odd number of stones on the board.

Because of 4) this means that Alice wins!