Informatics exam 26 word assignment. Game theory. Finding a winning strategy

In this task, the most difficult part is to correctly and logically write down the solution.

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).
The 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 one who went last won.

Important Notes

We will build a party tree in some tasks. We are obliged to do this according to the condition only in Task 3. In Task 2 we not required build a party tree.
In each of the tasks, it is not enough just to say who has a winning strategy. It is also required to describe it and indicate the possible number of steps that will be required to win.
It is not enough to call the strategy winning. Need to prove that it leads to a win. Even obvious statements require proof.

Exercise 1.

Consider now Task 1. In heaps - (6, 33) stones (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 of the players, if played correctly, will definitely win, regardless of the actions of the opponent.

Here and below, we will divide the solution into two parts. First, there will be a preliminary explanation (it is not necessary to write it in the USE), and then - a "formal decision", that is, what needs to be written in the USE form itself.

Discussion.

Let's think: the first player obviously cannot win in one move, because no matter what he does, there will not be a total of 73. The "largest" 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. So, the first one in one move is clearly to win can not. However, the second one can. The first can potentially do four things: 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). In 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). In 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). In 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). In total - 138. So, the second one wins.

Total: no matter how the first player behaves, the second one will win in one move.

It is solved similarly with (8.32).

Formal solution of 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. During the move of the first player, 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, leading to a win. We will show the 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 73, 80, 74 and 136, respectively, from left to right). At the same time, 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 Not walks (that is, walks second). Or, in other words, the one who walks loses in one move.

In the 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 the 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 Game Tree in Task 1, acting according to Vanya's strategy.

Similarly in position (7, 32). Petya, on his first move, adds +1 stone to the first pile, getting position (8, 32). In this position, according to the same reasoning, the one who moves loses. There 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). Petya, on his first move, adds +1 stone to the second pile, getting the position (8, 32). In this position, according to the same reasoning, the one who moves loses. There 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 get either into situations (8, 31) and (7, 32), in which, according to the previous Task, the one who moves wins, or into 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. At the same time, 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 construct a tree of all parties.

Tree of all games for 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 piles), or in two moves (if Petya doubled the number of stones in the first or second piles).

Thus, in the initial position (7, 31), Vanya has a winning strategy, and Vanya will win in one or two moves.

Evgeny Smirnov

Expert in IT, computer science teacher

The lesson considered the analysis of the 26th task of the exam in computer science: given detailed explanation and the solution of the task of 2017

The 26th task - "Game theory, the search for a winning strategy" - is characterized as a task of a high level of complexity, the execution time is about 30 minutes, the maximum score is 3

* Some images and page examples are taken from K. Polyakov's presentation materials

Game theory. Finding a winning strategy

To solve task 26, you need to remember the following topics and concepts:

Winning strategy

in order to find a winning strategy in simple games, it is sufficient to use the method of enumeration of all possible variants of the players' moves;
to solve problems 26 tasks are most often used for this tree construction method;
if two branches depart from each node of the tree, i.e. possible moves, then such a tree is called binary(if there are three continuation options from each position, the tree will be ternary).

Winning and losing positions

all positions in simple games divided into winning and losing;
winning position- this is such a position in which the player making the first move will definitely win in any actions of the opponent, if he does not make a mistake; it is said that this player has winning strategy- an algorithm for choosing the next move, allowing him to win;
if the player making the first move is in losing position, then he will definitely lose if his opponent does not make a mistake; in this case we say that this player has no winning strategy; thus, the general strategy of the game is to create a losing position for the opponent with one's 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 this losing(for opponent) position.

Who wins with a strategically correct game?

in order to determine which of the players will win in a strategically correct game, it is necessary to answer the following questions:
Can either player win, regardless of the other players' moves?
What should a player with a winning strategy do on their first move so that they can win, regardless of the actions of the players' moves?

Consider an example:

A game: there are 5 matches in a pile; two players play, who take turns removing matches from a pile; condition: in one move you can remove 1 or 2 matches; the one who leaves 1 match in the pile wins

Solution:

Answer: with the correct game (game strategy), the first player will win; to do this, it is enough for him to remove one match with his first move.

Solving 26 USE tasks in computer science

