Proving by Induction/Recursion

[mr.tea]

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.

 

[PeroK]

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.

What are you not sure about?

 

[mr.tea]

What are you not sure about?

Thank you for the fast comment.

First, it looks way to easy.
Second, I always ask myself, how do we know that the case n-k ends with a win of the second player. I have done some cases, and look at all the combinations. Maybe all the cases before n-k ends like that but that case isn't.

I have just seen some "proof" that all the horses are at the same color. The problem was in the implication from case n=1 to case n=2, but all the other cases(from 2 to 3 and so on) were ok. How do I know that I don't have such a problem?

Thank you again!

 

[PeroK]

Thank you for the fast comment.

First, it looks way to easy.
Second, I always ask myself, how do we know that the case n-k ends with a win of the second player. I have done some cases, and look at all the combinations. Maybe all the cases before n-k ends like that but that case isn't.

I have just seen some "proof" that all the horses are at the same color. The problem was in the implication from case n=1 to case n=2, but all the other cases(from 2 to 3 and so on) were ok. How do I know that I don't have such a problem?

Thank you again!

Either there's a flaw in the proof or there isn't. With your logic you could never prove anything, because you'd say: I think my proof is correct, but I remember once I got fooled by one of those paradoxical proofs, so maybe I've made a mistake somewhere.

 

[mr.tea]

Either there's a flaw in the proof or there isn't. With your logic you could never prove anything, because you'd say: I think my proof is correct, but I remember once I got fooled by one of those paradoxical proofs, so maybe I've made a mistake somewhere.

Thank you again.

I think it might be just the induction idea. Maybe I need to get use to the power of induction.

But as I understand from you, my proof(or sketch of the proof) is correct (right?).

Thank you!

 

[PeroK]

Thank you again.

I think it might be just the induction idea. Maybe I need to get use to the power of induction.

But as I understand from you, my proof(or sketch of the proof) is correct (right?).

Thank you!

You just have to ask yourself how you would play the game if you were playing second.

 

[mr.tea]

You just have to ask yourself how you would play the game if you were playing second.

I would probably do the same as I wrote(trying to bring the game to a situation I already know I can win independently of the other player's moves).

 

[PeroK]

I would probably do the same as I wrote(trying to bring the game to a situation I already know I can win independently of the other player's moves).

You have at least three proofs:

The strong induction proof

If there are games where the second player does not have a winning strategy, there must be a least example.

Simply specify the strategy and note that eventually you must hit 0-0 and win (you can't take positive numbers from a finite pile indefinitely).

 

[mr.tea]

You have at least three proofs:

The strong induction proof

If there are games where the second player does not have a winning strategy, there must be a least example.

Simply specify the strategy and note that eventually you must hit 0-0 and win (you can't take positive numbers from a finite pile indefinitely).

I think that since we are talking about induction, probably the strong induction proof is appropriate here. But you are right, there are few other strategies which can prove the statement without induction.
Regarding the example, what would you do if you don't know if the statement is true\false and the number of combinations for "games" is high?

Thank you!

 

[PeroK]

I think that since we are talking about induction, probably the strong induction proof is appropriate here. But you are right, there are few other strategies which can prove the statement without induction.
Regarding the example, what would you do if you don't know if the statement is true\false and the number of combinations for "games" is high?

Thank you!

If I understood your question I would try to answer it.

 

[mr.tea]

If I understood your question I would try to answer it.

Sorry for my English.

If you have a similar game, but this time you don't know if the statement is true of false. And for each case(case n=1,2,...) the number of possibilities increases, let's say by powers of 3. How many cases would you check before you would try to decide if the statement is true or false?

 

[PeroK]

Sorry for my English.

If you have a similar game, but this time you don't know if the statement is true of false. And for each case(case n=1,2,...) the number of possibilities increases, let's say by powers of 3. How many cases would you check before you would try to decide if the statement is true or false?

This was a very simple game. In general, it may be very difficult to determine who has the winning strategy. Take a look at:

https://en.wikipedia.org/wiki/Nim

 

[mr.tea]

This was a very simple game. In general, it may be very difficult to determine who has the winning strategy. Take a look at:

https://en.wikipedia.org/wiki/Nim

So this game is Nim of two heaps. I didn't know that there are games with such mathematical theory about them. Absolutely beautiful! :) thank you.