19.01 Перекладывание камней одна куча - Каталог заданий по ЕГЭ

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

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

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

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

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

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

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

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

Максимальный ход доступный нам в партии это $∗3$ . Определим отрезок, в котором игра заканчивается за один ход. Минимальное значение отрезка равняется: $78 --= 26 3$

Получается, что в отрезке [26;77] игра заканчивается в один ход. Минимальное значение, из которого ходом $∗3$ можно попасть в данный отрезок и есть минимальное значение S, из которого Ваня может победить после неудачного хода Пети. Определим данное значение: $26= 8,66 3$ (округляем в большую сторону) = $9$

Ответ: $9$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 78: # если камней в куче стало больше 77
        return 0 # прекращаем игру
    moves = [game(first_heap+1),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,78):
    if game(i+1) == 1 or game(i+5) == 1 or game(i*3) == 1: # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Решение АР

from functools import lru_cache
def moves(h):
    return (h + 1), (h + 5), (h * 3)
@lru_cache(None)
def f(h):
    if h >= 78:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’P1’
    if any(f(x) == ’P1’ for x in moves(h)):
        return ’V1’
for h in range(1, 79):
    if f(h) == ’V1’:
        print(h)
        break

Ответ: 9

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

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

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

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

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

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

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

Получается, что в отрезке [15;57] игра заканчивается в один ход. Минимальное значение, из которого ходом $∗4$ можно попасть в данный отрезок и есть минимальное значение S, из которого Ваня может победить после неудачного хода Пети. Определим данное значение: $15= 3,75 4$ (округляем в большую сторону) = $4$

Ответ: $4$

Решение БУ

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,57):
    if game(i+1) == 1 or game(i*2) == 1 or game(i*4) == 1: # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Решение АР

from functools import lru_cache


def moves(h):
    return h+1, h*2, h*4


@lru_cache(None)
def f(h):
    if h >= 58:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’P1’
    if any(f(x) == ’P1’ for x in moves(h)):
        return ’V1’


for i in range(1, 57):
    if f(i) == ’V1’:
        print(i)
        break

Ответ: 4

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

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

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

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

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

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

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

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

Возьмем $S = 11$ . Тогда Петя может добавить 2 камня и станет 13 камней, либо увеличить кол-во камней в куче в 2 раза и станет 22 камня. И из 13, и из 22 Ваня выигрывает умножением на 2.

Возьмем $S = 12$ . Тогда Петя может добавить 2 камня и станет 14 камней, либо увеличить кол-во камней в куче в 2 раза и станет 24 камня. И из 14, и из 24 Ваня выигрывает умножением на 2.

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 25: # если камней в куче стало больше 24
        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,25):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)

Решение АР

from functools import lru_cache
def moves(h):
    return (h+2), (h*2)
@lru_cache(None)
def game(h):
    if h >= 25:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
for s in range(1, 25):
    if game(s) == ’LOSE1’:
        print(s)

Ответ: 11

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

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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в $2$ раза. Например, имея кучу из $17$ камней, за один ход можно получить кучу из $18$ или $34$ камней. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее $31$ .

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.

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

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

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

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

$2S ≥ 31 ⇒ S = 16$ .

$S + 1 ≥ 31 ⇒ S = 30$ .

$16 < 30$ , значит ответ $16$ .

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 31: # если камней в куче стало больше 30
        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
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

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

Решение АР

from functools import lru_cache


def moves(heap):
    return heap + 1, heap * 2


@lru_cache(None)
def game(heap):
    if heap >= 31:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(1, 31):
    if game(s) == ’P1’:
        print(s)
        break

Ответ: 16

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

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

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

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.

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

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

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

В этой задаче требуется найти позицию , в которой выигрыш Вани первым ходом. Чтобы её найти, давайте сначала найдём позиции, в которых выигрыш Пети первым ходом. Это все позиции при $S ≥ 28$ . Тогда все ходы из позиции $26$ ведут в позиции, где выигрыш Пети первым ходом, а это значит, что позиция $26$ является позицией, где выигрыш Вани первым ходом. Также из позиции $27$ все ходы ведут в выигрыш Пети первым ходом, она тоже подходит, но $26 < 27$ . Ответ $26$ .

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 55: # если камней в куче стало больше 54
        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,55):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)

Решение АР