Analysis of the 26th task of the Unified State Examination in Informatics 2017 FIPI option 5 (Krylov S.S., Churkina T.E.):

Two players, Pasha and Valya, play 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, no more than 44 stones, the winner is the player who made the last move. 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) For what values of the number S Pasha can win in one move? Indicate all such values and the corresponding moves of Pasha.
b) Which of the players has a winning strategy for S = 26, 25, 24? Describe winning strategies for these cases.

Task 2
S = 13, 12? Describe relevant winning strategies.

Task 3
Which of the players has a winning strategy for S=11? Construct a tree of all games possible with this winning strategy (in the form of a figure or a table). On the edges of the tree indicate who makes the move; in nodes — the number of stones in the position.

✍ Solution:

For a detailed explanation of task 26 of the exam, see the video:

Analysis of task 26 of the Unified State Examination in Informatics 2017 (one of the options according to the graduate):

Petya and Vanya are playing a game: there is a set of words, you need to sequentially name the letters of these words. The player who names the last letter of any word from the set wins. Petya goes first.

For example, there is a set of words (Wolf, Informatics, Scary); for a given set of words, Petya's first move can name a letter IN, AND or WITH. If Petya chooses a letter IN, then Vanya will win (the following moves: Petya - IN, Vania - ABOUT, Peter - L, Vania - TO).

Exercise 1
A) 2 words (a set of letters) are given ( IKLMNIKLMNH, NMLKINMLKI). Determine a winning strategy.

B) 2 words are given ( THREETHREE…THREE, RITARITARITARITA…RITA). In the first word 99 letters, in the second 164 . Determine a winning strategy.

Task 2
You need to swap two letters from the point set 1A in the word with the smallest length so that the other player has a winning strategy. Explain 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 information on solving the task about words, see the video lesson:

Decision 26. Demo version of the exam 2018 computer science:

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 for 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 opponent's plays. To the description of the winning strategy do not do it include the moves of the player playing according to this strategy, which are not unconditionally winning for him, i.e. not being winning regardless of the opponent's game.

Exercise 1
A) Indicate such values of the number S for which Petya can win in one move.
b) Indicate a value of S for which Petya cannot win in one move, but for any Petya's move Vanya can win with his first move. Describe Vanya's winning strategy.

Task 2
Indicate two such values of S for which Petya has a winning strategy, moreover:
- Petya cannot win in one move;
— Petya can win with his second move, regardless of how Vanya moves.
For the indicated values of S, describe Petya's winning strategy.

Task 3
Specify the value of S, at which:
- Vanya has a winning strategy that allows him to win on the first or second move in any game of Petya;
- Vanya does not have a strategy that will allow him to win with a guarantee on the 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 figure or a table). On the edges of the tree indicate who makes the move; in knots - the number of stones in a position

The tree should not contain games that are impossible for the winning player to implement his winning strategy. For example, the complete game tree is not a valid answer for this task.

✍ Solution:

Exercise 1.

a) Petya can win if S = 15, ... 28

15, ..., 28 - winning positions from the first move

b) Vanya can win on the first move (no matter how Petya plays) if there are S=14 stones. Then after Petya's first move there will be 15 or 28 stones in the pile. In both cases Vanya doubles the pile and wins in one move.

S = 14 Petya: 14 + 1 = 15 winning position (see item a). Vanya Petya wins: 14 * 2 = 28 winning position (see item a). Vanya wins 14 - losing position

Task 2.

Possible values S: 7, 13. In these cases Petya obviously cannot win on the first move. However, he can get a pile of 14 stones: in the first case by doubling, in the second by adding one stone. This position is discussed in paragraph 1b. In it, the player who will move (now this is Vanya) cannot win, and his opponent (that is, Petya) will win on the next move.

S = 7 Peter: 7 * 2 = 14 is a losing position (see point 1 b). Petya wins S = 13 Petya: 13 + 1 = 14 losing position (see item 1 b). Petya wins 7, 13 - winning positions from the second move

Task 3.

Possible values S: 12. After Petya's first move, there will be 13 or 24 stones in the pile. If there are 24 stones in the pile, Vanya will double the number of stones and win on the first move. The situation, when there are 13 stones in a pile, is analyzed in paragraph 2. In this situation, the player who will move (now it is Vanya) wins with his second move.

