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

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

Задание 19.

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

Задание 20.

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

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

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

Задание 21

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

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

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

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

39. 
    (А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 25. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 25 или больше камней.
    

В начальный момент в куче было S камней, 1 ≤ S ≤ 24.

40. 
    (А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу три камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 18 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 33. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 33 или больше камней.
    

В начальный момент в куче было S камней, 1 ≤ S ≤ 32.

41. 
    (А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в три раза. Например, имея кучу из 10 камней, за один ход можно получить кучу из 12 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 50. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 50 или больше камней.
    

В начальный момент в куче было S камней, 1 ≤ S ≤ 49.

42. 
    (А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня, добавить в кучу три камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 17, 18 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 30. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 30 или больше камней.
    

В начальный момент в куче было S камней, 1 ≤ S ≤ 29.

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

Задание 19.

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

Задание 20.

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

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

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

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

Задание 21

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задание 19.

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

Задание 20.

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

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

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

Задание 21

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

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

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

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

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

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

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

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

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

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

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

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 36. Если при этом в куче оказалось не более 60 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. В начальный момент в куче было S камней, 1 ≤ S ≤ 35.

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

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

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

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 43. Если при этом в куче оказалось не более 72 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. В начальный момент в куче было S камней, 1 ≤ S ≤ 42.

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

Задание 19.

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

Задание 20.

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

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

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

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

Задание 21

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

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

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

49. 
    (А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из одной из куч один камень или уменьшить количество камней в куче в два раза (если количество камней в куче нечётно, остаётся на 1 камень больше, чем убирается). Например, пусть в одной куче 6, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (5, 9), (3, 9), (6, 8), (6, 5). Игра завершается в тот момент, когда суммарное количество камней в кучах становится не более 20. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 20 или меньше камней. В начальный момент в первой куче было 10 камней, во второй куче – S камней, S > 10.
    
50. 
    (А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из одной из куч один камень или уменьшить количество камней в куче в два раза (если количество камней в куче нечётно, остаётся на 1 камень больше, чем убирается). Например, пусть в одной куче 6, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (5, 9), (3, 9), (6, 8), (6, 5). Игра завершается в тот момент, когда суммарное количество камней в кучах становится не более 30. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 30 или меньше камней. В начальный момент в первой куче было 18 камней, во второй куче – S камней, S > 12.
    
51. 
    (А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из одной из куч один камень или уменьшить количество камней в куче в два раза (если количество камней в куче нечётно, остаётся на 1 камень больше, чем убирается). Например, пусть в одной куче 6, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (5, 9), (3, 9), (6, 8), (6, 5). Игра завершается в тот момент, когда суммарное количество камней в кучах становится не более 32. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 32 или меньше камней. В начальный момент в первой куче было 10 камней, во второй куче – S камней, S > 22.
    
52. 
    (Е. Джобс) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
    

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

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

Например, имея кучу из 10 камней, за один ход можно получить кучу из 110 или 20 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 1000. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 1000 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 999.

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

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

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

53. 
    (Д. Ф. Муфаззалов, г. Уфа) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча, состоящая из S конфет. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может съесть не более пяти, но не менее одной конфеты или съесть половину конфет, если число конфет четное. Съесть можно только целое количество конфет.
    

Игра завершается в тот момент, когда в куче останется менее десяти конфет. Победителем считается игрок, который сделал последний ход.

Задание 19. Укажите значение S, при которых Ваня выиграет первым ходом.

Задание 20. Укажите минимальное и максимальное S, при которых Петя не может выиграть первым ходом, но может выиграть вторым ходом при любом ходе Вани.

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

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

Задание 19.

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

Задание 20.

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

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

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

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

Задание 21

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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