Pile of Rocks

Solution. Undoubtedly, some of them have a winning strategy, for the Zermelo's theorem. The problem is to determine which of the two has it, and which It is that strategy. Part of the difficulty of this problem is the large number of initial stones, which makes impossible an exhaustive analysis of all the possible plays. The indicated thing then is to simplify the problem assuming an initial number of stones smaller. For example if there is only one stone, then A retires and wins. The same happens if initially there are 2, 3, 4, or 5 stones, since A can remove them all in a single move. Instead if there are 6 stones who has a winning strategy is B, since he plays what that plays A in the pile will be 1 to 5 stones, and B wins by removing them all. Note that in general the player who faces a lot with 6 stones lose. Therefore, if there are initially 7 stones, A wins by removing 1 and leaving 6 to B. In the same way if initially there are 8, 9, 10 or 11 stones A wins by retiring respectively 2, 3, 4 or 5 stones. In general the player to face a lot with 7, 8, 9, 10 or 11 stones wins. Thus if initially there are 12 stones A loses, because after playing it will leave your opponent 7, 8, 9, 10 or 11 stones. Here you can see a pattern: If the initial number of stones is a multiple of 6, there is a strategy winner for the second player, otherwise there is for the first. In both cases the winning strategy consists in removing a number of stones such that the number of those remain in the heap is a multiple of 6. To prove that this is really the case, let's note that if in the heap There are n stones and n is not a multiple of 6, so n = 6q + r with 1 ≤ r ≤ 5. By so whoever has the turn can remove stones and leave in the heap a multiple of 6. On the other hand if n is a multiple of 6 the player who has the turn must remove 1 to 5 stones, leaving a number in the pile which is not a multiple of 6. So if initially n is not a multiple of 6, A has a winning strategy that consists of always withdrawing the rest of 5 the division between 6 of the number of stones left in the pile. As always leave a multiple of 6, and the number of stones decreases in each play, will eventually reach 0 giving the victory to player A. Instead if initially n is not a multiple of 6, whatever the move of A a number of stones that is not a multiple of 6 will remain in the pile, that allows B to apply the winning strategy already described. Like in this problem n = 100 is not a multiple of 6, A is the one who has a strategy Winner If initially there are n stones in the pile and each player can remove from 1 to k stones, it is clear that if n is not a multiple of k + 1 the first player has a winning strategy, consisting in playing in such a way that its opponent always have a multiple of k + 1 stones. Yes (k + a) | n then the second player is the one who has a winning strategy. This game supports numerous variants: you can change the set of allowed plays, the number of heaps or the rule "the one that withdraws the last stone wins "for" the one that removes the last stone loses ". In the problems to At the end of the section there are several examples.