S = 12 Petya: 12 + 1 = 13 Vanya: 13 + 1 = 14 losing position (see point 1 b). Vanya wins second move!

The table shows the tree of possible games (and only them) for Vanya's described strategy. The final positions (Vanya wins them) are underlined. In the figure, the same tree is shown graphically.

Tree of all games possible with Vanya's strategy:

* red circle means win

Early exam in computer science 2018, option 1. Task 26:

Two players, Pasha and Vasya, play 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 move, the player can add to the pile one or four stone or increase the number of stones in the pile by five times. The game ends when the number of stones in 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 such values of the number S for which Pasha can win in one move. Justify that all required values of S are found, and indicate the winning move for each specified value of S.

b) Indicate a value of S for which Pasha cannot win in one move, but Vasya can win with his first move in any move of Pasha. Describe Vasya's winning strategy.

Task 2. Indicate 2 values of S for which Pasha has a winning strategy, and Pasha cannot win in one move and can win on his second move regardless of how Vasya moves. For each given value of S, 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 on the first or second move whenever Pasha plays, and Vasya does not have a strategy that will allow him to win on the first move. For the given value of S, describe Vasya's winning strategy. Construct a tree of all games possible with this winning Vasya's strategy (in the form of a figure or a table).

✍ Solution:

S ≥ 14

S ≥ 14 winning positions

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 a pile.

S = 13 Pasha 1 move: 13 + 1 = 14 Pasha 1 move: 13 + 4 = 17 Pasha 1 move: 13 * 5 = 65 Vanya 1 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 that, the game is reduced to the strategy described in paragraph 1b.

S = 13 Pasha 1 move: 9 + 4 = 13 Pasha wins Pasha 1 move: 12 + 1 = 13 Pasha wins 9, 12 - winning positions from the second move

3. S=8. On his first move, Pasha can make the number of stones in the pile 9, 12, or 40. If Pasha increases the number five times, then Vasya wins on his first move, increasing the number of stones five times.
For the case of 9 and 12 stones, Vasya uses the strategy indicated in item 2.

S = 8 Pasha 1 move: 8 + 1 = 9 Vanya Wins (see item 2) Pasha 1 move: 8 + 4 = 12 Vanya Wins (see item 2) Pasha 1 move: 8 * 5 = 40

See the video for the solution to task 26:

USE simulator in informatics 2018, control option 1. Task 26 (Krylov S., Ushakov D.):

one stone or . The game ends 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 get such a position that there will be a total of 73 stones or more in the piles.

Exercise 1.
(6, 33), (8, 32) indicate which of the players has a winning strategy. In each case, describe the winning strategy; explain why this strategy leads to a win, and indicate the maximum number of moves the winner can take to win with this strategy.

Task 2.
For each of the initial positions (6, 32), (7, 32), (8, 31) indicate which of the players has a winning strategy.

Task 3.
For starting position (7, 31) indicate which of the players has a winning strategy. Construct a tree of all games possible with the winning strategy you have specified. Present the tree in the form of a picture or a table.

✍ Solution:

Video of solving 26 tasks with two piles:

26_6: Analysis of task 26 from the site of K. Polyakov (No. 31):

Two players, Petya and Vanya, play the following game. There are two piles of stones in front of the players. Players move in turn, Petya makes the first move. In one turn, the 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 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 get such a position that there will be a total of 44 or more stones in the piles.

At the initial moment, the first heap contained 5 stones, in the second heap - S stones; 1 ≤ S ≤ 38.
Exercise 1.
At what S: 1a) Petya wins on the first move; 1b) Vanya wins on the first move?

Task 2.
Name one value S, under which Petya can win on his second move.

Task 3.
Name 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 pile, it does not change according to the condition

Accordingly, all values big 20 will result in a larger number 44 . Let's put it in the table. + means a winning position from the first move:

Answer 1 a): S= (On the exam, explain the moves, for example: (5; 20) -> (Petit's move) -> (5; 40); 40 + 5 = 45)

Task 1 b):

Since Vanya will move second, it is necessary to change the number of stones in the first pile. So let's consider the situations where Petya could move on the first move to (7;S) and in (10;S). Let us indicate whether these positions will be winning from one move: for example (7;19) winning position, because the player will make a move (7;38) and win (7 + 38 = 45). Accordingly, all positions are winning (7; over 19). Let's analyze the table, increasing the number of stones in the first pile and searching for winning positions in one move:

The following logic of reasoning: Vanya can win with his first move, when Petya, with his first move, can only move to winning positions from the first move (to +). We mark such positions, considering that this is Petya's first move, and the number of stones in the first pile should be 5. The positions found will be losing positions (-):

We find the only such value - (5; 19). Those. S = 19.

Answer 1 b): S=19 (On the 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 point)

Task 2:

Please note that in the table, all formed "corners" are losing positions (from the 1st move): that is, if the player finds himself in such a position, then he can only move to winning positions (that is, the opponent will win the next move) :

Reasoning logic: Petya will be able to win with his second move when he gets into a losing position with his first move, i.e. will put the opponent in a losing situation. Such values: S = 16, 17 or 18. Let's call these positions winning from the second move (2+):

Answer 2: S = 16, 17 or 18

Task 3:

We also indicate in the table the positions that are winning from the n-th move: when the player can transfer the opponent to a losing position:

We also indicate the losing positions from the second move: the player who finds himself in such a position can only move to winning positions (then the opponent will win):

Reasoning logic: Vanya will be able to win with his first or second move, when Petya with his first move can hit only either to a winning position from the first move (+), or to a winning position from the second move or the n-th move (2+). This is the position at S = 14:

Answer 3: S=14 (On the exam, explain the moves, referring to the explanations in the previous paragraphs)

Analysis of the 26 task of the USE 2017 in informatics from the demo. This is a task from the second part of a high level of difficulty. Estimated 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, play the following game. There is a pile of stones in front of the players. Players move in turn, Pasha makes the first move. In one move, the 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, the heap had 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 opponent's plays.

Complete the following tasks.
1. a) For what values of the number S Pasha can win in one move?
Indicate all such values and the corresponding moves of Pasha.
b) Which of the players has a winning strategy for S = 18, 17, 16?
Describe winning strategies for these cases.
2. Which of the players has a winning strategy when S= 9, 8? Describe relevant winning strategies.
3. Which of the players has a winning strategy when S= 7? Construct a tree of all games possible with this winning strategy (in the form of a figure or a table). On the edges of the tree indicate who makes 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. With S= 19 In the first move, one stone must be added 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 walker (i.e. Valya) wins (see point 1a): at S= 18 Pasha (the player who must go first) loses.

Vali has a winning strategy.

At S= 17, after Pasha adds one stone on his first move, there will be 18 stones in the pile. In this position, the walker (i.e. Valya) loses (see above): at S= 17 Pasha (the player who must move first) wins. Pasha has a winning strategy.

At S= 16 Vali has a winning strategy. Indeed, if Pasha doubles the number of stones on his first move, then there are 32 stones in the pile, and the game immediately ends with Valya winning. If Pasha adds one stone, then there are 17 stones in the pile. As we already know, in this position the player who has to move (i.e. Valya) wins.

In all cases, the win 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 batches for the specified values S.
Another possibility is to (1) point out that doubling the heap does not make sense, and (2) successively reduce the case S= 18 per case S= 19, case S= 17 - to the case S= 18 etc.

2. When S= 9 or 8 Pasha has a winning strategy. It consists in doubling the number of stones in the heap and getting a heap containing 18 or 16 stones, respectively. In both cases, the player who will make the move (now it's Valya) loses (see point 1b).

3. When S= 7 Vali has a winning strategy. After Pasha's first move, the heap can contain either 8 or 14 stones. In both of these positions, the player who will make the move wins (now it's Valya). Happening S= 8 considered in paragraph 2, case S= 14 considered in paragraph 1a.

The table shows the tree of possible games for the described Wali strategy. The final positions (Valya wins them) are underlined. In the figure, the same tree is shown graphically (both ways of representing the tree are acceptable).

The tree of all games possible with Valya's strategy. The >> sign denotes the positions where the game ends.

