Two players, Pasha and Vova, are playing the next game. There is a pile of stones in front of the players. The players take turns, Pasha makes the first move. In one turn, a player can add 1 stone or 10 stones to the pile. For example, having a pile of 7 stones, in one move you can get a pile of 8 or 17 stones. Each player has an unlimited number of stones to make moves. The game ends when the number of stones in the pile becomes at least 31. The winner is the player who made the last move, that is, the first to receive a pile containing 31 or more stones.
At the initial moment, there were S stones in the pile, 1 ≤ S ≤ 30.
Solution.
1. a) Pasha can win if S = 21, ..., 30. With smaller values of S, in one move it is impossible to get a pile with more than 30 stones. Pasha only needs to increase the number of stones by 10. For S 1. b) Vova can win on the first move (no matter how Pasha plays) if the heap initially contains S = 20 stones. Then after Pasha's first move there will be 21 stones or 30 stones in the pile. In both cases, Vanya increases the number of stones by 10 and wins in one move.
2. Possible values of S: 10, 19. In these cases, Pasha obviously cannot win with his first move. However, he can get a pile of 20 stones (at S=10 he increases the number of stones by 10; at S=19 he adds 1 stone). This position is discussed in paragraph 1 b. In it, the player who will move (now this is Vova) cannot win, but his opponent (that is, Pasha) will win on the next move.
3. Possible value of S: 18. After Pasha's first move, there will be 19 or 28 stones in the pile. If there are 28 stones in the pile, Vova will increase the number of stones by 10 and you play with your first move. The situation when there are 19 stones in the heap is dealt with in paragraph 2. In this situation, the player who will move (now this is Vova) wins with his second move.
Guest 26.05.2014 12:31
Point 3. But what about the situation when there are initially 9 stones in the pile. After Pasha’s move, the stones become either 10 or 19, Vasya finishes up to 20 and further according to point 1.b.
Konstantin Lavrov
Yes, 9 is also the correct answer. It is enough to indicate at least one correct value.
Two players, Pasha and Vova, are playing the next game. There is a pile of stones in front of the players. The players take turns, Pasha makes the first move. In one turn, a player can add 1 stone or 10 stones to the pile. For example, having a pile of 7 stones, in one move you can get a pile of 8 or 17 stones. Each player has an unlimited number of stones to make moves. The game ends when the number of stones in the pile becomes at least 41. The winner is the player who made the last move, that is, the first to receive a pile containing 41 or more stones.
At the initial moment there were S stones in the pile, 1 ≤ S ≤ 40.
We will say that a player has a winning strategy if he can win with any moves of his opponent. To describe a player's strategy means to describe what move he should make in any situation that he may encounter with different plays from the enemy.
Complete the following tasks. In all cases, justify your answer.
1. a) Indicate all such values of the number S for which Pasha can win in one move. Justify that all the required values of S have been found and indicate the winning moves.
b) Indicate a value of S such that Pasha cannot win in one move, but with any move of Pasha, Vova can win with his first move. Describe Vova's winning strategy.
2. Indicate two values of S for which Pasha has a winning strategy, and Pasha cannot win in one move, but can win with his second move, regardless of how Vova moves. For the given values of S, describe Pasha's winning strategy.
3. Indicate the value of S at which Vova has a winning strategy that allows him to win with the first or second move in any game of Pasha, but Vova does not have a strategy that will allow him to win with the first move. For the specified value of S, describe Vova’s winning strategy. Construct a tree of all games possible with this winning strategy of Vova (in the form of a picture or table). On the edges of the tree indicate who is making the move, and at the nodes - the number of stones in the pile.
Solution.
1. a) Pasha can win if S = 31, ..., 40. With smaller values of S, in one move it is impossible to get a pile with more than 40 stones. Pasha only needs to increase the number of stones by 10. With S b) Vova can win on the first move (no matter how Pasha plays) if the pile initially contains S = 30 stones. Then after Pasha's first move there will be 31 stones or 40 stones in the pile. In both cases, Vanya increases the number of stones by 10 and wins in one move.
2. Possible values of S: 20, 29. In these cases, Pasha obviously cannot win with his first move. However, he can get a pile of 30 stones (for S = 20 he increases the number of stones by 10; for S = 29 he adds 1 stone). This position is discussed in paragraph 1. b). In it, the player who will move (now this is Vova) cannot win, but his opponent (that is, Pasha) will win on the next move.
3. Possible value of S: 28. After Pasha's first move, there will be 29 or 38 stones in the pile. If the pile reaches 38 stones, Vova will increase the number of stones by 10 and you play with your first move. The situation when there are 29 stones in a heap is dealt with in paragraph 2. In this situation, the player who will move (now this is Vova) wins with his second move.
The table shows the tree of possible games for Vova's strategy described above. The final positions (Vova wins in them) are underlined. In the figure, the same tree is depicted graphically (both ways of depicting a tree are acceptable).
Two players, Petya and Vanya, are playing the next game. In front of them lie two piles of stones, the first of which contains 2, and the second - 3 stones. Every game has a lot of stones. The players take turns, with Petya making the first move. The move consists in the fact that the player either removes the number of stones in some pile, or adds 4 stones to some pile. The game ends at the moment when the total number of stones in two piles is at least 31. If at the moment the game ends the total the number of stones in two piles is at least 40, then Petya won, otherwise Vanya won. Who do you play when both players play without error? What should be the first move of your game? Explain the answer.
Solution.
Vanya wins.
To prove it, consider an incomplete game tree, designed in the form of a table, where each cell contains pairs of numbers separated by a comma. These numbers correspond to the number of stones at each stage of the game in the first and second piles, respectively.
The table contains everything possible options the first player's moves. It shows that for any move of the first player, the second has a move leading to victory.
Two players, Petya and Vasya, are playing the following game. In front of them lie two piles of stones, the first of which contains 2, and the second - 1 stone. Each player has an unlimited number of stones. The players take turns, Petya goes first. The move is that the player either increases the number of stones in some pile by 3 times, or adds 3 stones to some pile. The player wins, after whose move there are at least 24 stones in one of the piles. Who wins when playing without errors? What should the winning player's first move be?
Justify your answer.
Solution.
Petya wins; with his first move he must triple the number of stones in the second pile. To prove it, consider an incomplete game tree, designed in the form of a table, where each cell contains pairs of numbers separated by a comma. These numbers correspond to the number of stones at each stage of the game in the first and second piles, respectively.
The table contains all possible options for Vasya's moves. It shows that with any answer, Petya has a move leading to victory.
Two players, Petya and Vanya, play the following game. There is a pile of stones in front of the players. The players take turns, Petya makes the first move. In one turn, a player can add one stone to the pile or increase the number of stones in the pile five times. For example, having a pile of 10 stones, in one move you can get a pile of 11 or 50 stones. Each player has an unlimited number of stones to make moves.
The game ends the moment the number of stones in the pile becomes more than 100. The winner is the player who made the last move, that is, the first to receive a pile containing 101 or more stones.
At the initial moment there were S stones in the pile, 1 ≤ S ≤ 100.
A player is said to have a winning strategy if he can win with any of his opponent's moves. To describe a player's strategy means to describe what move he should make in any situation that he may encounter with different plays from the enemy.
Complete the following tasks. In all cases, justify your answer.
1. a) For what values of the number S can Petya win with his first move? List all such values and Petit's winning move.
b) Specify a value of S such that Petya cannot win in one move, but for any move Petya makes, Vanya can win with his first move. Describe Vanya's winning strategy.
2. Specify two values of S for which Petya has a winning strategy, and Petya cannot win with his first move, but Petya can win with his second move, regardless of how Vanya moves. For the given values of S, describe Petit's winning strategy.
3. Indicate a value of S such that Vanya has a winning strategy that allows him to win with the first or second move in any Petya game, and at the same time Vanya does not have a strategy that will allow him to win with the first move.
For the given value of S, describe Vanya's winning strategy. Construct a tree of all games possible with Vanya's winning strategy. Present it in the form of a picture or table. For each edge of the tree, indicate who makes the move; for each node, indicate the number of stones in the position.
Solution.
1. a) Petya can win if S = 21, ..., 100. With smaller values of S, in one move it is impossible to get a pile with more than 100 stones. For Petya, it is enough to increase the number of stones by 5 times. When S 1. b) Vanya can win with the first move (no matter how Petya plays), if initially there are S = 20 stones in the heap. Then after Petya’s first move there will be 21 stones or 100 stones in the heap. In both cases, Vanya increases the number of stones 5 times and wins in one move.
2. Possible values of S: 4, 19. In these cases, Petya obviously cannot win with his first move. However, he can get a pile of 20 stones (with S = 4, he increases the number of stones by 5 times; with S = 19, he adds 1 stone). This position is discussed in paragraph 1 b). In it, the player who will move (now Vanya) cannot win, but his opponent (that is, Petya) will win on his next move.
3. Possible value of S: 18. After Petya’s first move, there will be 19 or 90 stones in the pile. If there are 90 stones in the pile, Vanya will increase the number of stones 5 times and win with his first move. The situation when there are 19 stones in the heap is dealt with in paragraph 2. In this situation, the player who will move (now this is Vanya) wins with his second move.
The table shows the tree of possible games for Vanya's strategy described above. The final positions (Vanya wins in them) are underlined. In the figure, the same tree is depicted graphically (both methods of depiction are acceptable).
Take tests on these tasks
The most difficult part of this problem is writing the solution correctly and logically.
So let's start by trying to understand the condition.
- We have two piles of stones and two players: the first (Petya) and the second (Vanya).
- Players take turns.
- During a move, you can either add one stone to any of the piles, or double the number of stones in the pile.
- As soon as there are 73 or more stones in the pile, the game ends.
- The last one to go wins.
Important Notes
- In some tasks we will build a tree of parties. We are obliged to do this according to the condition only in Task 3. In Task 2 we not obliged build a party tree.
- In each of the tasks, it is not enough to simply say who has the winning strategy. You also need to describe it and indicate the possible number of steps that will be required to win.
- It is not enough to call a strategy winning. Need to prove that it leads to winning. Even obvious statements require evidence.
Exercise 1.
Let us now consider Task 1. There are (6, 33) stones in piles (the first part of Task 1) and (8, 32) stones (the second part of Task 1). We need to determine which player has a winning strategy. In other words, which player, if played correctly, will definitely win, regardless of the opponent’s actions.
Here and further we will split the solution into two parts. First there will be a preliminary explanation (there is no need to write it in the Unified State Exam), and then - a “formal decision,” that is, what needs to be written on the Unified State Exam form itself.
Discussion.
Let's think: the first player obviously cannot win in one move, since no matter what he does, the total will not be 73. The “biggest” action he can do is to double the number of stones in the second pile, making them 66. But (6, 66) is 72 stones, not 73. This means that the first one can clearly be won in one move can not. However, the second one is quite capable. The first one can potentially do four actions: add 1 to the first pile, double the number of stones in the first pile, add 1 to the second pile, double the number of stones in the second pile. Let's see where this leads:
- (6.33) -> (7.33). In this case, the second player can double the number of stones in the second pile. We get (7, 66). Total - 73. So the second one wins.
- (6.33) -> (12, 33). In this case, the second player can double the number of stones in the second pile. We get (12, 66). Total - 78. So the second one wins.
- (6.33) -> (6.34). In this case, the second player can double the number of stones in the second pile. We get (6, 68). Total - 74. So the second one wins.
- (6.33) -> (6.66). In this case, the second player can double the number of stones in the second pile. We get (6, 132). Total - 138. So the second one wins.
Total: no matter how the first player behaves, the second will win in one move.
Solves similarly with (8.32).
Formal solution to Task 1.
The second player has a winning strategy. Let's prove it and show this strategy. To do this, we will build a party tree for each of the initial positions. In the game tree, we will indicate the state of both piles in the format (a,b), where a is the number of stones in the first pile, b is the number of stones in the second pile. When the first player turns, we will consider four possible options for his behavior: add 1 to the first pile, double the number of stones in the first pile, add 1 to the second pile, double the number of stones in the second pile. For the second player, we will indicate one move each that leads to a win. We will show moves in the form of arrows, next to which we write I in the case of the first move and II in the case of the second move.
Game tree for starting position (6, 33).
Game tree for starting position (8, 32).
According to the game tree, regardless of the moves of the first, the second always has a winning strategy that allows him to win in one move, described in the trees (the sums after Vanya’s moves are, from left to right, 73, 80, 74 and 136, respectively). Moreover, according to the game tree, the second player can win in exactly one move.
Task 2
Formal solution
Consider the initial position (6,32). Note that it is close to (6,33) from Task 1. In Task 1 we found out that in position (6, 33) the second one wins, and in one move. This condition can be reformulated: in position (6.33) the one who wins in one move is Not walks (that is, walks second). Or, in other words, the one who moves loses in one move.
In position (6.32), the first one wins in two moves. Let's prove it. On his first move, Petya adds +1 to the second pile. Thus, the position (6.33) is obtained. As we found out earlier, in position (6,33) the one who moves loses. In our case it will be Vanya's move. Therefore, Vanya will lose in one move. In this case, Petya will have to make two moves in total: the first (add 1 stone to the second pile) + the second move in accordance with the Party Tree in Task 1, acting according to Vanya’s strategy.
Similarly in position (7, 32). With his first move, Petya adds +1 stone to the first pile, getting position (8, 32). In this position, according to the same reasoning, the one who moves loses. It will be Vanya's move, so Vanya will lose. Petya's winning strategy is as follows: Petya adds +1 stone to the first pile, and then follows Vanya's strategy from Task 1.
Similarly in position (8, 31). With his first move, Petya adds +1 stone to the second pile, getting position (8, 32). In this position, according to the same reasoning, the one who moves loses. It will be Vanya's move, so Vanya will lose. Petya's winning strategy is as follows: Petya adds +1 stone to the second pile, and then follows Vanya's strategy from Task 1.
Task 3
Discussion
Note that from situation (7, 31) it is very easy to end up either in situations (8, 31) and (7, 32), in which, according to the previous Task, the one who moves wins, or in situation (14, 31) and (7, 62), in which the one who moves can win in one move by doubling the number of stones in the second pile. Thus, it turns out that Vanya must have a winning strategy. Moreover, he can win both in 2 moves (the first two cases) and in one move (the second two cases).
Formal solution
In the initial position (7, 31), Vanya wins in one or two moves. Let's prove it. To do this, we will build a tree of all parties.
Tree of all games for the starting position (7, 31).
According to the tree of all games, Vanya wins either in one move (if Petya doubled the number of stones in the first or second pile) or in two moves (if Petya increased the number of stones in the first or second pile by 1).
Thus, in the initial position (7, 31) Vanya has a winning strategy, and Vanya will win in one or two moves.
Evgeny Smirnov
IT expert, computer science teacher
The lesson covers the analysis of task 26 of the Unified State Exam in computer science: a detailed explanation and solution to the 2017 task is given
The 26th task - “Game theory, search for a winning strategy” - is characterized as a task high level complexity, completion time – approximately 30 minutes, maximum score – 3
* Some images and page examples are taken from the presentation materials of K. Polyakov
Game theory. Finding a winning strategy
To solve task 26, you need to remember the following topics and concepts:
- in order to find a winning strategy in simple games, it is enough to use the method of enumerating all possible options for player moves;
- to solve problems 26 tasks are most often used for this tree construction method;
- if two branches extend from each node of the tree, i.e. possible options for moves, then such a tree is called binary(if there are three continuation options from each position, the tree will be ternary).
- all positions in simple games are divided into winning and losing;
- winning position– this is a position in which the player making the first move will definitely win no matter what the opponent does, unless he makes a mistake; at the same time they say that this player has winning strategy– an algorithm for choosing the next move that allows him to win;
- if the player making the first move is in losing position, then he will definitely lose unless his opponent makes a mistake; in this case it is said that this player has no winning strategy; Thus, the general strategy of the game is to create a losing position for your opponent with your move;
- winning and losing positions are characterized as follows:
- a position from which all possible moves lead to winning positions – losing;
- a position from which at least one of the subsequent possible moves leads to a losing position - winning, and the player's strategy is to turn the game into a losing one(for opponent) position.
- in order to determine which player will win with a strategically correct game, it is necessary to answer the questions:
- Can any player win, regardless of the other players' moves?
- What must a player with a winning strategy do on his first move so that he can win, regardless of the actions of the players' moves?
Winning strategy
Winning and losing positions
Who will win with a strategically correct game?
Let's look at an example:
A game: there are 5 matches in a pile; played by two players who take turns removing matches from the pile; condition: in one move you can remove 1 or 2 matches; The winner is the one who leaves 1 match in the pile
Solution:
Answer: with the correct game (game strategy), the first player will win; To do this, he only needs to remove one match with his first move.
Solving 26 Unified State Exam tasks in computer science
Analysis of task 26 of the Unified State Exam in computer science 2017 FIPI option 5 (Krylov S.S., Churkina T.E.):
Two players, Pasha and Valya, are playing the following game. There is a pile of stones in front of the players. The players take turns Pasha makes the first move one twice. For example, having a pile of 7 stones, in one move you can get a pile of 14 or 8 stones. Each player has an unlimited number of stones to make a move.
The game ends when the number of stones in the pile becomes at least 28 . If at the same time there are no more than 44 stones, the winner is the player who made the last move. IN otherwise his opponent becomes the winner. For example, if there were 23 stones in the pile, and Pasha doubles the number of stones in the pile, then the game will end and Valya will be the winner. At the initial moment there were S stones in the pile, 1≤ S ≤ 27.
Exercise 1
a) At what values of the number S Can Pasha win in one move? List all such values and Pasha's corresponding moves.
b) Which player has a winning strategy when S = 26, 25, 24? Describe winning strategies for these cases.
Task 2
S = 13, 12? Describe relevant winning strategies.
Task 3
Which player has a winning strategy when S=11? Construct a tree of all games possible with this winning strategy (in the form of a picture or table). On the edges of the tree indicate who is making the move; in nodes - the number of stones in the position.
✍ Solution:
For a detailed explanation of task 26 of the Unified State Exam, watch the video:
Analysis of task 26 of the Unified State Exam in computer science 2017 (one of the options according to a graduate):
Petya and Vanya play a game: there is a set of words, you need to consistently name the letters of these words. The winner is the player who names the last letter of any word from the set. Petya goes first.
For example, there is a set of words (Wolf, Computer Science, Scary); for a given set of words, Petya can name the letter with his first move IN, AND or WITH. If Petya chooses the letter IN, then Vanya will win (next moves: Petya - IN, Vania - ABOUT, Peter - L, Vania - TO).
Exercise 1
A) Given 2 words (set of letters) ( IKLMNIKLMNH, NMLKINMLKI). Determine a winning strategy.
B) Given 2 words ( TRITRITRI...THREE, RITARITARITARITARITA...RITA). In the first word 99 letters, in the second 164 . Determine a winning strategy.
Task 2
It is necessary to swap two letters from the item set 1A in the word with the shortest length so that the winning strategy is the other player. Explain a winning strategy.
Task 3
Given a set of words ( Crow, Wolf, Wave, Derivative, Prokhor, Millet). Which player has a winning strategy? Justify your answer and write a tree of all possible games for a winning strategy.
✍ Solution:
* For Vanya, only strategy moves are displayed
**Red circle means win
For more details on solving the word problem, watch the video tutorial:
Solution 26. Demo version of the Unified State Exam 2018 computer science:
Two players, Petya and Vanya, play the following game. There is a pile of stones in front of the players. The players take turns, Petya makes the first move. In one turn, a player can add to the pile one stone or increase the number of stones in the pile twice. For example, having a pile of 15 stones, in one move you can get a pile of 16 or 30 stones. Each player has an unlimited number of stones to make moves.
The game ends when the number of stones in the pile becomes at least 29. The winner is the player who made the last move, that is, the first to receive a pile containing 29 or more stones. At the initial moment there were S stones in the pile, 1 ≤ S ≤ 28.
We will say that a player has a winning strategy if he can win with any moves of his opponent. To describe a player's strategy means to describe what move he should make in any situation that he may encounter with different plays from his opponent. Description of a winning strategy do not do it include moves of a player playing according to this strategy that are not unconditionally winning for him, i.e. not winning regardless of the opponent's play.
Exercise 1
A) Indicate such values of the number S for which Petya can win in one move.
b) Indicate a value of S such that Petya cannot win in one move, but for any move Petya makes, Vanya can win with his first move. Describe Vanya's winning strategy.
Task 2
Specify two such values of S for which Petya has a winning strategy, and:
— Petya cannot win in one move;
- Petya can win with his second move, regardless of how Vanya moves.
For the given values of S, describe Petit's winning strategy.
Task 3
Specify the value of S at which:
— Vanya has a winning strategy that allows him to win with the first or second move in any of Petya’s games;
— Vanya does not have a strategy that will allow him to be guaranteed to win on his first move.
For the given value of S, describe Vanya's winning strategy. Construct a tree of all games possible with this winning strategy (in the form of a picture or table). On the edges of the tree indicate who is making the move; in nodes - the number of stones in a position
The tree should not contain games that are impossible if the winning player implements his winning strategy. For example, the complete game tree is not the correct answer to this task.
✍ Solution:
- Exercise 1.
- a) Petya can win if S = 15, … 28
Task 2.
Task 3.
The table shows a tree of possible games (and only them) for Vanya’s described strategy. The final positions (Vanya wins in them) are underlined. In the figure the same tree is depicted graphically. 
Tree of all games possible under Vanya's strategy:
*red circle means win
Early exam in computer science 2018, option 1. Task 26:
Two players, Pasha and Vasya, are playing the following game. There is a pile of stones in front of the players. The players take turns Pasha makes the first move. In one turn, a player can add to the pile one or four stone or increase the number of stones in a pile five times. The game ends when the number of stones the heap becomes at least 69.
The winner is the player who made the last move, that is, the first to receive a pile containing 69 or more stones. At the initial moment there were S stones in the pile, 1 ≤ S ≤ 68.
Exercise 1.
A) Indicate all values of the number S for which Pasha can win in one move. Justify that all required values of S have been found, and indicate the winning move for each specified value of S.
b) Specify a value of S such that Pasha cannot win in one move, but with any move of Pasha, Vasya can win with his first move. Describe Vasya's winning strategy.
Task 2. Specify 2 such values of S for which Pasha has a winning strategy, and Pasha cannot win in one move and can win with his second move, regardless of how Vasya moves. For each value of S given, describe Pasha's winning strategy.
Task 3. Indicate at least one value of S for which Vasya has a winning strategy that allows him to win with the first or second move in any game of Pasha, and Vasya does not have a strategy that will allow him to win with the first move. For the specified value of S, describe Vasya's winning strategy. Construct a tree of all games possible with this winning strategy of Vasya (in the form of a picture or table).
✍ Solution:
- 1.
A) S ≥ 14. If the number of stones in the pile is 14 or more, Pasha needs to increase their number five times, thereby obtaining 70 or more stones.
b) S=13. Pasha can make 14, 17 or 65 stones on his first move, after which Vasya increases the number five times, getting 70, 85 or 325 stones in the pile.
S = 13 Pasha 1st move: 13 + 1 = 14 Pasha 1st move: 13 + 4 = 17 Pasha 1st move: 13 * 5 = 65 Vanya 1st move: * 5 = S ≥ 14 Vanya wins 13 - losing position
2.
S = 9, 12. For these cases, Pasha needs to add 4 stones to a pile of 9 stones, or 1 stone to a pile of 12, and get a pile of 13 stones.
After which the game comes down to the strategy described in paragraph 1b.
S = 13 Pasha 1st move: 9 + 4 = 13 Pasha wins Pasha 1st move: 12 + 1 = 13 Pasha wins 9, 12 - winning positions from the second move
3.
S=8. With his first move, Pasha can make the number of stones in the pile 9, 12 or 40. If Pasha increases the number by five times, then Vasya wins with his first move, increasing the number of stones by five times.
For the case of 9 and 12 stones, Vasya uses the strategy specified in clause 2.
S = 8 Pasha 1st move: 8 + 1 = 9 Vanya Wins (see point 2) Pasha 1st move: 8 + 4 = 12 Vanya Wins (see point 2) Pasha 1st move: 8 * 5 = 40
Watch the video for the solution to task 26:
Unified State Exam simulator in computer science 2018, test version 1. Task 26 (Krylov S., Ushakov D.):
one stone or . The game ends at the moment when the total number of stones in the piles becomes at least 73.
The winner is the player who made the last move, i.e. the first to receive such a position that the piles will contain 73 stones or more.
Exercise 1.
(6, 33), (8, 32)
indicate which player has a winning strategy. In each case, describe the winning strategy; explain why this strategy leads to winnings and indicate what greatest number moves may be required for the winner to win with this strategy.
Task 2.
For each of the starting positions (6, 32), (7, 32), (8, 31)
indicate which player has a winning strategy.
Task 3.
For starting position (7, 31)
indicate which player has a winning strategy. Construct a tree of all games possible with the winning strategy you specified. Imagine the tree as a picture or table.
✍ Solution:
Video solution to task 26 with two heaps:
26_6: Analysis of task 26 from K. Polyakov’s website (No. 31):
Two players, Petya and Vanya, play the following game. In front of the players are two piles of stones. The players take turns, Petya makes the first move. In one turn, a player can add to one of the piles (of his choice) two stones or double the number of stones in the pile. In order to make moves, each player has an unlimited number of stones. The game ends at the moment when the total number of stones in the piles becomes at least 44.
The winner is the player who made the last move, i.e. the first to obtain such a position that the piles will contain 44 or more stones.
At the initial moment in the first heap there was 5 stones, in the second heap – S stones; 1 ≤ S ≤ 38.
Exercise 1.
At what S: 1a)
Petya wins with his first move; 1b)
Does Vanya win with his first move?
Task 2.
Name any one value S, in which Petya can win with his second move.
Task 3.
Give the value of S at which Vanya wins with his first or second move.
✍ Solution:
5 + 20*2 = 45 (>44) * 5 - the number of stones in the first heap, it does not change according to the condition
Answer 1 a):
S= (On the Unified State Exam, explain the moves, for example: (5; 20) -> (Petit’s move) -> (5; 40); 40 + 5 = 45)
Task 1 b):
Answer 1 b): S=19 (On the Unified State Exam, explain the moves, for example: (5; 19) -> (Petya’s moves): (5;21),(5;28);(7;19);(7;28). Vanya will win everywhere with the next move, see previous paragraph)
Task 2:
Answer 2: S = 16, 17 or 18
Task 3:
Answer 3:
S=14 (On the Unified State Exam, explain the moves, referring to the explanations in the previous paragraphs)
Analysis of task 26 of the 2017 Unified State Exam in computer science from the demo version. This is a task from the second part of a high level of difficulty. Approximate time to complete the task is 30 minutes. The maximum score for completing the task is 3.
Checked content elements:
— The ability to build a game tree according to a given algorithm and justify a winning strategy.
Task 26
Two players, Pasha and Valya, are playing the following game. There is a pile of stones in front of the players. The players take turns, Pasha makes the first move. In one turn, a player can add to the pile one stone or increase the number of stones in the pile twice. For example, having a pile of 15 stones, in one move you can get a pile of 16 or 30 stones. Each player has an unlimited number of stones to make moves.
The game ends at the moment when the number of stones in the pile becomes at least 20. If at the same time there are no more than 30 stones in the pile, then the player who made the last move is considered the winner. Otherwise, his opponent becomes the winner. For example, if there were 17 stones in the pile and Pasha doubles the number of stones in the pile, then the game will end and Valya will be the winner. At the initial moment there was in the heap S stones, 1 ≤ S ≤ 19.
We will say that the player has winning strategy, if he can win with any moves of the opponent. To describe a player's strategy means to describe what move he should make in any situation that he may encounter with different plays from the opponent.
Complete the following tasks.
1. a) At what values of the number S Can Pasha win in one move?
List all such values and Pasha's corresponding moves.
b) Which player has a winning strategy when S = 18, 17, 16?
Describe winning strategies for these cases.
2. Which player has a winning strategy when S= 9.8? Describe relevant winning strategies.
3. Which player has a winning strategy when S= 7? Construct a tree of all games possible with this winning strategy (in the form of a picture or table). On the edges of the tree indicate who is making the move; in nodes – the number of stones in the position.
1. a) Pasha can win if S= 19 or S= 10, 11, 12, 13, 14, 15. When S= 19 the first move is to add one stone to the pile, with the remaining values indicated S you need to double the number of stones.
b) When S= 16, 17 or 18, doubling the number of stones does not make sense, since after such a move the opponent wins. Therefore, we can assume that the only possible move is to add one stone to the pile.
At S= 18 after such a move by Pasha there will be 19 stones in the pile. In this position, the one who walks (i.e. Valya) wins (see point 1a): at S= 18 Pasha (the player who must go first) loses.
Valya has a winning strategy.
At S= 17, after Pasha adds one stone with his first move, there will be 18 stones in the pile. In this position, the player (i.e. Valya) loses (see above): at S= 17 Pasha (the player who must go first) wins. Pasha has a winning strategy.
At S= 16 Valya has a winning strategy. Indeed, if Pasha doubles the number of stones on his first move, then the pile becomes 32 stones, and the game immediately ends with Vali winning. If Pasha adds one stone, then the pile becomes 17 stones. As we already know, in this position the player who must move (i.e. Valya) wins.
In all cases, winning is achieved by the fact that during his move, the player with a winning strategy must add one stone to the pile.
It is possible to draw trees of all possible parties for specified values S.
Another possibility is to (1) point out that doubling the heap does not make sense, and (2) reduce the case sequentially S= 18 per case S= 19, case S= 17 – to the occasion S= 18, etc.
2. When S= 9 or 8 Pasha has a winning strategy. It consists of doubling the number of stones in the pile and getting a pile that will have 18 or 16 stones, respectively. In both cases, the player who makes the move (now Valya) loses (see point 1b).
3. When S= 7 Valya has a winning strategy. After Pasha's first move, the pile can have either 8 or 14 stones. In both of these positions, the player who makes the move (now Valya) wins. Happening S= 8 considered in point 2, case S= 14 reviewed in point 1a.
The table shows the tree of possible games for Vali's described strategy. The final positions (Valya wins in them) are underlined. In the figure, the same tree is depicted graphically (both ways of depicting a tree are acceptable).
The tree of all games possible under Valya's strategy. The >> sign indicates the positions at which the game ends.
