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

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

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

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

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

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

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

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

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

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

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

Например, если в куче 5 камней, то за один ход можно получить 8, 9 или 25 камней.

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

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

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

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

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

Если начальное значение будет более $25$ , то и его квадрат будет более $627$ , что даст Пете автоматическую победу. Рассмотрим значения менее или равные $25$ .

При $25$ Петя не сможет достичь $627$ , но будет обязан увеличить значение как минимум на $3$ , что даст Ване возможность выиграть возведением в квадрат.

При $24$ всё абсолютно аналогично, как и при $23$ .

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

Ответ: $3$

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

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

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

Ответ: 3

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

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

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

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

Например, если в куче 5 камней, то за один ход можно получить 8, 9 или 25 камней.

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

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

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

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

Если начальное значение будет более $18$ , то и его квадрат будет более $350$ , что даст Пете автоматическую победу. Рассмотрим значения менее или равные $18$ .

При $18$ Петя не сможет достичь $350$ , но будет обязан увеличить значение как минимум на $3$ , что даст Ване возможность выиграть возведением в квадрат.

При $17$ всё абсолютно аналогично, как и при $16$ .

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

Ответ: $3$

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

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

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

Ответ: 3

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

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

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

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

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

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

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

Поймём, что любое число можно будет увеличить как минимум в полтора раза.

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

Очевидно, что нечётные числа более $55$ проверять не стоит, ведь $55⋅2 = 110$ , что будет победой, аналогично с большими числами.

Проанализируем чётные числа. Они могут быть увеличены в полтора раза. Число $72$ , к примеру, даст нам $72 ⋅1.5 = 108$ , что будет победой, аналогично с большими числами.

Возьмём $70$ . Петя, прибавив $1$ , даст Ване возможность увеличить число в $2$ раза и проиграет. Вариант увеличить число в $1.5$ раза для Пети тоже критичен. $70⋅1.5 = 105$ . Ваня вновь может умножить число на $2$ и выиграть. Получаем, что $70$ нам подходит. Максимальное нечётное число будет точно меньше $55$ , что меньше $70$ . Мы же вычислили максимальное чётное, которое может подойти Ване без победы Пети первым ходом.

Ответ: $70$

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

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

Ответ: 70

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

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

Например, если в куче 5 камней, то за один ход можно получить 6 или 10 камней, а если в куче 6 камней, то за один ход можно получить 7 или 9 камней. Игра завершается, когда количество камней в куче достигает 84.

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

В начале игры в куче было S камней, $1 ≤ S ≤ 83$ .

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

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

Поймём, что любое число можно будет увеличить как минимум в полтора раза.

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

Очевидно, что нечётные числа более $43$ проверять не стоит, ведь $43⋅2 = 86$ , что будет победой, аналогично с большими числами.

Проанализируем чётные числа. Они могут быть увеличены в полтора раза. Число $56$ , к примеру, даст нам $56 ⋅1.5 = 84$ , что будет победой, аналогично с большими числами.

Если нам нужно максимальное число, то будем проверять чётные числа меньше $56$ , чтобы не дать Пете победить первым ходом.

Возьмём $54$ . Петя, прибавив $1$ , даст Ване возможность увеличить число в $2$ раза и проиграет. Вариант увеличить число в $1.5$ раза для Пети тоже критичен. $54⋅1.5 = 81$ . Ваня вновь может умножить число на $2$ и выиграть. Получаем, что $54$ нам подходит. Максимальное нечётное число будет точно меньше $43$ , что меньше $54$ . Мы же вычислили максимальное чётное, которое может подойти Ване без победы Пети первым ходом.

Ответ: $54$

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

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

Ответ: 54

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

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

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

Например, если в начале игры в куче 4 камня, Петя может первым ходом получить кучу из 5 или из 8 камней. Добавить два камня Петя не может, так как в этом случае в куче станет 6 камней, а 6 делится на 3.

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

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

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

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

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

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

$51⋅2 = 102$ , что уже меньше нужного. К тому же $51$ кратно трём, Петя не сможет умножить на два, ведь $102$ кратно трём. Он прибавит $1$ или $2$ . Если добавить единицу, то $52⋅2 = 104$ , что даст Ване победить. Если добавить $2$ , то $53 ⋅2 = 106$ , Ваня вновь победит.

Ответ: $51$

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

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

Варианты правильных ответов:

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

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

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

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

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

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

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

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

$75⋅2 = 150$ , что уже меньше нужного. К тому же $75$ кратно трём, Петя не сможет умножить на два, ведь $150$ кратно трём. Он прибавит $1$ или $2$ . Если добавить единицу, то $76⋅2 = 152$ , что даст Ване победить. Если добавить $2$ , то $77 ⋅2 = 154$ , Ваня вновь победит.

Ответ: $75$

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

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

Варианты правильных ответов: