Теория игр. Поиск выигрышной стратегии

• Название: Теория игр. Поиск выигрышной стратегии
• Дата: 23.03.2022
• Размер: 0.68 Mb.
• Имя файла: ege1921.doc
• Тип: Документы; #410484
• страница: 6 из 6

Задание 19. Сколько существует пар (K; S), таких что Ваня выигрывает первым ходом при любой игре Пети?

Задание 20. При K=6, найдите минимальное и максимальное значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Задание 21. Сколько существует пар (K; S), при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

63. 
    (А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в любую кучу один камень или увеличить количество камней в первой куче в два раза или увеличить количество камней во второй куче в три раза. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 30, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было K≥1 камней, а во второй – S≥1 камней, K+S ≤ 29. Ответьте на следующие вопросы:
    

Задание 19. Сколько существует пар (K; S), таких что Ваня выигрывает первым ходом при любой игре Пети?

Задание 20. При S=7, найдите минимальное и максимальное значение K, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Задание 21. При K=1 найдите такое значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

64. 
    (А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в любую кучу два камня или увеличить количество камней в любой куче в три раза. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 45, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было K≥1 камней, а во второй – S≥1 камней, K+S ≤ 43.
    

Ответьте на следующие вопросы:

Задание 19. Сколько существует пар (K; S), таких что Ваня выигрывает первым ходом при любой игре Пети?

Задание 20. При K=4, найдите минимальное и максимальное значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Задание 21. При K=13 найдите такое значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

65. 
    (А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из кучи один камень или уменьшить количество камней в любой куче в два раза (если количество камней нечётно, то остаётся на один камень меньше, чем убирается). Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не более 18, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было K≥1 камней, а во второй – S≥1 камней, S+K ≥ 19.
    

Ответьте на следующие вопросы:

Задание 19. Известно, что из начальной позиции (M; M) Ваня выигрывает первым ходом при любой игре Пети. При каком значении M это возможно?

Задание 20. При K=13, найдите минимальное и максимальное значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Задание 21. При каком минимальном значении N для начальной пары (N;N) одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Вопросы 19-21 к следующим задачам:

Задание 19.

Известно, что Ваня выиграл своим первым ходом после первого хода Пети. Назовите минимальное значение S, при котором это возможно.

Задание 20.

Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Задание 21

Найдите значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

66. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в любую кучу один камень;

б) добавить в любую кучу столько камней, сколько их в данный момент в другой куче.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 81, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 7 камней, а во второй – S камней, 1 ≤ S ≤ 73.

67. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в любую кучу один камень;

б) добавить в любую кучу столько камней, сколько их в данный момент в другой куче.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 69, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 7 камней, а во второй – S камней, 1 ≤ S ≤ 61.

68. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в любую кучу один камень;

б) добавить в любую кучу столько камней, сколько их в данный момент в другой куче.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 58, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 6 камней, а во второй – S камней, 1 ≤ S ≤ 51.

69. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в любую кучу один камень;

б) добавить в любую кучу столько камней, сколько их в данный момент в другой куче.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 64, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 6 камней, а во второй – S камней, 1 ≤ S ≤ 57.

70. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в любую кучу один камень;

б) добавить в любую кучу столько камней, сколько их в данный момент в другой куче.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 62, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 8 камней, а во второй – S камней, 1 ≤ S ≤ 53.

71. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в любую кучу один камень;

б) добавить в любую кучу столько камней, сколько их в данный момент в другой куче.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 68, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 8 камней, а во второй – S камней, 1 ≤ S ≤ 59.

72. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в любую кучу один камень;

б) добавить в любую кучу столько камней, сколько их в данный момент в другой куче.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 80, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 8 камней, а во второй – S камней, 1 ≤ S ≤ 71.

73. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в любую кучу один камень;

б) добавить в любую кучу столько камней, сколько их в данный момент в другой куче.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 73, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 9 камней, а во второй – S камней, 1 ≤ S ≤ 63.

74. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в любую кучу один камень;

б) добавить в любую кучу столько камней, сколько их в данный момент в другой куче.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 79, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 9 камней, а во второй – S камней, 1 ≤ S ≤ 69.

Вопросы 19-21 к следующим задачам:

Задание 19.

Известно, что Ваня выиграл своим первым ходом после первого хода Пети. Назовите минимальное значение S, при котором это возможно.

Задание 20.

Определите, сколько существует таких значений S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Задание 21

Укажите максимальное значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть при любой игре Пети.

75. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в любую кучу один камень;

б) увеличить количество камней в куче в три раза.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 70, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 6 камней, а во второй – S камней, 1 ≤ S ≤ 63.

76. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в любую кучу один камень;

б) увеличить количество камней в куче в три раза.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 81, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 7 камней, а во второй – S камней, 1 ≤ S ≤ 73.

77. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в любую кучу один камень;

б) увеличить количество камней в куче в три раза.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 90, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 9 камней, а во второй – S камней, 1 ≤ S ≤ 80.

78. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в любую кучу один камень;

б) увеличить количество камней в куче в три раза.

Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 99, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 8 камней, а во второй – S камней, 1 ≤ S ≤ 90.

Вопросы 19-21 к следующим задачам:

Задание 19.

Известно, что Ваня выиграл своим первым ходом после первого хода Пети. Назовите минимальное значение S, при котором это возможно.

Задание 20.

Определите, два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Задание 21

Найдите значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

79. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в кучу один камень;

б) увеличить количество камней в куче в два раза.

