Theory of Undergaming
For the disclosure of the theme, let us analyze the variation of the famous game Nim.
And so, on the table are a few piles of stones. in one move, it is allowed to either take an arbitrary number of stones from any pile, or divide any pile into two non-empty ones.
In normal rules, a player who cannot make a move loses. In giveaways, he loses, after whose turn there will be no stones on the table.
Decision
')
To solve the problem, the Olympian must be familiar with Game Theory
The analysis of this variation of the game is not much more complicated than the usual game.
The Sprague-Grande function (or Sprague-Grundy, like someone used to) for an ordinary game has the following form.
G (n) =
{ n-1 with n (mod 4) == 0},
{ n with n (mod 4) == 1 or 2},
{ n + 1 with n (mod 4) == 3}
Proof can be given by induction on n. The case n = 1 is trivial (you can always pick up and win a whole bunch). Let our Grandi function be valid for all k <n. Check for n.
Let's return to the game by the changed rules.
Let us prove the statement that the game is similar to the usual one, except for the cases when there are 1 stone in all heaps. 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 the Sprand Grande numbers, we show that all positions from P are losing, and all of! P (the designation “not P”) are winning, and that there are no moves from P to other positions from P.
It is easy to prove that from any position! P there is a move in R. For this you need to slightly change the strategy of the game. Say, if we leave 1 stone in the pile with the chosen move, take the whole pile instead, and vice versa, if we take the whole pile, then leave 1 stone instead. And finally, if we divide a pile of 2 to 1 stone, we can always leave only 1 stone.
This method allows you to solve problems with the rules of "giveaway", having considered only some extreme cases.
And so, on the table are a few piles of stones. in one move, it is allowed to either take an arbitrary number of stones from any pile, or divide any pile into two non-empty ones.
In normal rules, a player who cannot make a move loses. In giveaways, he loses, after whose turn there will be no stones on the table.
Decision
')
To solve the problem, the Olympian must be familiar with Game Theory
The analysis of this variation of the game is not much more complicated than the usual game.
The Sprague-Grande function (or Sprague-Grundy, like someone used to) for an ordinary game has the following form.
G (n) =
{ n-1 with n (mod 4) == 0},
{ n with n (mod 4) == 1 or 2},
{ n + 1 with n (mod 4) == 3}
Proof can be given by induction on n. The case n = 1 is trivial (you can always pick up and win a whole bunch). Let our Grandi function be valid for all k <n. Check for n.
- From such a handful, you can get a handful of any smaller size by removing the required number of stones, that is, our function with a smaller parameter.
- It can be verified that splitting the heap into two does not allow one to get a position with a Grandi number that is different from G (k), k <n, except for n = 4 * k + 3. Then, P (1, n-1) = G (1) xor G (n-1) = 1 xor (4 * k + 2) = 4 * k + 3 = n. That is, G (4 * k + 3) = n + 1.
Let's return to the game by the changed rules.
Let us prove the statement that the game is similar to the usual one, except for the cases when there are 1 stone in all heaps. 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 the Sprand Grande numbers, we show that all positions from P are losing, and all of! P (the designation “not P”) are winning, and that there are no moves from P to other positions from P.
It is easy to prove that from any position! P there is a move in R. For this you need to slightly change the strategy of the game. Say, if we leave 1 stone in the pile with the chosen move, take the whole pile instead, and vice versa, if we take the whole pile, then leave 1 stone instead. And finally, if we divide a pile of 2 to 1 stone, we can always leave only 1 stone.
This method allows you to solve problems with the rules of "giveaway", having considered only some extreme cases.
Source: https://habr.com/ru/post/101105/
All Articles