Math Proof for: 4k is a Sufficient and Necessary Condition for Not Win


  • 18
    T

    Sufficient Condition ("n = 4k => the first guy encounters n = 4k will fail")

    (1) Base case, true; (2) Assume n = 4k makes one who take the first step from n=4k fail. For n = 4(k+1), you have no strategy to make your opponent be the one take the first step from n'=4k, while he can, thus you will fail. Therefore, for any "n = 4k", you will fail.

    Necessary Condition ("fail => n = 4k")

    If the statement "fail => n = 4k" is true then the statement "n != 4k => win" is true. We can prove the later one: if n != 4k, thus n = 4k +1, or 4k + 2, or 4k + 3. For any of n = 4k +1, or 4k + 2, or 4k + 3, you can remove 1, or 2, or 3 stones to make your opponent be the guy who first encounter "n is a multiple of 4 (n = 4 k' )" situation in which the opponent is doom to fail, because we have proved "n = 4k => the first guy encounters n = 4k will fail". Therefore we've prove "n != 4k => win" is true, so "fail => n = 4k" is true.

    So now we can confirm the one line solution is correct:

        return n%4 == 0? false: true;
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.