from functools import lru_cache


def moves(heap):
    return heap + 2, heap * 2


@lru_cache(None)
def game(heap):
    if heap >= 55:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(1, 55):
    if game(s) == ’V1’:
        print(s)
        break

Ответ: 26

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

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

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

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.

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

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

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

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

$(S +1) ⋅3 ≥ 71 ⇒ S ≥ 23$

Также Петя мог утроить количество камней, тогда неравенство будет выглядеть так:

$S ⋅3⋅3 ≥ 71 ⇒ S ≥ 8$

$8 < 23$ , значит ответ $8$ .

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 71: # если камней в куче стало больше 70
        return 0 # прекращаем игру
    moves = [game(first_heap+1),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,71):
    if game(i+1) == 1 or game(i*3) == 1: # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Решение АР

from functools import lru_cache


def moves(heap):
    return heap + 1, heap * 3


@lru_cache(None)
def game(heap):
    if heap >= 71:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif any(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(1, 71):
    if game(s) == ’V1’:
        print(s)
        break

Ответ: 8

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

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

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

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

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

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

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

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

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

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

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

Ответ: $92$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 185: # если камней в куче стало больше 184
        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
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

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

Решение АР

from functools import lru_cache

def m(h):
    return h * 2, h + 1

@lru_cache(None)
def f(h):
    if h >= 185:
        return "END"
    if any(f(x) == "END" for x in m(h)):
        return "P1"
    if all(f(x) == "P1" for x in m(h)):
        return "V1"
for i in range(1, 185):
    if f(i) == "V1":
        print(i)

Ответ: 92

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

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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча маркеров. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один маркер или увеличить количество маркеров в куче в $2$ раза. Например, имея кучу из $17$ маркеров, за один ход можно получить кучу из $18$ или $34$ маркеров. Чтобы делать ходы, у каждого игрока есть неограниченное количество маркеров. Игра завершается в тот момент, когда количество маркеров в куче становится не менее $42$ .

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.

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

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

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

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

Получается, что в отрезке [21;41] Петя выигрывает своим первым ходом.

Ответ: $21$

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

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 42: # если камней в куче стало больше 41
        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
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

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

Альтернативное решение программой

from functools import lru_cache

def moves(h):
    return h + 1, h * 2

@lru_cache(None)
def f(h):
    if (h >= 42):
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’P1’

for s in range(1, 42):
    if f(s) == ’P1’:
        print(s)
        break

Ответ: 21

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

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

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

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

В начальный момент в куче было $1 ≤ S ≤ 24$ . Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

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

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

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

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

Получается, что в отрезке [13;24] Петя выигрывает своим первым ходом.

Ответ: $13$

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

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 25: # если камней в куче стало больше 24
        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
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

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

Альтернативное решение программой

from functools import lru_cache

def moves(h):
    return (h + 1), (h * 2)

@lru_cache(None)
def game(h):
    if h >= 25:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(h)):
        return ’WIN1’

for i in range(1, 25):
    if game(i) == ’WIN1’:
        print(i)
        break

Ответ: 13

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

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

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

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

В начальный момент в куче было $1 ≤ S ≤ 80$ . Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

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

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

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

Максимальный ход доступный нам в партии это $∗3$ . Определим отрезок, в котором игра заканчивается за один ход. Минимальное значение отрезка равняется: $81 --= 27 3$

Получается, что в отрезке [27;80] игра заканчивается в один ход. Минимальное значение, из которого ходом $∗ 3$ можно попасть в данный отрезок и есть минимальное значение S, из которого Ваня может победить после неудачного хода Пети. Определим данное значение: $27 = 9 3$

Ответ: $9$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 81: # если камней в куче стало больше 80
        return 0 # прекращаем игру
    moves = [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,81):
    if game(i+3) == 1 or game(i*3) == 1: # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Решение АР

from functools import lru_cache

def moves(h):
    return (h + 3), (h * 3)

@lru_cache(None)
def game(h):
    if h >= 81:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    elif any(game(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’

for i in range(1, 81):
    if game(i) == ’LOSE1’:
        print(i)
        break

Ответ: 9

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

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

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

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

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

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

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

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

Это значение будет равняться $16$ .

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 53: # если камней в куче стало больше 52
        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,52):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)
        break

