The original question goes like this: There are 99 stones, A and B are playing a game that, each one take some stones in turn, and each turn one can only take 1, 2, 4, or 6 stones, the one take the last stone wins. If A is the first one to take stones, how many stones shall A take in the first turn?
This seems a quite complex tree searching quiz, listing out all the branches, then work it bottom up: the leaf with A taking the last stone is marked as "win"; for the intermediate node that whatever strategies B might take, if A always has a way to reach a node marked as "win", this node is also marked as "win".
But this approach is quite time consuming. Is there any smart algorithm to check out if A has a "guaranteed to win" strategy?
O(n) solution
If we start with 1, 2, 4 or 6 stones, A
will always win, because he'll just take them all in the first move.
If we start with 3, A
will lose no matter what he does, because regardless of whether he takes 1 or 2, B
will take 2 or 1 next and win.
If we start with 5, A
will win by taking 2 first, thus sending B
to the case above, where he starts with 3 stones.
If we start with 7, A
will win by taking 4
, sending B
to the same case with 3
.
If we start with 8, A
will lose no matter what he does: whatever he takes, he will send B
to a winning position.
If we start with 9, A
can take 1 and send B
to the situation with 8, causing him to lose.
If we start with 10, A
can take 2 and send B
to the situation with 8 again, causing him to lose.
By now, it should become quite obvious how you can incrementally build an O(n)
solution: let win[i] = true if i stones are winnable for the first person to move
We have:
win[1] = win[2] = win[4] = win[5] = win[6] = true, win[3] = false
win[x > 6] = not (win[x - 6] and win[x - 4] and win[x - 2] and win[x - 1])
For example:
win[7] = not (win[1] and win[3] and win[5] and win[6])
= not (true and false and true and true)
= not false
= true
Compute this up until the number you're interested in and that's it. No trees involved.
O(1) solution
By looking carefully at the above solution, we can derive a simple constant time solution: note that A
can only lose if he sends B
to a winning position no matter what he does, so if k - 6, k - 4, k - 2, k - 1
are all winning positions.
If you compute win
for a few values, the pattern becomes obvious:
win[k] = false if k = 3, 8, 11, 16, 19, 24, 27, 32...
=> win[k] = false iff k mod 8 == 3 or k mod 8 == 0
For 99, 99 mod 8 = 3
, so A
does not have a sure winning strategy.
OK, so we can see that:
Every turn, number of stones can be taken is less than 7, so the result should be related to modulus 7.
So, for n < 1000, I have printed out the sequence of number of stones that makes the first person win, modulus 7, and it is a truly repeated cycle.
1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5 0 1 3 4 5 6 1 2 4 5 6 0 2 3 5 6 0 1 3 4 6 0 1 2 4 5 0 1 2 3 5 6 1 2 3 4 6 0 2 3 4 5
This cycle has the length is 56, so the problem can be solved in O(1) by finding the result of first 56 numbers.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With