Theorem: all 4s shall be false


  • 152
    L

    Theorem: The first one who got the number that is multiple of 4 (i.e. n % 4 == 0) will lost, otherwise he/she will win.

    Proof:

    1. the base case: when n = 4, as suggested by the hint from the problem, no matter which number that that first player, the second player would always be able to pick the remaining number.

    2. For 1* 4 < n < 2 * 4, (n = 5, 6, 7), the first player can reduce the initial number into 4 accordingly, which will leave the death number 4 to the second player. i.e. The numbers 5, 6, 7 are winning numbers for any player who got it first.

    3. Now to the beginning of the next cycle, n = 8, no matter which number that the first player picks, it would always leave the winning numbers (5, 6, 7) to the second player. Therefore, 8 % 4 == 0, again is a death number.

    4. Following the second case, for numbers between (2*4 = 8) and (3*4=12), which are 9, 10, 11, are winning numbers for the first player again, because the first player can always reduce the number into the death number 8.

    Following the above theorem and proof, the solution could not be simpler:

    public boolean canWinNim(int n) {    
        return n % 4 != 0 ;
    }

  • 0
    J

    I have a question about n = 8. I believe that even if n = 8, it's possible for the user to win.

    I know I must be missing something, but can't figure out the flaw in my logic. I'd appreciate any help:

    with n = 8, here's what I'm thinking:

    I will take 2. n = 6

    Opponent takes 1. n = 5

    I take 1. n = 4

    Opponent takes 1, 2, or 3... leaving me as the winner.

    Am I doing something wrong?


  • 10
    J

    when you take 2, n = 6;
    and your opponent will definitely take 2, because he or she is also very clever and have optimal strategies as it has been mentioned in the problem.
    so now n = 4 and it's your turn...sorry for that ; )


  • 0
    J

    Thanks for the response. Makes perfect sense. I definitely didn't pay enough attention to the problem.


  • 6

    I don't think "mod (of) 4" is a proper label for the losing numbers. If anything, they're not mod 4, as they are nothing (zero) mod 4. Also, "multiple of 4" is an obvious clear label for them.

    What about 0 (which I'd btw say is the real base case), 1, 2 and 3?

    If you backslash-escape the asterisks, then it won't look like "(24 = 8) and (34=12)".


  • 1
    W

    it could be simpler.

    public bool canWinNim(int n){
        return n%4;
    }
    

    lol, jk, your explanation and code are perfect.


  • 0
    L

    Thanks for the advices.

    I think the '1, 2, 3', are sort of special cases that happen to fail into the formula.

    The numbers (1, 2, 3) are not big enough to complete a full round,
    unlike the other numbers which allow each player to play at least once.


  • 25
    J

    If you are familiar with math induction, this problem can be proved by natural induction.

    Base case: n = 4, we can show that for taking 1, 2, or 3, you will always lose.

    Induction case: suppose for n = 4K, you will lose. For 4 (K + 1), you have 4K + 4, which is 4 more than 4K. For all the possible choice (1, 2, 3), your enemy can take 3, 2, 1 so you must take 4K, which is losing.

    Thus, for all 4K (K is natural number) cases, you will lose.


  • 0
    W

    How did you think of this solution? This isn't something I would have thought of..


  • 0
    L

    I don't think it's enough. You also need to prove you will win in the other case.


  • 0
    C

    The other case it is possible to win, not that you will win. The problem is "can"win Nim.
    So to clarify, I'd say that if you show that you will never win in the case where n % 4 == 0, then you show that you will "not never" win in the other cases.


  • 0
    H

    Line 5: error: incompatible types: int cannot be converted to boolean


  • 0
    W

    thanks for pointing out!


  • 9
    X

    Or we can do bit manipulation, which might be faster than % operator

    public boolean canWinNim(int n) {
        return (n & 3) != 0;
    }
    

  • 0

    Brilliant explanation.


  • 0
    N

    This problem is so xXXx.


  • 0
    N

    return n % 4 ;


  • 0
    K

    @jkang410 You win if the opponent is not clever. Opponent takes 2, you lose.


  • 0
    M

    @jkang410 Because of the optimal strategies for the game,the opponent will choose 2.Because when you are 4,you have lost the game.


  • 0
    T
    return n & 3;
    

Log in to reply
 

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