Proof by induction of a 2 player dot removal game

Question

Consider a 2 player game where there are two rows of dots with row 1 having $n_1$ dots and row 2 having $n_2$ dots. The players can remove any number of dots from their row during their turn but the number they remove must be greater than 0 and the current player can only remove the dots from one row. The player who is forced to remove the last dot loses.

If $n_1 = n_2$ and both are greater than $0$, prove by strong induction that it is possible for the second player to win. What happens if $n_1$ and $n_2$ are not equal?

Starting with the proof, for the base case I assume that $n=2$. In this case, the game could proceed as such: For a player 2 winning strategy, player 1 removes 1 dot, player 2 removes two dots, and player 1 removes 1 dot, so he loses.

The inductive hypothesis I came up with is that $\forall i \leq k$,if $n_1=n_2=i$, then player 2 wins. Since this is strong induction, this assumes for up to $k$ dots.

However, the inductive step is where I'm lost. I want to prove for $k+1$ dots. How would I go about doing this? Can you explain your thought process through each part of solving the inductive step?

Answer 1

As stated the claim is false because the first player wins $n_1=n_2=1$ by taking either dot and forcing the second player to take the last. You need $n_1=n_2 \ge 2$ for a second player win. Your base case is only half done. You have shown one choice for the first player leads to a second player win, but need to show that the other one does, too. It works the same way.

Strong induction says you assume the truth of a statement for all values up to $k$, then prove it is true for $k+1$. If you have $n_1=n_2=k+1$ the first player can take $k+1, k,$ or less than $k$ dots. If he takes $k+1,$ the second player takes $k$ and wins. If he takes $k,$ the second player takes $k+1$ and wins. If he takes less than $k$ there will be at least $2$ dots left in the row he took from. The second player then takes the same number from the other row, leaving two equal rows of at least two dots, which we have assumed is a second player win, so $n_1=n_2=k+1$ is a second player win.

Answer 2

If $n_1=n_2=1$, it's clear that player 2 can't win. So adjusting the question for $n_1=n_2\ge2$, and you've already dealt with the base case, the induction hypothesis should be

"Suppose $P(i)$ is true for $2\le i\le k$" where $P(i)$ is the statement "If $n_1=n_2=i$, then player 2 CAN win" (meaning it's possible for player 2 to win, NOT always wins).

Let $n_1=n_2=k+1$. Player 1 has to pick a row and some dots $1\le n\le k+1$.

CASE 1: If player 1 picks, say from row 1, some dots $1\le n\le k-1$, then row 1 has at least $k+1-(k-1)=2$ dots left and at most $k+1-(1)=k$ dots left. Then player 2 can pick, from the other row, the same number $n$ dots so $2\le n_1=n_2\le k$. By induction hypothesis, player 2 can win so $P(k+1)$.

CASE 2: Now suppose player 1 picks $n=k$ dots, then the above method doesn't work since then $n_1=n_2=1$. Row 1 has $k-1-(k)=1$ dot left so we have player 2 pick, from the other row, all the dots so player 1 is then forced to pick the last dot so $P(k+1)$.

CASE 3: If player 1 picks $n=k+1$, i.e. all the dots, then player 2 picks, from the other row, $k$ dots so the only row left with dots has a single dot left, so player 1 is then forced to pick the last dot so $P(k+1)$.

By strong induction, for $n\ge2$, $P(n)$ is true.

By the way, I interpreted the question as player 2 can win for ANY/EVERY move player 1 can make, thus all these cases. If you interpret the question as player 2 can win for SOME move player 1 can make, then we don't need induction. In fact, we never really needed induction. Let $n_1\ge 2$, $n_2\ge1$ (or the other way around, it doesn't matter), player 1 takes $n_1-1$ from row 1, player 2 takes all from row 2, player 1 takes the last dot from row 1, we're done. Then $n_1=n_2\ge2$ is a special case.