1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving by Induction/Recursion

  1. Apr 10, 2016 #1
    1. The problem statement, all variables and given/known data
    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.

    2. Relevant equations
    Induction/Strong induction

    3. 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.
     
  2. jcsd
  3. Apr 10, 2016 #2

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    What are you not sure about?
     
  4. Apr 10, 2016 #3
    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!
     
  5. Apr 10, 2016 #4

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  6. Apr 10, 2016 #5
    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!
     
  7. Apr 10, 2016 #6

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You just have to ask yourself how you would play the game if you were playing second.
     
  8. Apr 10, 2016 #7
    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).
     
  9. Apr 10, 2016 #8

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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).
     
  10. Apr 10, 2016 #9
    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!
     
  11. Apr 10, 2016 #10

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    If I understood your question I would try to answer it.
     
  12. Apr 10, 2016 #11
    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?
     
  13. Apr 10, 2016 #12

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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
     
  14. Apr 10, 2016 #13
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proving by Induction/Recursion
  1. Proving by induction (Replies: 5)

Loading...