Ответ: 16

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

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

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

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

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

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

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

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 64: # если камней в куче стало больше 63
        return 0 # прекращаем игру
    moves = [game(first_heap+1),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,64):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)

Ответ: 21

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

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

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

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

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

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

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

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

Решение БУ

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*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,48):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)
        break

Ответ: 23

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

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

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

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

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

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

Максимальный ход, который мы имеем в игре это $+ 10$ , это значит, что промежуток, в котором игрок выигрывает в один ход располагается от $51$ до $60$ .

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

Ответ: $41$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 61: # если камней в куче стало больше 60
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap+10)] # прописываем ходы возможные в партии
    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,56):
    if game(i+1) == 1 or game(i+10) == 1: # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Ответ: 41

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

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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или три камня или увеличить количество камней в куче в $2$ раза, при этом после каждого хода в куче должно быть четное количество камней. Например, пусть в куче будет $6$ камней. Тогда за один ход можно получить кучу из $12$ камней. Игра завершается в тот момент, когда количество камней в куче становится не менее $88$ .

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.

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

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

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

Для начала определим какие ходы в каких ситуациях мы можем совершать. После каждого хода у нас должно быть обязательно чётное количество камней в куче. Если текущее количество камней чётное, то мы можем совершать только ход $∗2$ , так как чётное * чётное = чётное число. В обратном случае, если текущее количество камней нечётное, то мы можем совершать любой ход, так как нечётное * чётное = чётное число и нечётное + нечётное = чётное число. Определим при каких значениях Петя побеждает своим первым ходом. Максимальный ход, который нам доступен это $∗2$ . Значит, минимальное значение, в котором Петя побеждает первым своим ходом равняется: $88 2 = 44$

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

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

Ответ: $22$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 88: # если камней в куче стало больше 87
        return 0 # прекращаем игру
    moves = [] # cписок всех возможных ходов в партии
    if first_heap % 2 == 0: # если количество камней в куче является чётным
        # то можем сделать только ход *2, так как чётное*чётное = чётное
        moves = [game(first_heap*2)]
    else: # если количество камней в куче является нечётным
        # то можем сделать только любой ход, так как нечётное*чётное = чётное и нечётное + нечётное = чётное
        moves = [game(first_heap * 2),game(first_heap+1),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,88):
    # если в данной позиции возможен выигрыш Ваня первым ходом
    if game(i) == -1:
        print(i)
        break

Решение АР

from functools import lru_cache
def moves(h):
    a = [h * 2]
    if (h + 1) % 2 == 0:
        a += [h + 1]
        a += [h + 3]
    return a
@lru_cache(None)
def f(h):
    if h >= 88:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’P1’
    if all(f(x) == ’P1’ for x in moves(h)):
        return ’V1’
for s in range(1, 88):
    if f(s) == ’V1’:
        print(s)
        break

Ответ: 22

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

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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два или четыре камня либо увеличить количество камней в куче в три раза. Например, из кучи в 10 камней можно получить кучу из 12, 14 либо 30 камней. У каждого игрока есть неограниченное количество камней, чтобы делать ходы. Игра завершается в тот момент, когда количество камней в куче становится не менее 271. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 271 или более камня. В начальный момент в куче было S камней; 1 $≤$ S $≤$ 270. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

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

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

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

Из этого следует, что наибольшее значение, при котором Ваня выиграет первым ходом это $90$ .

Решение БУ

from  functools import lru_cache
lru_cache(None)
def f(a,c):# Параметр ’с’ в этой программе - это счётчик,сделанных ходов в данной партии.
    # В данной задаче он обязателен,поскольку изначальное кол-во камней может быть слишком мало,а также есть ходы,которые не так сильно увеличивают кол-во камней в куче(+2,+4),как,например ход (*3).
    # По этой причине у нас может возникнуть ошибка,связанная с превышением глубины рекурсии или же программа будет слишком долго высчитывать значения.
    if a >= 271:return 0
    if c > 10:return 1000 #Возвращаем очень большое значение,которое указывает программе,что при таком значении невозможно дойти до выигрыша при малом количестве ходов.
    t = [f(a+2,c+1),f(a+4,c+1),f(a*3,c+1)]
    n = [i for i in t if i <= 0]
    if n:return -max(n) + 1
    return -max(t)
