Question 695384
There are two stacks of cards that each contain "r" cards. Two players play the following game. Each player in turn chooses one stack and then removes any number of cards, but at least one, from the chosen stack. The player who removes the last card wins the game. Prove that the second player (the player that does not go first) can always win. Don't prove by example cover all cases.
<pre>
Strategy:  The second player simply always causes the two 
stacks to have the same number of cards. 

Explanation:

The object is to force your opponent to take all the cards
in one of the stacks.  For then you can pick up last by
taking the other stack.  Let's assume the first player is
not stupid enough to lose early by taking all the cards in
one of the piles until forced to do so.

1. First player has no choice but to leave the two stacks with a DIFFERENT
number of cards.

2. Second player then takes the same number of cards the first player took
off of one pile, off the other pile, leaving the two stacks with the SAME 
number of cards.

3. Then the first player must again leave the two stacks with a DIFFERENT number of cards.

4. Second player then takes the same number of cards the first player took
off of one pile, off the other pile, leaving the two stacks with the SAME 
number of cards.

5. Then the first player must again leave the two stacks with a DIFFERENT number of cards.

etc. etc.


This continues until the second player leaves the two stacks with just 1
card in each pile.  Then the first player must take 1 card, and the second
player picks up last and wins.

Edwin</pre>