Here is the one crucial thing we need to notice and understand, that if the starting position is divisible by 3 then the position is a losing position for the starter, in all other cases the starter can win. Here is how it happens. All the powers of two have remainders 1 and 2 when divided on 3 obviously. The optimal strategy would be the following : "At every step leave your opponent in a divisible by 3 position". The smallest non negative number divisible by 3 is 0 and if the starter get's to 0 that would only mean that the second player picked the last stones left. The steps are as follow. If you are in a divisible by 3 position after, you make a move for sure your opponent will not be in a position divisible by 3 (it will have a remainder of 1 or 2 when divided on 3) and after that he can take some number of stones which will leave you in a divisible by 3 position again, this process will continue until he picks the last 1 or last 2 stones. When we begin on a non divisble by 3 position we just need to make the move of our opponent and leave him in a divisible by 3 position which will get him a defeat.
No comments:
Post a Comment