for i in range(1,271):
    if f(i,0) == -1:
        print(f"19) {i}")

Ответ: 90

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

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

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

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

Решение

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

Минимальное значение, при котором возможна такая ситуация это $6$ . Ход партии будет таков: $6− > 18− > 42$ (Ваня побеждает).

Максимальным значением будет $36$ . Развитие партии будет таково: $36− > 39− > 42$ (Ваня побеждает).

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

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 40: # если камней в куче стало больше 39
        return 0 # прекращаем игру
    if first_heap % 6 == 0: # если текущее количество камней кратно 6
        moves = [game(first_heap*2),game(first_heap*3),game(first_heap+3)] # то мы можем совершить любой ход
    else: # в ином случае
        moves = [game(first_heap + 3)] # мы можем совершить только ход +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 i % 6 == 0: # если текущее количество камней кратно 6
        if game(i*2) == 1 or game(i*3) == 1 or game(i+3) == 1: # если после неудачного хода Пети возможен выигрыш Вани
            print(i)
    else: # в ином случае
        if game(i + 3) == 1: # если после неудачного хода +3 от Пети возможен выигрыш Вани
            print(i)

Ответ: 636

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

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

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

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

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

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

Для начала определим какие ходы в каких ситуациях мы можем совершать. Изначальное значение S всегда нечётное, также после ходов мы должны получать нечётные значения, значит, в данной игре мы можем использовать только $+ 4$ , $∗ 3$ ходы. Так как, нечётное * нечётное = нечётное число и нечётное + чётное = нечётное число. Теперь определим при каких значениях первым ходом побеждает Петя. Максимальный ход, который мы можем совершить это $∗3$ . Минимальное значение, при котором Петя побеждает своим первым ходом равняется: $180 = 60 3$

Поскольку данное значение чётное, оно нам не подходит. Тогда берём следующее значение $61$ и оно уже нам подходит. Получается, что все нечётные значения в отрезке [61;179] - это значения, в которых Петя побеждает своим первым ходом.

Определим значения, при которых Ваня побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанный отрезок – это значение, в котором Ваня выигрывает своим первым ходом. Распишем значения и стратегии, при которых Ваня побеждает первым ходом:

$S = 57$ . Петя может увеличить количество камней до $61$ ходом $+ 4$ или до $171$ ходом $∗3$ . В обоих случаях Ване не составит труда завершить партию следующим ходом.

$S = 59$ . Петя может увеличить количество камней до $63$ ходом $+ 4$ или до $177$ ходом $∗3$ . В обоих случаях Ване не составит труда завершить партию следующим ходом.

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

Программная реализация

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 180: # если камней в куче стало больше 179
        return 0 # прекращаем игру
    moves = [] # cписок всех возможных ходов в партии
    if first_heap % 2 == 0: # если количество камней в куче является чётным
        # то можем совершить только +3 ход, так как чётное+нечётное = нечётное
        moves = [game(first_heap+3)]
    else: # если количество камней в куче является нечётным
        # то можем совершить только +4,*3 ход, так как нечётное*нечётное = нечётное и нечётное+чётное = нечётное
        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,180,2):
    # если в данной позиции возможен выигрыш Вани первым ходом
    if game(i) == -1:
        print(i)

В результате программы на экран будет выведены числа 57 и 59. Наибольшим является число 59.

Ответ: 59

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

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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 1 или 3 камня. Например, имея кучу из 12 камней, за один ход можно получить кучу из 13 или 15. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 45. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 45 или больше камней. В начальный момент в куче было $1 ≤ S < 45$ . Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.

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

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

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

Максимальный ход доступный нам в партии это $+ 3$ . Минимальное значение отрезка значений, в которых Петя побеждает первым ходом равняется: $45− 3 = 42$

Получается, что в отрезке [42;44] Петя выигрывает своим первым ходом.

Ответ: $424344$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 45: # если камней в куче стало больше 44
        return 0 # прекращаем игру
    moves = [game(first_heap+1),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,45):
    if game(i) == 1: # если в данной позиции возможен выигрыш Пети первым ходом
        print(i)

Ответ: 424344

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

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

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

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

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

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

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

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

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

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

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 59: # если камней в куче стало больше 58
        return 0 # прекращаем игру
    moves = [game(first_heap+2),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,59):
    if game(i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)
        break

Ответ: 18