# Detailed proof for "(n % 4)" principle

• Hello my friends. I come up with a rigorous proof that "return (n % 4)" works. Here is my detailed explanation and I apologize if this is wordy or more complex than your own method.

Statement1
we have a function Win(n) that takes in an input "n", and outputs: 0 or 1.
For its output 1, it means "you can win in one of the three moves: take 1, 2, 3"
For its output 0, it means "you cannot win, no matter what moves you take" (in the assumption that your opponent is smart).

Statement2
Now I claim that the function Win(n) is:

• 1 when n % 4 != 0

• 0 when n % 4 == 0

In other words, n = 4k + 4, then Win(n) = 0; n = 4k+1, 4k+2, 4k+3, Win(n) = 1;

Now I prove this by Induction:

1. when k = 0.
• n = 1, 2, 3, on every of these three case you can win by taking all of them.

• n = 4, you simply cannot win in any way.

1. Assume this is true for k = x:
n = 4x+1, 4x+2, 4x+3, Win(n) = 1; n = 4x + 4, then Win(n) = 0;
Then I will prove the following:
for k = x + 1, this is also true:
n = 4x+5, 4x+6, 4x+6, Win(n) = 1; n = 4x + 8, then Win(n) = 0;
• For n = 4x+5, you can take 1 to leave your opponent n=4x+4, which is 0 in the assumption. Similarly, for n=4x+6, 4x+7, you should take 2, 3 stones from it.
• For n = 4x+8, any number of stone (1, 2, 3) you take, will leave your opponent the previous three cases, which in turn leaves you a 4x+4 case, and you lose.

In conclusion, the Win(n) function is:

• Win(n) = 0; n = 4k + 4 (k is int)

• Win(n) = 1; n = 4k+1, 4k+2, 4k+3 (k is int)

And that is why return n % 4 works.

• Thanks a lot for your explanation.

• That is rigorous

• Thanks for the detailed proof by induction.

• @lclc Thanks!

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