Игра завершается в тот момент, когда количество камней в куче становится не менее 20. Если при этом в куче оказалось не более 30 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 17 камней и Петя удвоит количество камней в куче, то игра закончится, и победителем будет Ваня. В начальный момент в куче было S камней, 1 ≤ S ≤ 19.

80. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в кучу один камень;

б) увеличить количество камней в куче в два раза.

Игра завершается в тот момент, когда количество камней в куче становится не менее 25. Если при этом в куче оказалось не более 45 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 23 камня и Петя удвоит количество камней в куче, то игра закончится, и победителем будет Ваня. В начальный момент в куче было S камней, 1 ≤ S ≤ 24.

81. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в кучу один камень;

б) увеличить количество камней в куче в два раза.

Игра завершается в тот момент, когда количество камней в куче становится не менее 30. Если при этом в куче оказалось не более 45 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 27 камней и Петя удвоит количество камней в куче, то игра закончится, и победителем будет Ваня. В начальный момент в куче было S камней, 1 ≤ S ≤ 29.

82. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в кучу один камень;

б) увеличить количество камней в куче в два раза.

Игра завершается в тот момент, когда количество камней в куче становится не менее 50. Если при этом в куче оказалось не более 70 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 40 камней и Петя удвоит количество камней в куче, то игра закончится, и победителем будет Ваня. В начальный момент в куче было S камней, 1 ≤ S ≤ 49.

83. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в кучу один камень;

б) увеличить количество камней в куче в три раза.

Игра завершается в тот момент, когда количество камней в куче становится не менее 56. Если при этом в куче оказалось не более 80 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 45 камней и Петя удвоит количество камней в куче, то игра закончится, и победителем будет Ваня. В начальный момент в куче было S камней, 1 ≤ S ≤ 55.

84. 
    Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) добавить в кучу один камень;

б) увеличить количество камней в куче в три раза.

Игра завершается в тот момент, когда количество камней в куче становится не менее 65. Если при этом в куче оказалось не более 100 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 55 камней и Петя удвоит количество камней в куче, то игра закончится, и победителем будет Ваня. В начальный момент в куче было S камней, 1 ≤ S ≤ 64.

85. 
    (А. Богданов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит одна куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

а) убрать из кучи половину камней, если количество камней в куче делится на 2; иначе убрать из кучи два камня;

б) убрать из кучи две трети камней, если количество камней в куче делится на 3; иначе убрать из кучи три камня.

Например, пусть в куче 10 камней, тогда можно убрать половину или только три камня. А если в куче 12 камней, то можно убрать половину или две трети камней. Игра завершается в тот момент, когда в куче останется ровно 1 камень. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет ровно 1 камень. В начальный момент в куче было S камней, 2 ≤ S ≤ 37.

Задание 19.

Найдите максимальное значение S, когда Петя мог выиграть первым ходом, но ошибся, и Ваня выиграл.

Задание 20.

Найдите минимальное и максимальное значение S, при котором Петя выигрывает вторым ходом при любом ходе Вани.

Задание 21

Найдите минимальное значение S, при котором Петя может выбрать, каким ходом выиграет Ваня.

86. 
    (Е. Джобс) Два игрока, Петя и Ваня, играют в следующую игру. У игроков есть табличка, на которой записана пара неотрицательных целых чисел. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может заменить любое число на сумму обоих чисел. Так, например, если перед ходом игрока была позиция (3, 5), то после его хода будет позиция (8, 5) или (3, 8). Игра завершается в тот момент, когда сумма чисел пары становится не менее 45, побеждает игрок, сделавший последний ход.
    

Задание 19.

Известно, что игра началась в позиции (7, S), при этом Ваня одержал победу после неудачного хода Пети. Укажите минимальное значение S, при котором это возможно.

Задание 20.

Найдите значения S, при которых Петя при правильной игре гарантированно выигрывает своим вторым ходом из позиции (6, S). В качестве ответа укажите сначала минимальное, затем максимальное значение.

Задание 21

Известно, что при игре из позиции (S, S) Ваня гарантированно выигрывает своим вторым ходом при любой игре Пети. Найдите минимальное значение S, при котором это возможно.

87. 
    (А. Богданов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит три кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч 3, 13 или 23 камня. Игра завершается в тот момент, когда в сумме в кучах будет не менее 73 камней. Победителем считается игрок, сделавший последний ход. В начальный момент в кучах было (2, S, 2S) камней, 1 ≤ S ≤ 23.
    

Задание 19.

При некотором значении S Ваня одержал победу свои первым ходом после неудачного хода Пети. Укажите минимальное значение S, при котором это возможно.

Задание 20.

Найдите минимальное и максимальное значения S, при которых Петя выигрывает вторым ходом при любом ходе Вани.

Задание 21

Найдите два значения S, при которых выигрышная стратегия есть у Вани, но Петя может выбрать, каким ходом выиграет Ваня – первым или вторым.

88. 
    (А. Богданов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч 1 или 2 камня. Игра завершается в тот момент, когда в сумме в кучах будет 13 камней. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 3 камня, во второй – S камней, 1 ≤ S ≤ 9.
    

Задание 19.

Петя мог выиграть первым ходом, но сделал неудачный ход и Ваня выиграл. При каком минимальном значении S это возможно?

Задание 20.

Найдите минимальное и максимальное значения S, при которых Петя выигрывает вторым ходом при любом ходе Вани.

Задание 21

Найдите значение S, при котором Ваня выигрывает вторым ходом при любых ходах Пети.

http://kpolyakov.spb.ru