Е19-21.58 Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 211

Администратор

3 месяца назад

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, в одной куче 10 камней, а в другой 5 камней; такую позицию в игре обозначим (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 211. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах 211 или больше камней.
В начальный момент в первой куче 17 камней, во второй куче — S камней; 1 < S ≤193.

Апробация 04.03.2026 – задание №19-21

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

Ответ:

20. Для игры, описанной в задании 19, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.

Ответ:

21. Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Ответ:

Решение на Python

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

Решение — 19

def f(s1,s2,m):
    if s1+s2 >= 211: return m%2==0
    if m==0: return 0
    h = [f(s1+1,s2,m-1),f(s1,s2+1,m-1),f(s1*2,s2,m-1),f(s1,s2*2,m-1)]
    return any(h) if (m-1)%2==0 else any(h)
print('19)', [s2 for s2 in range(1,194) if f(17, s2, 2)])

def f(s1,s2,m):

if s1+s2 >= 211: return m%2==0

if m==0: return 0

h = [f(s1+1,s2,m-1),f(s1,s2+1,m-1),f(s1*2,s2,m-1),f(s1,s2*2,m-1)]

return any(h) if (m-1)%2==0 else any(h)

print('19)', [s2 for s2 in range(1,194) if f(17, s2, 2)])

19) [49, 50, 51, 52, 53, 54,…]

Решение — 20-21

def f(s1,s2,m):
    if s1+s2 >= 211: return m%2==0
    if m==0: return 0
    h = [f(s1+1,s2,m-1),f(s1,s2+1,m-1),f(s1*2,s2,m-1),f(s1,s2*2,m-1)]
    return any(h) if (m-1)%2==0 else all(h)
print('20)', [s2 for s2 in range(1,194) if not f(17, s2, 1) and f(17, s2, 3) ])
print('21)', [s2 for s2 in range(1,194) if not f(17, s2, 2) and f(17, s2, 4) ])

def f(s1,s2,m):

if s1+s2 >= 211: return m%2==0

if m==0: return 0

h = [f(s1+1,s2,m-1),f(s1,s2+1,m-1),f(s1*2,s2,m-1),f(s1,s2*2,m-1)]

return any(h) if (m-1)%2==0 else all(h)

print('20)', [s2 for s2 in range(1,194) if not f(17, s2, 1) and f(17, s2, 3) ])

print('21)', [s2 for s2 in range(1,194) if not f(17, s2, 2) and f(17, s2, 4) ])

20) [88, 96]
21) [87, 95]