August 22, 2010 at 14:01Game Theory
To expand on the topic, we will analyze a variation of the famous Nimes game.
And so, on the table are several piles of stones. in one move it is allowed either to take an arbitrary number of stones from any pile, it is nice to divide any pile into two non-empty ones.
In normal rules, a player who cannot make a move loses. In the giveaways, the one who loses after whose move no stones remain on the table.
Solution
To solve the problem, the Olympian must be familiar with Game Theory
Analysis of this variation of the game is not much more complicated than a regular game.
The Sprag-Grandi function (or Sprag-Grundi, as someone used to) for a regular game has the following form.
G (n) =
{ n-1 for n (mod 4) == 0},
{ nfor n (mod 4) == 1 or 2},
{ n + 1 for n (mod 4) == 3} The
proof can be given by induction on n. The case n = 1 is trivial (you can always pick up and win the whole bunch). Let our Grandi function hold for all k
Let's go back to the game according to the changed rules.
Let us prove the assertion that the game is similar to the usual one, except for the cases when all the heaps have 1 stone each. In this case, nothing depends on the players and the result of the game is determined by the parity n.
Evidence.
We denote the described set of positions by P. According to the definition of Sprague Grandi numbers, we show that all positions from P are losing, and all of! P (notation “not P”) are winning, and that there are no moves from other positions from P to other positions from P.
It is easy to prove that from any position! R there is a move in R. To do this, you need to slightly change the strategy of the game. Say, if we leave 1 stone in the pile in the selected move, instead we take the whole pile and vice versa, if we take the whole pile, we will leave 1 stone instead. And finally, if we divide the pile into 2 by 1 stone, we can always leave only 1 stone.
This method allows you to solve problems with the rules of "giveaway", considering only some extreme cases.
And so, on the table are several piles of stones. in one move it is allowed either to take an arbitrary number of stones from any pile, it is nice to divide any pile into two non-empty ones.
In normal rules, a player who cannot make a move loses. In the giveaways, the one who loses after whose move no stones remain on the table.
Solution
To solve the problem, the Olympian must be familiar with Game Theory
Analysis of this variation of the game is not much more complicated than a regular game.
The Sprag-Grandi function (or Sprag-Grundi, as someone used to) for a regular game has the following form.
G (n) =
{ n-1 for n (mod 4) == 0},
{ nfor n (mod 4) == 1 or 2},
{ n + 1 for n (mod 4) == 3} The
proof can be given by induction on n. The case n = 1 is trivial (you can always pick up and win the whole bunch). Let our Grandi function hold for all k
- From such a heap you can get a heap of any smaller size by removing the required number of stones, i.e. our function with a smaller parameter.
- You can make sure that dividing the heap into two does not allow you to get a position with a Grandi number other than G (k), k
Let's go back to the game according to the changed rules.
Let us prove the assertion that the game is similar to the usual one, except for the cases when all the heaps have 1 stone each. In this case, nothing depends on the players and the result of the game is determined by the parity n.
Evidence.
We denote the described set of positions by P. According to the definition of Sprague Grandi numbers, we show that all positions from P are losing, and all of! P (notation “not P”) are winning, and that there are no moves from other positions from P to other positions from P.
It is easy to prove that from any position! R there is a move in R. To do this, you need to slightly change the strategy of the game. Say, if we leave 1 stone in the pile in the selected move, instead we take the whole pile and vice versa, if we take the whole pile, we will leave 1 stone instead. And finally, if we divide the pile into 2 by 1 stone, we can always leave only 1 stone.
This method allows you to solve problems with the rules of "giveaway", considering only some extreme cases.