19.04 Уменьшение количества камней

Решение 1

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

Решение 2

from functools import lru_cache
def moves(h):
    a, b = h
    m = []
    if a > 1:
        m += [((a + 1)//2, b), (a - 1, b)]
    if b > 1:
        m += [(a, (b + 1)//2), (a, b - 1)]
    return m

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

for i in range(19, 100):
    h = i, 20
    if f(h) == ’P1’:
        print(i)

Решение 1

Подпишем ячейки: — , — . Поместим в ячейке число , а наше значение . В ячейке запишем формулу — там будет сумма камней во время старта

В ячейках запишем все возможные пары куч, которые можно получить: в поместим , в — , в поместим (ЦЕЛОЕ возвращает как раз нужный нам результат деления), в — , в поместим , в — , в поместим , в — . В ячейках столбца будем вести сумму куч (в поместим и растянем эту формулу на все пары куч).

В ячейке запишем формулу . Так мы получим сумму куч после самого аргессивного хода Вжика.

Условно окрасим в зеленый цвет ячейку , если значение в ней меньше 35.

Постепенно перебирая значения ячейки от 50 (например) вниз, заметим, что первый раз все ячейки результата выделяются зеленым при . Значит, это максимальное значение, при котором выполняется условие.

Решение 2

from functools import cache
def moves(h):
    a, b = h
    mesi = []
    if a >= 1:
        mesi.append((a // 2, b))
        mesi.append((a - 1, b))
    if b >= 1:
        mesi.append((a, b // 2))
        mesi.append((a, b - 1))
    return mesi

@cache
def game(h):
    if sum(h) <= 34:
        return ’end’
    if any(game(x) == ’end’ for x in moves(h)):
        return ’win1’
    if all(game(x) == ’win1’ for x in moves(h)):
        return ’lose1’

for i in range(100, 11, -1):
    h = i, 22
    print(i, game(h))

from functools import lru_cache
def moves(heap):
    m = []
    if heap > 0:
        m += [heap - 1]
    if heap > 2:
        m += [heap - 3]
    return m
@lru_cache(None)
def game(heap):
    if heap <= 11:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif any(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’
for s in range(12, 100):
    print(s, game(s))
# или
from functools import lru_cache
def moves(heap):
    m = []
    if heap > 0:
        m += [heap - 1]
    if heap > 2:
        m += [heap - 3]
    return m
@lru_cache(None)
def game(heap):
    if heap <= 11:
        return 0
    steps = [game(x) for x in moves(heap)]
    if any(x % 2 == 0 for x in steps):
        return min(x for x in steps if x % 2 == 0) + 1
    return max(steps) + 1
                                                                                                     
                                                                                                     
for s in range(1, 100):
    print(s, game(s), [game(x) for x in moves(s)])

from functools import lru_cache


@lru_cache(None)
def f(first_heap, second_heap, third_heap, c=0):
    if first_heap + second_heap + third_heap <= 32:
        return 0
    if c > 4:
        return 123123
    moves = []
    if first_heap > 1:
        moves.append(f(first_heap - 1, second_heap, third_heap, c + 1))
        moves.append(f((first_heap + 1) // 2, second_heap, third_heap, c + 1))
    if second_heap > 1:
        moves.append(f(first_heap, second_heap - 1, third_heap, c + 1))
        moves.append(f(first_heap, (second_heap + 1) // 2, third_heap, c + 1))
    if third_heap > 1:
        moves.append(f(first_heap, second_heap, third_heap - 1, c + 1))
        moves.append(f(first_heap, second_heap, (third_heap + 1) // 2, c + 1))

    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(11, 100):
    if f(11 - 1, 11, i) == 1 or f((11 + 1) // 2, 11, i) == 1 or f(11, 11-1, i) == 1 or \
            f(11, (11 + 1) // 2, i) == 1 or f(11, 11, i - 1) == 1 or f(11, 11, (i + 1) // 2) == 1:
        print(i)

from functools import lru_cache

def moves(h):
    a, b = h
    if a > 1 and b > 1:
        return (a - 1, b), (a, b - 1), (a // 2 + (a % 2), b), (a, b // 2 + (b % 2))
    if a > 1:
        return (a - 1, b), (a, b - 1), (a // 2 + (a % 2), b)
    if b > 1:
        return (a - 1, b), (a, b - 1), (a, b // 2 + (b % 2))
    return (a - 1, b), (a, b - 1)

@lru_cache(None)
def f(h):
    if sum(h) <= 32:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’

for i in range(23, 100):
    h = i, 10
    if f(h) == ’LOSE1’:
        print(i)

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

Неудачный ход – ход при котором игрок мог победить, но отдал победу противнику. Поэтому для начала найдем значения , при которых Петя мог победить за 1 или 2 хода.

Рассмотрим ситуацию, когда Петя сделал один ход. Чтобы получить число 7 есть всего 2 возможных хода: убрать из кучи один камень или убрать из кучи три камня. Для этих ходов подойдут значения и .

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

Рассмотрим . Первым ходом Петя делает неудачный ход – убирает 1 камень, – из этой позиции нельзя победить за один ход, поэтому этот вариант не подходит.

Рассмотрим . Первым ходом Петя делает неудачный ход – убирает 3 камня, – из этой позиции можно победить за один ход, поэтому этот вариант подходит.

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

from functools import lru_cache

@lru_cache(None)
def game(heap):  # Функция игры
    if heap <= 7:  # Если камней в кучах стало меньше 7
        return 0  # Прекращаем игру
    moves = [game(heap - 1), game(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(8, 100):
    if game(i) == 1 or game(i) == 2:  # Если Петя мог победить своим 1ым или 2м ходом

        # Для неудачного хода Пети нужно вручную сделать за него ходы от взятого s
        # и запустить функцию с изменнённым значением кучи, чтобы в хотя бы одном из ходов Петя ошибся.
        # Таким образом, Ваня станет первым ходившим игроком для функции,
        # и в итоге нужно будет получить значение 1 для победы Вани первым ходом после неудачного хода Пети.

        vanya_win = False  # Переменная-флаг, отвечающая за победу Вани (изначально Ваня не побеждает)
        if game(i - 1) == 1:  # Если при ходе -1 в итоге победит Ваня
            vanya_win = True
        if game(i - 3) == 1:  # Если при ходе -3 в итоге победит Ваня
            vanya_win = True

        if vanya_win:  # Если в итоге Ваня победил
            print(i)

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

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

Решение Excel

Создадим табличку, первый столбец которой назовём Старт, четвёртый Петя, а седьмой — Ваня.

В ячейку запишем , а в D4 запишем формулу =СУММ(B4:C4).

Так как Ване нужно победить первым ходом, то выгоднее всего ходить самым агрессивным ходом — делением на два. В ячейку запишем формулу =ЦЕЛОЕ(МАКС(E4:F4)/2), в — =МИН(E4:F4).

В ячейку J4 запишем формулу =СУММ(H4:I4), скопируем и вставим её в следующую клеточку.

В запишем =B4-1, в =C4, а в — =СУММ(E4:F4).

Добавим условное форматирование. Выделим суммы, которые относятся к Пете и затем в разделе Главная выберем условное форматирование Правила выделения ячеек Меньше…, в открывшемся окошке записываем и выбираем красный цвет. Выделим сумму, которая относится к старту, сделаем её зелёной по аналогии с суммой после хода Пети. То же самое сделаем с суммой, которая относится к Ване.

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

В начальную позицию запишем и начнём подставлять значения в ячейку , пока все суммы камней после хода Вани не станут зелёными.

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

from functools import lru_cache

@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap <= 12:  # Если камней в кучах стало меньше 12
        return 0  # Прекращаем игру
    moves = [game(first_heap, second_heap // 2), game(first_heap // 2, second_heap),
             game(first_heap - 1, second_heap),game(first_heap, second_heap - 1)]  # Генерация всех возможных ходов
    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(4, 20):
    # если в данной позиции возможен выигрыш Вани первым ходом
    if game(9,i) == -1:
        print(i)
        break

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

Для начала найдем значения , при которых Петя мог победить за 1 ход. Чтобы получить число 2, есть всего 4 возможных хода: убрать половину камней, убрать два камня, убрать две трети камней, убрать три камня. Для всех этих ходов подойдут следующие значения Значит нужно рассмотреть только 4 значения и выбрать максимальное, чтобы Ваня мог победить при неудачном ходе Пети. Рассмотрим Первым ходом Петя делает неудачный ход делением на 2 (так как 6 делится на 2) в после чего Ваня например убирает из кучи две трети камней, создавая этим позицию в которой он побеждает.

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

from functools import lru_cache


@lru_cache(None)
def game(heap):  # Функция игры

    if heap <= 2:  # Если куча меньше или равна 2
        return 0  # Возвращаем стартовое значение 0

    # Список для возможных ходов,
    # которые нужно добавить в зависимости от условий
    steps = []
    # 1 Условие
    if heap % 2 == 0:
        steps += [game(heap // 2)]  # Убираем половину
    else:
        steps += [game(heap - 2)]  # Убираем 2 камня
    # 2 Условие
    if heap % 3 == 0:
        steps += [game(heap // 3)]  # Убрать две трети равносильно оставить одну треть
    else:
        steps += [game(heap - 3)]  # Убираем 3 камня

    petya_win = [x for x in steps if x <= 0]  # Выигрышные позиции для пети

    if petya_win:  # Если такие значения есть
        return -max(petya_win) + 1
    return -max(steps)


for s in range(3, 100):
    if game(s) == 1:  # Если Петя мог победить своим 1ым ходом

        # Для неудачного хода Пети нужно вручную сделать за него ходы от взятого s
        # и запустить функцию с изменнённым значением кучи, чтобы в хотя бы одном из ходов Петя ошибся.
        # Таким образом, Ваня станет первым ходившим игроком для функции,
        # и в итоге нужно будет получить значение 1 для победы Вани первым ходом после неудачного хода Пети.

                                                                                                     
                                                                                                     
        vanya_win = False  # Переменная-флаг, отвечающая за победу Вани (изначально Ваня не побеждает)
        if s % 2 == 0:
            if game(s // 2) == 1:  # Если при ходе //2 в итоге победит Ваня
                vanya_win = True
        else:
            if game(s - 2) == 1:  # Если при ходе -2 в итоге победит Ваня
                vanya_win = True
        if s % 3 == 0:
            if game(s // 3) == 1:  # Если при ходе //3 в итоге победит Ваня
                vanya_win = True
        else:
            if game(s - 3) == 1:  # Если при ходе -3 в итоге победит Ваня
                vanya_win = True

        if vanya_win:  # Если в итоге Ваня победил
            print(s)