Тема 19. Теория игр

19.01 Перекладывание камней одна куча

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела теория игр

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 41#59176Максимум баллов за задание: 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или пять камней или увеличить количество камней в куче в три раза. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 49. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 49 или больше камней. В начальный момент в куче было S камней, $1 ≤ S ≤ 48$ .

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

Показать ответ и решение

Решение руками

Для начала определим значения, при которых Петя побеждает первым ходом. Максимальный ход доступный нам в партии это $∗3$ . Минимальное значение отрезка значений, в которых Петя побеждает первым ходом равняется: $49 = 16,33.. 3$ (округляем в большую сторону) = $17$

Получается, что в отрезке [17;48] Петя выигрывает своим первым ходом. Теперь определим значение, в котором Ваня побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанный отрезок – это значение, в котором Ваня выигрывает своим первым ходом. Распишем значение и стратегии, при которых Ваня побеждает первым ходом:

$S = 15$ . Петя может увеличить количество камней до $17$ , $20$ или $45$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

$S = 16$ . Петя может увеличить количество камней до $18$ , $21$ или $48$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

В ответ нужно указать минимальное значение S. Ответ: $15$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 49: # если камней в куче стало больше 48
        return 0 # прекращаем игру
    moves = [game(first_heap+2),game(first_heap+5),game(first_heap*3)] # расписываем ходы доступные нам в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,49):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)
        break

Ответ: 15

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 42#59179Максимум баллов за задание: 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу три камня или увеличить количество камней в куче в два раза. Например, имея кучу из 25 камней, за один ход можно получить кучу из 28 или 50 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 57. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 57 или больше камней. В начальный момент в куче было S камней, $1 ≤ S ≤ 56$ .

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

Показать ответ и решение

Решение руками

Максимальный ход, который мы имеем в игре это $∗ 2$ , это значит, что промежуток, в котором игрок выигрывает в один ход располагается от $29$ до $56$ .

Значит, нам нужно найти минимальное значение, при котором количество камней в куче после хода Пети будет находиться в промежутке, объявленном в предыдущем предложении. Это значение будет равняться $26$ .

Программное решение

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 57: # если камней в куче стало больше 56
        return 0 # прекращаем игру
    moves = [game(first_heap+3),game(first_heap*2)] # расписываем ходы доступные нам в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,57):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
       print(i)
       break

Ответ: 26

Ошибка.
Попробуйте повторить позже

Задача 43#59597Максимум баллов за задание: 1

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

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

Показать ответ и решение

Решение руками

Максимальный ход доступный нам в партии это $∗3$ . Определим отрезок, в котором игра заканчивается за один ход. Минимальное значение отрезка равняется: $40 --= 13,33.. 3$ (округляем в большую сторону) = $14$

Получается, что в отрезке [14;39] игра заканчивается в один ход. Если значение S после первого хода Пети не находится в данном отрезке, то Ваня специально совершит такой ход, чтобы после него значение S находилось в данном отрезке для того чтобы Петя смог завершить партию следующим ходом. А если значение S после первого хода уже находится в данном отрезке, то Ваня специально совершить такой ход, чтобы не завершить партию, а просто передать очередь хода Пете для того чтобы он завершил партию. Распишем значения и стратегии, при которых Петя не может победить за один ход, но может победить вторым ходом после неудачного хода Вани:

$S = 1$ . Петя увеличит количество камней до $7$ , а Ваня увеличит количество камней до $21$ . Пете не составит труда завершить партию следующим ходом.

$S = 2$ . Петя увеличит количество камней до $8$ , а Ваня увеличит количество камней до $14$ или $24$ . Пете не составит труда завершить партию следующим ходом.

$S = 3$ . Петя увеличит количество камней до $9$ , а Ваня увеличит количество камней до $15$ или $27$ . Пете не составит труда завершить партию следующим ходом.