Two players, Pasha and Vova, play the following game. There is a pile of stones in front of the players. Players move in turn, Pasha makes the first move. In one turn, the 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 heap, 1 ≤ S ≤ 30.

Solution.

1. a) Pasha can win if S = 21, ..., 30. With smaller values of S, one cannot get a pile containing more than 30 stones in one move. It is enough for Pasha to increase the number of stones by 10. With S 1. b) Vova can win on the first move (no matter how Pasha plays) if initially there are S = 20 stones in the heap. 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 the 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, and 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 on your first move. The situation, when there are 19 stones in a pile, is discussed in paragraph 2. In this situation, the player who will move (now it 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 a pile. After Pasha's move, the stones become either 10 or 19, Vasya finishes up to 20 and further according to paragraph 1.b.

Konstantin Lavrov

Yes, 9 is also the correct answer. It is enough to specify at least one correct value.

Two players, Pasha and Vova, play the following game. There is a pile of stones in front of the players. Players move in turn, Pasha makes the first move. In one turn, the 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 heap, 1 ≤ S ≤ 40.

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 are found, and indicate the winning moves.

b) Indicate the value of S. for which Pasha cannot win in one move, but for 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 on his second move regardless of how Vova moves. For the given values of S, describe Pasha's winning strategy.

3. Specify the value of S for which Vova has a winning strategy that allows him to win on the first or second move whenever Pasha plays, but Vova does not have a strategy that will allow him to win on the first move. For the given 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 figure or a table). On the edges of the tree indicate who makes the move, 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, one cannot get a pile with more than 40 stones in one move. It is enough for Pasha to increase the number of stones by 10. With S b) Vova can win on the first move (no matter how Pasha plays) if initially there are S = 30 stones in the heap. 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 by the first move. However, he can get a pile of 30 stones (at S = 20, he increases the number of stones by 10; at 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, and 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 there are 38 stones in the pile, Vova will increase the number of stones by 10 and you play on your first move. The situation, when there are 29 stones in a pile, is discussed in paragraph 2. In this situation, the player who will move (now it is Vova) wins with his second move.

The table shows the tree of possible games for the described strategy of Vova. The final positions (Vova wins them) are underlined. In the figure, the same tree is shown graphically (both ways of representing the tree are acceptable).

Two players, Petya and Vanya, are playing the next game. In front of them are two piles of stones, in the first of which there are 2, and in the second - 3 stones. Each game-ro-ka has no-ogran-no-chen-but a lot of stones. Players walk by eye-re-di, the first move is de-la-et Petya. The move consists in the fact that the player either am-and-was the number of stones in some pile, or adds 4 stones to some pile. The game is completed at the moment when the total number of stones in two piles becomes at least 31. If at the moment of completion of the game the total the number of stones in two piles is at least 40, then Petya played, in the opposite case - Vanya. Who are you-ig-ry-va-et in the absence of an error-boch-noy game of both games-ro-kov? What should be the first move of you-ig-ry-va-yu-sche-go-ro-ka? Justify the answer.

Solution.

Vanya wins.

To prove it, consider an incomplete game tree, designed as 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 moves for the first player. It shows that for any move of the first player, the second has a move that leads to victory.

Two players, Petya and Vasya, play the following game. In front of them are two piles of stones, the first of which has 2, and the second - 1 stone. Each player has an unlimited number of stones. Players move in turn, Petya goes first. The move consists in the fact 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 turn there are at least 24 stones in one of the piles. Who wins when playing flawlessly? What should be the first move of the winning player?

Justify the 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 as 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 can be seen from it that with any of his answers, Petya has a move that leads to victory.

The game ends when 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 heap, 1 ≤ S ≤ 100.

A player is said to have a winning strategy if he can win for any of the 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 opponent's play.

Complete the following tasks. In all cases, justify your answer.

1. a) For what values of the number S can Petya win on the first move? Specify all such values and Petya's winning move.

b) Indicate a value of S for which Petya cannot win in one move, but for any Petya's move, Vanya can win with his first move. Describe Vanya's winning strategy.

2. Indicate two values of S for which Petya has a winning strategy, and Petya cannot win on the first move, but Petya can win on his second move regardless of how Vanya moves. For the indicated values of S, describe Petya's winning strategy.

