Game of Taking Stones

89 Views Asked by At

Alice and Bob play the following game. Initially, there is a stone on each lattice point such that x,y $\in$ {1,...,10}. Alice moves first, and then they take turns. On each player's turn, they choose a point (x,y) that still has a stone on it and removes that stone, and all stones down and to the left of that stone. That is, they remove a stone from each ($x_0$, $y_0$) such that $x_0$ $\leq$ x and $y_0$ $\leq$ y (that still has a stone). The player who takes the last stone loses. Who has a winning strategy to this game? Explain how a player can force a win.

I am pretty sure that Alice has the winning strategy to this game, with the idea being to leave Bob with one stone at the end of the game to force a win for Alice, so Bob has no choice but to take the last stone. However, I am having difficulty with a proof for this. Any help would be appreciated.