$S = 4$ . Петя увеличит количество камней до $5$ или $10$ или $12$ , а Ваня увеличит количество камней до $15$ или $16$ , $30$ или $18$ , $36$ . Пете не составит труда завершить партию следующим ходом.

$S = 5$ . Петя увеличит количество камней до $6$ или $11$ или $15$ , а Ваня увеличит количество камней до $18$ или $17$ , $33$ или $16$ , $21$ .Пете не составит труда завершить партию следующим ходом.

$S = 6$ . Петя увеличит количество камней до $7$ или $12$ или $18$ , а Ваня увеличит количество камней до $21$ или $18$ , $36$ или $19$ , $24$ . Пете не составит труда завершить партию следующим ходом.

$S = 7$ . Петя увеличит количество камней до $8$ или $13$ или $21$ , а Ваня увеличит количество камней до $14$ , $24$ или $14$ , $19$ , $39$ или $22$ , $27$ . Пете не составит труда завершить партию следующим ходом.

$S = 8$ . Петя увеличит количество камней до $9$ или $14$ или $24$ , а Ваня увеличит количество камней до $15$ , $27$ или $15$ , $20$ или $25$ , $30$ . Пете не составит труда завершить партию следующим ходом.

$S = 9$ . Петя увеличит количество камней до $10$ или $15$ или $27$ , а Ваня увеличит количество камней до $16$ , $30$ или $16$ , $21$ или $28$ , $33$ . Пете не составит труда завершить партию следующим ходом.

$S = 10$ . Петя увеличит количество камней до $11$ или $16$ или $30$ , а Ваня увеличит количество камней до $17$ , $33$ или $17$ , $22$ или $31$ , $36$ . Пете не составит труда завершить партию следующим ходом.

$S = 11$ . Петя увеличит количество камней до $12$ или $17$ или $33$ , а Ваня увеличит количество камней до $18$ , $36$ или $18$ , $23$ или $34$ , $39$ . Пете не составит труда завершить партию следующим ходом.

$S = 12$ . Петя увеличит количество камней до $13$ или $18$ или $36$ , а Ваня увеличит количество камней до $19$ , $39$ или $19$ , $24$ или $37$ . Пете не составит труда завершить партию следующим ходом.

$S = 13$ . Петя увеличит количество камней до $14$ или $19$ , а Ваня увеличит количество камней до $15$ , $20$ или $20$ , $25$ . Пете не составит труда завершить партию следующим ходом.

В ответ нужно указать количество значений S. Ответ: $13$

Программное решение

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 40: # если камней в куче стало больше 39
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap+6),game(first_heap*3)] # расписываем ходы доступные нам в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)
count = 0
for i in range(1,40):
    # проверка, что Петя не может выиграть за один ход
    # проверка, что Петя может выиграть вторым ходом после неудачного хода Вани. Расписываем всевозможные первые два хода и проверяем можно ли после них завершить игру за один ход.
    if game(i) != 1 and (game(i+1+1) == 1 or game(i+1+6) == 1 or game(i+1*3) == 1 or game(i+6+1) == 1 or game(i+6+6) == 1 or game(i+6*3) == 1 or game(i*3+1) == 1 or game(i*3+6) == 1 or game(i*3*3) == 1):
        count += 1
print(count)

Ответ: 13

Ошибка.
Попробуйте повторить позже

Задача 44#61314Максимум баллов за задание: 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу три камня или пять камней или увеличить количество камней в куче в два раза. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 67. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 67 или больше камней. В начальный момент в куче было S камней, $1 ≤ S ≤ 66$ .

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

Показать ответ и решение

Решение руками

Для начала определим значения, при которых Петя побеждает первым ходом. Максимальный ход доступный нам в партии это $∗2$ . Минимальное значение отрезка значений, в которых Петя побеждает первым ходом равняется: $67 = 33,5 2$ (округляем в большую сторону) = $34$

Получается, что в отрезке [34;66] Петя выигрывает своим первым ходом. Теперь определим значение, в котором Ваня побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанный отрезок – это значение, в котором Ваня выигрывает своим первым ходом. Распишем значение и стратегии, при которых Ваня побеждает первым ходом:

$S = 31$ . Петя может увеличить количество камней до $34$ , $36$ или $62$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

$S = 32$ . Петя может увеличить количество камней до $35$ , $37$ или $64$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

$S = 33$ . Петя может увеличить количество камней до $36$ , $38$ или $66$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

В ответ нужно указать минимальное значение S. Ответ: $31$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 67: # если камней в куче стало больше 66
        return 0 # прекращаем игру
    moves = [game(first_heap+3),game(first_heap+5),game(first_heap*2)] # расписываем ходы доступные нам в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)
count = 0
for i in range(1,67):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)
        break

Ответ: 31

Ошибка.
Попробуйте повторить позже

Задача 45#61317Максимум баллов за задание: 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу четыре камня или увеличить количество камней в куче в три раза. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 72. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 72 или больше камней. В начальный момент в куче было S камней, $1 ≤ S ≤ 71$ .

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

Показать ответ и решение

Решение руками

Получается, что в отрезке [24;71] Петя выигрывает своим первым ходом. Теперь определим значение, в котором Ваня побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанный отрезок – это значение, в котором Ваня выигрывает своим первым ходом. Распишем значение и стратегии, при которых Ваня побеждает первым ходом:

$S = 20$ . Петя может увеличить количество камней до $24$ , $60$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

$S = 21$ . Петя может увеличить количество камней до $25$ , $63$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

$S = 22$ . Петя может увеличить количество камней до $26$ , $66$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

$S = 23$ . Петя может увеличить количество камней до $27$ , $69$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

В ответ нужно указать минимальное значение S. Ответ: $20$

Программное решение

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 72: # если камней в куче стало больше 71
        return 0 # прекращаем игру
    moves = [game(first_heap+4),game(first_heap*3)] # расписываем ходы доступные нам в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,72):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)
        break

Ответ: 20

Ошибка.
Попробуйте повторить позже

Задача 46#61320Максимум баллов за задание: 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу шесть камней или увеличить количество камней в куче в два раза. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 81. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 81 или больше камней. В начальный момент в куче было S камней, $1 ≤ S ≤ 80$ .

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

Показать ответ и решение

Решение руками

Для начала определим значения, при которых Петя побеждает первым ходом. Максимальный ход доступный нам в партии это $∗2$ . Минимальное значение отрезка значений, в которых Петя побеждает первым ходом равняется: $81 = 40,5 2$ (округляем в большую сторону) = $41$

Получается, что в отрезке [41;40] Петя выигрывает своим первым ходом. Теперь определим значение, в котором Ваня побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанный отрезок – это значение, в котором Ваня выигрывает своим первым ходом. Распишем стратегии ходов у минимального подходящего значения, при которых Ваня побеждает первым ходом:

$S = 35$ . Петя может увеличить количество камней до $41$ или $70$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

Ответ: $35$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 81: # если камней в куче стало больше 80
        return 0 # прекращаем игру
    moves = [game(first_heap+6),game(first_heap*2)] # расписываем ходы доступные нам в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,80):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)
        break

Ответ: 35

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 47#62665Максимум баллов за задание: 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 38. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 38 или больше камней. В начальный момент в куче было S камней, $1 ≤ S ≤ 37$ .

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

Показать ответ и решение

Решение руками

Петя может прибавить в кучу два камня или увеличить кучу в два раза, то есть из начальной кучи $S$ получится куча равная $S + 2$ или куча равная $2S$ . Тогда Ваня, чтобы наверняка выиграть, домножит кучу на $2$ , значит:

({ ({ 2(S +2) ≥ 38 S ≥ 17 ⇒ S ≥ 17 ⇒ S = 17 ( 2 ∗2S ≥ 38 ( S ≥ 10

Программное решение

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 38: # если камней в куче стало больше 37
        return 0 # прекращаем игру
    moves = [game(first_heap+2),game(first_heap*2)] # расписываем ходы доступные нам в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,38):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)
        break

Ответ: 17

Ошибка.
Попробуйте повторить позже

Задача 48#62668Максимум баллов за задание: 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 17 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 47. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 47 или больше камней. В начальный момент в куче было S камней, $1 ≤ S ≤ 46$ .

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

Показать ответ и решение

Решение руками

Петя может прибавить в кучу два камня или увеличить кучу в три раза, то есть из начальной кучи $S$ получится куча равная $S + 2$ или куча равная $3S$ . Тогда Ваня, чтобы наверняка выиграть, домножит кучу на $3$ , значит:

({ ({ 3(S +2) ≥ 47 S ≥ 14 ⇒ S ≥ 14 ⇒ S = 14 ( 3 ∗3S ≥ 47 ( S ≥ 6

Программное решение

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 47: # если камней в куче стало больше 46
        return 0 # прекращаем игру
    moves = [game(first_heap+2),game(first_heap*3)] # расписываем ходы доступные нам в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,47):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)
        break

Ответ: 14

Ошибка.
Попробуйте повторить позже

Задача 49#62671Максимум баллов за задание: 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу четыре камня или увеличить количество камней в куче в два раза. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 55. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 55 или больше камней. В начальный момент в куче было S камней, $1 ≤ S ≤ 54$ .

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

Показать ответ и решение

Решение руками

Петя может прибавить в кучу четыре камня или увеличить кучу в два раза, то есть из начальной кучи S получится куча равная $S + 4$ или куча равная $2S$ . Тогда Ваня, чтобы наверняка выиграть, домножит кучу на $2$ , значит:

({ ({ 2(S +4) ≥ 55 S ≥ 24 ⇒ S ≥ 24 ⇒ S = 24 ( 2 ∗2S ≥ 55 ( S ≥ 14

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 55: # если камней в куче стало больше 54
        return 0 # прекращаем игру
    moves = [game(first_heap+4),game(first_heap*2)] # расписываем ходы доступные нам в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,55):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)
        break

Ответ: 24

Ошибка.
Попробуйте повторить позже

Задача 50#62674Максимум баллов за задание: 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в два раза. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 29 или больше камней. В начальный момент в куче было S камней, $1 ≤ S ≤ 28$ .

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

Показать ответ и решение

Решение руками

Неудачный ход Пети это ход умножить кучу на два, то есть $2S$ . Тогда Ваня, чтобы наверняка выиграть, домножит кучу на $2$ , значит:

$2∗ 2S ≥ 29 → S ≥ 8 → S = 8$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 29: # если камней в куче стало больше 28
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap+2),game(first_heap*2)] # расписываем ходы доступные нам в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,29):
    if game(i+1) == 1 or game(i+2) == 1 or game(i*2) == 1: # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Ответ: 8

Ошибка.
Попробуйте повторить позже

Задача 51#62677Максимум баллов за задание: 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить три или пять камней или увеличить количество камней в куче в три раза. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 61. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 61 или больше камней. В начальный момент в куче было S камней, $1 ≤ S ≤ 60$ .

Показать ответ и решение

Решение руками

Неудачный ход Пети это ход умножить кучу на три, то есть $3S$ . Тогда Ваня, чтобы наверняка выиграть, домножит кучу на $3$ , значит:

$3∗ 3S ≥ 61 → S ≥ 7 → S = 7$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 61: # если камней в куче стало больше 60
        return 0 # прекращаем игру
    moves = [game(first_heap+3),game(first_heap+5),game(first_heap*3)] # расписываем ходы доступные нам в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,61):
    if game(i+3) == 1 or game(i+5) == 1 or game(i*3) == 1: # если после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Ответ: 7

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 52#62834Максимум баллов за задание: 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 1 камень, либо увеличить число камней в куче в 2 или 4 раза. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11, 20 или 40 камней. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 58. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в куче будет 58 или больше камней. В начальный момент в куче было S камней; $1 ≤ S ≤ 57$ .

Показать ответ и решение

Решение руками

Обратим внимание, что в задаче Петя своим первым ходом совершает ошибку, благодаря которой Ваня выигрывает. Так как нас интересует минимальное S, при котором такая ситуация возможна, работаем мы с самым сильным ходом, а именно $∗4$ . Найдем кол-во камней, из которого Ваня мог выиграть: $58 = 14,5 => 15 4$ камней – минимальная позиция (=> диапазон для выигрыша = [15,57]). Такое количество Петя мог «подарить» сопернику любым из своих ходов, но для минимального значения вновь обращаемся к $∗ 4$ : $15 4 = 3,75 => 4$ . Следовательно, самой маленькой кучкой, при которой Петя мог совершить неудачный ход и помочь Ване выиграть, является куча при $S = 4$ . ( $4− > 16− > 64$ )

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 58: # если камней в куче стало больше 57
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap*2),game(first_heap*4)] # расписываем ходы доступные нам в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,58):
    if game(i+1) == 1 or game(i*2) == 1 or game(i*4) == 1: # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Ответ: 4

Ошибка.
Попробуйте повторить позже

Задача 53#63381Максимум баллов за задание: 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу три камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 18 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 46. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 46 или больше камней. В начальный момент в куче было S камней, $1 ≤ S ≤ 45$ .

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

Показать ответ и решение

Решение руками

Получается, что в отрезке [23;45] Петя выигрывает своим первым ходом. Теперь определим значение, в котором Ваня побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанный отрезок – это значение, в котором Ваня выигрывает своим первым ходом. Распишем значение и стратегии, при которых Ваня побеждает первым ходом:

$S = 20$ . Петя может увеличить количество камней до $23$ или $40$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

$S = 21$ . Петя может увеличить количество камней до $24$ или $42$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

$S = 22$ . Петя может увеличить количество камней до $25$ или $44$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

В ответ нужно указать минимальное значение S. Ответ: $20$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 46: # если камней в куче стало больше 45
        return 0 # прекращаем игру
    moves = [game(first_heap+3),game(first_heap*2)] # расписываем ходы доступные нам в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,46):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)
        break

Ответ: 20

Ошибка.
Попробуйте повторить позже

Задача 54#64069Максимум баллов за задание: 1

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

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

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

Показать ответ и решение

Решение руками

Для начала определим значения, при которых Петя побеждает первым ходом. Максимальный ход доступный нам в партии это $∗2$ Минимальное значение отрезка значений, в которых Петя побеждает первым ходом равняется: $80 = 40 2$

Получается, что в отрезке [40;79] Петя выигрывает своим первым ходом. Теперь определим значение, в котором Ваня побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанный отрезок – это значение, в котором Ваня выигрывает своим первым ходом. Распишем значение и стратегии, при которых Ваня побеждает первым ходом:

$S = 38$ . Петя может увеличить количество камней до $40$ , $41$ или $76$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

$S = 39$ . Петя может увеличить количество камней до $41$ , $42$ или $78$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

В ответ нужно указать минимальное значение S. Ответ: $38$

Решение БУ

from functools import lru_cache


@lru_cache(None)
def f(x):
    if x >= 80:
        return 0
    t = [f(x + 2), f(x + 3), f(x * 2)]
    h = [i for i in t if i <= 0]
    if h:
        return -max(h) + 1
    else:
        return -max(t)


for s in range(1, 79 + 1):
    if f(s) == -1:
        print(s)
        break

Ответ: 38

Ошибка.
Попробуйте повторить позже

Задача 55#72404Максимум баллов за задание: 1

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

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

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

Показать ответ и решение

Решение руками

Определим значение, в котором Ваня побеждает своим первым ходом. Значение, из которого все ходы ведут в отрезок [35; 69] – это значение, в котором Ваня выигрывает своим первым ходом.

Единственное значение $S$ , при котором Ваня выиграет своим первым ходом, является $S = 34$ .

Решение программой

def f(a):
    if a >= 70:return 0
    t = [f(a+1),f(a*2)]
    n= [i for i in t if i <= 0]
    if n:return -max(n) + 1
    return -max(t)
for i in range(1,70):
    if f(i) == -1:
        print(i)

Ответ: 34

Ошибка.
Попробуйте повторить позже

Задача 56#72431Максимум баллов за задание: 1

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

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

Показать ответ и решение

Решение руками

Получается, что в отрезке [40;119] Петя выигрывает своим первым ходом. Теперь определим значение, в котором Ваня побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанный отрезок – это значение, в котором Ваня выигрывает своим первым ходом. Распишем значение и стратегии, при которых Ваня побеждает первым ходом:

$S = 38$ . Петя может увеличить количество камней до $40$ , $41$ или $114$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

$S = 39$ . Петя может увеличить количество камней до $41$ , $42$ или $117$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

В ответ нужно указать минимальное значение S. Ответ: $38$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 120: # если камней в куче стало больше 119
        return 0 # прекращаем игру
    moves = [game(first_heap+2),game(first_heap+3),game(first_heap*3)] # расписываем ходы доступные нам в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,120):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)
        break

Ответ: 38

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 57#72457Максимум баллов за задание: 1

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

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

Показать ответ и решение

Решение руками

Получается, что в отрезке [32;63] Петя выигрывает своим первым ходом. Теперь определим значение, в котором Ваня побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанный отрезок – это значение, в котором Ваня выигрывает своим первым ходом. Распишем значение и стратегии, при которых Ваня побеждает первым ходом:

$S = 31$ . Петя может увеличить количество камней до $32$ или $62$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

Ответ: $31$

Решение программой:
Для решения на Python используем рекурсию с проверкой всех возможных ходов ( $+ 1$ , $× 2$ ), чтобы определить, чья это выигрышная позиция.
Функция возвращает $0$ , если игра уже завершена (камней $≥ 64$ ), положительное число — если при оптимальной игре побеждает текущий игрок, и отрицательное – если побеждает соперник.
Так как первый ход делает Петя, цикл запускается от его лица: если значение функции положительное, выигрвает Пете, а если отрицательное – Ваня. Если функция вернёт $− 1$ - значит Петя гарантированно проиграл первым ходом, а Ваня выиграл. При переборе возможных начальных значений программа выводит $31$ .

# lru_cache позволит сэкономить ресурсы компьютера. Функция будет сохранять прошлые значения функций, а значит не придётся считать из заново.
from functools import lru_cache
@lru_cache(None)
def game(first_heap): # Функция игры
    if first_heap >= 64: # Если камней в куче стало больше 64
        return 0 # Прекращаем игру
    moves = [game(first_heap + 1), game(first_heap * 2)] # Прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # Проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1 # От лица Пети будет выигрыш (положительное число, прибавляем 1, поскольку это будет уже следующий ход)
    else: # Если в данной позиции выигрыш Вани
        return -max(moves) # От лица Пети будет проигрыш (отрицательное число)

for i in range(1, 64): # Переберём возможные значения
    if game(i) == -1: # Если в данной позиции возможен выигрыш Вани первым ходом
        print(i) # Выведем нужное значение

Ответ: 31

Ошибка.
Попробуйте повторить позже

Задача 58#76979Максимум баллов за задание: 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу три камня или увеличить количество камней в 4 раза. Игра завершается в тот момент, когда количество камней куче становится не менее 100. Игрок, который получил 120 и более камней, считается проигравшим. В начальный момент в куче было S камней; $1 ≤ S ≤ 60$ .

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

Показать ответ и решение

Решение руками

Для начала определим значение, начиная с которого мы не можем совершать $∗4$ для того чтобы не проиграть. Это значение равняется: $120 ---= 30 4$ . Начиная с $30$ камней в куче мы не может совершать ход $∗4$ . Определим значения, в которых Петя побеждает своим первым ходом. Минимальное значение равняется: $100 --- = 25 4$ . Получается, что в отрезке значений [25;29] Петя выигрывает первым ходом, совершая ход $∗4$ .

В ответ нужно указать минимальное значение S. Ответ: $25$ .

Программное решение

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 100: # если камней в куче стало больше 99
        return 0 # прекращаем игру
    moves = [] # cписок всех возможных ходов в партии
    # если текущее количество камней в куче, помноженное на 4 больше или равно 120
    if first_heap * 4 >= 120:
        moves = [game(first_heap+3)] # то можем делать только ход +3
    else:
        moves = [game(first_heap+3),game(first_heap*4)] # то можем делать любой ход
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,61):
    # если в данной позиции возможен выигрыш Пети первым ходом
    if game(i) == 1:
        print(i)
        break

Ответ: 25

Ошибка.
Попробуйте повторить позже

Задача 59#76988Максимум баллов за задание: 1

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

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

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

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

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

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

Показать ответ и решение

Решение руками

Для начала определим значение, начиная с которого мы не можем совершать $∗3$ для того чтобы не проиграть. Это значение равняется: $109 ---= 36,(3) 3$ . Округляем в большую сторону - $37$ . Начиная с $37$ камней в куче мы не может совершать ход $∗ 3$ . Определим значения, в которых Петя побеждает своим первым ходом. Минимальное значение равняется: $65 --= 21,(6) 3$ . Округляем в большую сторону - $22$ . Получается, что в отрезке значений [22;36] Петя выигрывает первым ходом, совершая ход $∗3$ .

В ответ нужно указать минимальное значение S. Ответ: $22$ .

Программное решение

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 65: # если камней в куче стало больше 64
        return 0 # прекращаем игру
    moves = [] # cписок всех возможных ходов в партии
    # если текущее количество камней в куче, помноженное на 3 больше или равно 109
    if first_heap * 3 >= 109:
        moves = [game(first_heap+5),game(first_heap+7)] # то можем делать только +5,+7 ходы
    else:
        moves = [game(first_heap+5),game(first_heap+7),game(first_heap*3)] # то можем делать любой ход
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,40):
    # если в данной позиции возможен выигрыш Пети первым ходом
    if game(i) == 1:
        print(i)
        break

Ответ: 22

Ошибка.
Попробуйте повторить позже

Задача 60#78623Максимум баллов за задание: 1

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

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

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

Показать ответ и решение

Решение руками

Для начала определим значения, при которых Петя побеждает первым ходом. Максимальный ход доступный нам в партии это $∗2$ . Минимальное значение отрезка значений, в которых Петя побеждает первым ходом равняется: $47 = 23,5 2$ (округляем в большую сторону) = $24$

Получается, что в отрезке [24;46] Петя выигрывает своим первым ходом. Теперь определим значение, в котором Ваня побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанный отрезок – это значение, в котором Ваня выигрывает своим первым ходом. Распишем значение и стратегии, при которых Ваня побеждает первым ходом:

$S = 22$ . Петя может увеличить количество камней до $24$ , $27$ или $44$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

$S = 23$ . Петя может увеличить количество камней до $25$ , $28$ или $46$ камней. Во всех этих случаях Ване не составит труда завершить партию следующим ходом.

В ответ нужно указать минимальное значение S. Ответ: $22$

Решение БУ

def f(a):
  if a >= 47:  #если камней в куче стало больше 47, то выход из функции
    return 0
  t = [f(a+2), f(a+5), f(a*2)]    #сформировали список ходов
  n = [i for i in t if i <= 0] #записываем отрицательные элементы из t
  if n:  #если n не пустой список
    return -max(n)+1 #получаем положительный выигрышный ход для Пети
  else:
    return -max(t) #получаем отрицательный выигрышный ход для Вани


for i in range(1,47):
    if f(i) == -1:
        print(i)

Ответ: 22