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

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

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

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

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

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

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

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

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

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

Задача 1#49383

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 83.

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

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

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

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

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

def f(a,b):
 if a>=83: return b%2==0
 if b==0:return 0
 h = [f(a+2, b-1), f(a+3, b-1),f(a*4, b-1)]
 return any(h) if b%2!=0 else all(h)
print(min([a for a in range(6,81) if f(a,1)]))

Ответ: 21

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

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

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

Задача 2#78623

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

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

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

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

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

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

Задача 3#76988

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

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

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

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

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

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

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

from functools import lru_cache
@lru_cache(None)
def f(a):
    if a >= 65: return 0
    if a * 3 >= 109:
        n = [f(a + 5), f(a + 7)]
    else:
        n = [f(a + 5), f(a + 7), f(a * 3)] #список с возможными ходами
    t = [i for i in n if i <= 0] #список с отрицательными ходами
    if t:
        return -max(t) + 1 #выигрыш Пети
    else:
        return -max(n) #выигрыш Вани
for i in range(1, 40):
    if f(i) == 1:
        print(i)

Ответ: 22

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

Задача 4#76979

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

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

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

from functools import lru_cache
@lru_cache(None)
def f(a):
    if a >= 100: return 0
    if a * 4 > 120:
        n = [f(a + 3)]
    else:
        n = [f(a + 3), f(a * 4)] #список с возможными ходами
    t = [i for i in n if i <= 0] #список с отрицательными ходами
    if t:
        return -max(t) + 1 #выигрыш Пети
    else:
        return -max(n) #выигрыш Вани
for i in range(1, 61):
    if f(i) == 1:
        print(i)

Ответ: 25

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

Задача 5#72457

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

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

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

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

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

Ответ: 31

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

Задача 6#72431

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

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

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

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

from functools import  lru_cache
@lru_cache(None)
def f(a):
    if a >= 120:return 0
    m = [f(a+2),f(a+3),f(a*3)]
    n = [i for i in m if i <= 0]
    if n:return -max(n)+1
    return -max(m)
for i in range(1,120):
    if f(i) == -1:
        print(i)
        break

Ответ: 38

Курсы

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

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

Задача 7#72404

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

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

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

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

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

Задача 8#64069

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

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

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

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

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

def f(s,m):
    if s>=80: return m%2==0
    if m==0: return 0
    h=[f(s+2, m-1), f(s+3, m-1), f(s*2, m-1)]
    return any(h) if m%2!=0 else all(h)
print(min(s for s in range(1,80) if f(s,2)))

Ответ: 38

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

Задача 9#63381

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

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

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

#сколько камней в куче может получиться после хода, если до хода было s камней
def f(s):
    return s+3,s*2

#сколько ходов осталось до конца игры, если в куче сейчас s камней
def stepsLeft(s):
    if s>= 46:
        return 0
    else:
        steps = [stepsLeft(x) for x in f(s)]
        if any(x%2 == 0 for x in steps):
            return min(x for x in steps if x%2 == 0)+1
        else:
            return max(steps)+1


for s in range(1, 46):
    if stepsLeft(s) == 2: #Ваня выиграет своим первым ходом и игра закончится за два хода
        print("при s =",s," камней: игра закончится через", stepsLeft(s),"ходов")

Ответ: 20

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

Задача 10#62834

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

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

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

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

Ответ: 4

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

Задача 11#62677

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

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

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

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

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

Ответ: 7

Интенсивы

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

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

Задача 12#62674

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

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

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

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

Ответ: 8

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

Задача 13#62671

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

Ответ: 24

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

Задача 14#62668

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в три раза. Например, имея кучу из 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 f(a):
    if a >= 47:return 0
    t = [f(a+2),f(a*3)]
    n = [i for i in t if i <= 0]
    if n:return -max(n) + 1
    return -max(t)
for i in range(1,47):
    if f(i) == -1:
        print(i)
        break

Ответ: 14

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

Задача 15#62665

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в два раза. Например, имея кучу из 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 f(a):
    if a >= 38:return 0
    t = [f(a+2),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,38):
    if f(i) == -1:
        print(i)
        break

Ответ: 17

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

Задача 16#61320

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

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

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

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

Ответ: 35

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

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

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

Задача 17#61317

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

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

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

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

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

Ответ: 20

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

Задача 18#61314

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

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

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

from functools import lru_cache
@lru_cache(None)
def f(a):
    if a >= 67:return 0
    t = [f(a+3),f(a+5),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,67):
    if f(i) == -1:
        print(i)
        break

Ответ: 31

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

Задача 19#59597

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

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

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

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

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

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

def f(a,c=0):#Добавим параметр ’c’ в функцию,которая будет считать количество ходов в партии
    if a >= 40:return 0
    if c == 1:#Если сейчас первый ход Вани
        if a <= 13:#Если значение камней в куче не находится в области проигрыша,то Ваня должен сделать такой ход,
            # чтобы после его хода количество камней гарантированно было в данной области
            t = [f(a*3,c+1)]
        else: #Если количество камней уже находится в области проигрыша,то Ваня делает минимальный ход,чтобы ни в коем случае не выиграть своим ходом
            # и передать очередь хода Пете,чтобы он выиграл своим вторым ходом
            t = [f(a+1,c+1)]
    elif c == 2:
        t = [f(a*3,c+1),f(a+1,c+1),f(a+6,c+1)]
    else:#Если сейчас первый ход Пети,то он может совершить любой ход
        t = [f(a+1,c+1),f(a+6,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,40):
    if f(i) == 2:
        print(i,f(i))

Ответ: 13

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

Задача 20#59179

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

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

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

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

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

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

def f(a):
    if a >= 57:return 0
    h = [f(a+3),f(a*2)]
    n = [i for i in h if i <= 0]
    if n:
        return -max(n)+1
    return -max(h)

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

Ответ: 26

Предыдущий раздел

Следующий раздел