- #1

mr.tea

- 102

- 12

## Homework Statement

I have a question that I need to prove(probably by induction): In a game, two players take turns removing

**any**

**positive**number of matches from one of two heaps. The player who removes the last match wins. Prove that if the players start out with heaps of equal size, then the second player has a winning strategy.

But I don't know if I am correct or not, and if I can use induction the way I use it here.

## Homework Equations

Induction/Strong induction

## The Attempt at a Solution

I thought to use here strong induction. It's easy to see for the base case(1) why it's true. For any other case(assume n), if the first player removes some matches(I assume he doesn't remove all the matches from one heap, that's an obvious loss for him, I guess the player is not an idiot), then the second player can remove equal matches from the other heap, and they are going back to case n-k which I assumed is true.

Well, another way is just to say that the second player can reduce the problem to 1 match on each heap which is an obvious win to the second player.

I am not sure about my use of the induction here.

Thank you.