3. Indicate a value of S for which Vanya has a winning strategy that allows him to win on the first or second move for any game by Petya, and at the same time Vanya does not have a strategy that will allow him to win on 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 figure or a table. For each edge of the tree, indicate who makes the move, for each node, the number of stones in position.

Solution.

1. a) Petya can win if S = 21, ..., 100. For smaller values of S, one cannot get a pile containing more than 100 stones in one move. It is enough for Petya to increase the number of stones by 5 times. With S 1. b) Vanya can win on 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 by 5 times and wins in one move.

2. Possible values of S: 4, 19. In these cases, Petya obviously cannot win by the first move. However, he can get a pile of 20 stones (with S = 4, he increases the number of stones by 5; with S = 19, he adds 1 stone). This position is discussed in paragraph 1 b). In it, the player who will move (now this is Vanya) cannot win, and his opponent (that is, Petya) will win on the 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 by 5 times and win on his first move. The situation, when there are 19 stones in a pile, is discussed in paragraph 2. In this situation, the player who will move (now it is Vanya) wins with his second move.

The table shows the tree of possible games for Vanya's described strategy. The final positions (Vanya wins them) are underlined. In the figure, the same tree is shown graphically (both representations are acceptable).

Take the test for these tasks

We open a subscription to interactive simulators for preparing for the USE 2016 in computer science

Anyone with a Visa, MasterCard, Yandes.Money wallet, and even a positive balance on their cell phone, can order 60 unique interactive animations to prepare for the Unified State Exam 2016 in computer science without getting up from their computer

Simulator for task No. 26 of the demo version of the USE 2015
in Informatics and ICT using the "Hills and Holes" method

The simplest solution to problem 26 or old C3
in informatics and ICT using the visual method "Hills and Holes"

An example of solving the problem in the case of an increase in stones in a pile in two ways "+1" and "*2"

Two players, Petya and Vanya, play the following game. There is a pile of stones in front of the players. Players move in turn, Petya makes the first move. In one move, the player can add one stone to the pile or double the number of stones in the pile. 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 22. The winner is the player who made the last move, that is, the first to receive a pile containing 22 or more stones.
At the initial moment, there were S stones in the heap, 1<= S <=21. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Complete the following tasks. In all cases, justify your answer.

1. a) Indicate all such values of the number S for which Petya can win in one move. Justify that all required values of S are found, and indicate the winning move for each specified value of S.
b) Indicate a value of S for which Petya cannot win in one move, but for any Petya's move, Vanya can win with his first move. Describe Vanya's winning strategy.

2. Indicate two such values of S for which Petya has a winning strategy, and
– Petya cannot win in one move, and
– Petya can win with his second move, no matter how Vanya moves.
For each given value of S, describe Petya's winning strategy.

3. Specify the value of S, at which:
– Vanya has a winning strategy that allows him to win on the first or second move in any Petya’s game, and
– Vanya does not have a strategy that will allow him to win on 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 (in the form of a figure or a table). On the edges of the tree indicate who makes the move, at the nodes - the number of stones in the pile.

Question 1a.
By the reverse move from the "victory" we determine the boundaries of the initial winning position: 22 – 1 = 21 And 22/2 = 11
For any number lying within the boundaries of this range, the following entry is true max0*2>= 22 or max0*2 > 21 (circle this range from above and denote it as max0, which would mean the initial winning position or win in one move)

1a) Petya wins on the first move with 11<= S <= 21. Для этого достаточно число камней в куче увеличить вдвое и их всегда получится более 21.

Question 1b. To answer this question, you need to find positions, we will conditionally call them min0 , from which all possible moves lead to the initial winning position, marked by us as max0 . In reverse, we determine the “suspected” positions on min0 :
11/2=? is not completely divided, therefore, there is no such position. Remains only S= 11-1=10
(but for now this is just a guess)min0 , so we draw "pit" two features, which will mean - do not forget about the existence of 2 possible moves that will need to be checked!)

We check the assumption for S = 10 on min0. This check will be the answer. to question 1b
With S = 10, Petya has 2 moves that he cannot win in one move, but with any move by Petya, Vanya can win with his first move:
Any Petya's move "10+1=11" or 10*2=20 leads to the initial winning position of Vanya, who, having doubled the number of stones in the pile, gets 22 or 40, which is more than 21 and Van will win
Therefore, we circle the position S = 10 from below with a solid line ( draw a hole) - min0 (initial loss or loss for the 1st move):

Answer to question 1b. can be like this: With S = 10, Petya has 2 moves that he cannot win, but for any move by Petya, Vanya can win with his first move. Any Petya's move "10+1=11" or "10*2=20" leads to the initial winning position of Vanya, who, by doubling the number of stones in the pile, gets 22 or 40, which is more than 21 and Vanya wins

Question 2. In order for Petya to win on the second move, i.e. was in position max0 , after Vanya's move, he needs his first move " put Vanya in a hole". It is clear that such positions can be two, the values of which we find in reverse and must be checked ...
First suspicious position "10-1=9"

S=9. Let's check this position for guaranteed victory!
If Petya had played giveaway, he would have made a move "9 * 2 \u003d 18", but he needs to win, so we discard this move. Remains only "9+1 = 10", Ivanya is in "pit" - which leads Petya to win on the second move, regardless of how Vanya goes!

The second "suspicious position" 10/2 = 5

S=5. Let's check this position for guaranteed victory! move "5+1=6", drags out the game, so we don’t consider it (discard)
Remains only "5*2=10", Ivanya is in "pit" - which leads Petya to win on the second move, regardless of how Vanya goes!

Answer 2 could be:

With S = 5 and 9, Petya cannot win on the first move, but he can win on the second move, and for this it is enough for him to make the move “5*2 = 10” from the position S = 5, thereby sending Vanya to the initial losing position or from the position S = 9 send him to the same position with the move "9+1=10"

Question 3. Vanya must win, therefore, he must be on top max0, this means that Petya must certainly be in min0, where to "plant" Vanya from max1, it remains to find such positions from which Petya would unambiguously fall into max1
We find "suspicious" positions that can lead Petya to max1 with the same backtracking:
9-1=8
9/2=? 9 is not divisible by 2 - disappears
5-1=4
5/2=? 5 by 2 is not divisible - disappears
We find that such "suspicious" There are only two positions, but they still need to be checked!

S=8. Let's check this position to see if Petya is guaranteed to lose!
Petya's move is 8+1=9 and Vanya wins on the second move
Petya's move 8*2=16 and Vanya wins on the first move
S=4. Let's check this position to see if Petya is guaranteed to lose!
Petya's move is 4+1=5 and he would have lost, but from this position Petya's move 4*2=8 is beneficial, thus Vanya falls into the "pit" and loses. But we need to find Vanya's winning strategy, so we exclude the position S=4 from the contenders and get the final "picture":

3. In position S = 8 – Vanya does not have a strategy that will allow him to win on the first move, since his victory depends on Petya’s move, so Vanya has a strategy to win either on the first or second move: If Petya chooses the move “+1” , there are 9 stones in the pile and Vanya wins on the 2nd move (see the answer to question 2). If Petya chooses the move "*2", Vanya wins by the first move, doubling the number of stones in the pile.

The figure we obtained above can be easily redrawn into a game tree, after marking losing moves with red lines (thick line - " short stroke" or " +1 ", and thin -" long" or " *2 ”) and green - winning. (red thick lines can be drawn with humps up, which will coincide with the direction of the "short" branches of the game tree)

The final strategic picture of Petya's win may look like this:

Other methods for solving problems of this type can be found here -

Informatics exam 26 word assignment. Game theory. Finding a winning strategy

Exercise 1.

Task 2

Task 3

Game theory. Finding a winning strategy

Solving 26 USE tasks in computer science

Task 26

Simulator for task No. 26 of the demo version of the USE 2015 in Informatics and ICT using the "Hills and Holes" method

The simplest solution to problem 26 or old C3 in informatics and ICT using the visual method "Hills and Holes"

An example of solving the problem in the case of an increase in stones in a pile in two ways "+1" and "*2"

Simulator for task No. 26 of the demo version of the USE 2015
in Informatics and ICT using the "Hills and Holes" method

The simplest solution to problem 26 or old C3
in informatics and ICT using the visual method "Hills and Holes"