Решения. Ответьте на следующие вопросы

• Название: Ответьте на следующие вопросы
• Дата: 20.06.2022
• Размер: 0.57 Mb.
• Имя файла: Решения.docx
• Тип: Документы; #604633

1) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
  а) добавить в кучу один камень;
  б) увеличить количество камней в куче в три раза.
Игра завершается в тот момент, когда количество камней в куче становится не менее 56. Если при этом в куче оказалось не более 80 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. В начальный момент в куче было S камней, 1 ≤ S ≤ 55.
Ответьте на следующие вопросы:
  Вопрос 1. Известно, что Ваня выиграл своим первым ходом после первого хода Пети. Назовите минимальное значение S, при котором это возможно.
  Вопрос 2. Определите, два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
  Вопрос 3. Найдите значение S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

from functools import lru_cache

def moves(h):

return (h+1),(h*3)

@lru_cache(None)

def game(h):

if 56 <= h <= 80: return 'W'

if h > 80: return 'P1'

if any(game(m)=='W' for m in moves(h)): return 'P1'

if all(game(m)=='P1' for m in moves(h)): return 'B1'

if any(game(m)=='B1' for m in moves(h)): return 'P2'

if all(game(m)=='P1' or game(m)=='P2' for m in moves(h)): return 'B2'
for s in range(1,56):

if game(s) == 'B2':

print(s, game(s))


2) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в любую кучу один камень или увеличить количество камней в любой куче в четыре раза. Игра завершается в тот момент, когда общее количество камней в двух кучах становится не менее 105. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 4 камня, а во второй – S камней, 1 ≤ S ≤ 100.
Ответьте на следующие вопросы:
  Вопрос 1. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Назовите минимальное значение S, при котором это возможно.
  Вопрос 2. Найдите минимальное и максимальное значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
  Вопрос 3. Найдите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
from functools import lru_cache

def moves(h):

a,b = h

return (a+1,b),(a*4,b),(a,b+1),(a,b*4)

@lru_cache(None)

def game(h):

a,b = h

if a+b>=105: return 'W'

if any(game(m)=='W' for m in moves(h)): return 'P1'

if all(game(m)=='P1' for m in moves(h)): return 'B1'

if any(game(m)=='B1' for m in moves(h)): return 'P2'

if all(game(m)=='P1' or game(m)=='P2' for m in moves(h)): return 'B2'
for s in range(1,101):

h = 4 ,s

if game(h) == 'B2':

print(s, game(h))

3) (А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в любую кучу один камень или увеличить количество камней в любой куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 30. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было K камней, а во второй – S камней, 1 ≤ K ≤ 29, 1 ≤ S ≤ 29.
Ответьте на следующие вопросы:

  Вопрос 1. Сколько существует пар (K; S), таких что Ваня выигрывает первым ходом при любой игре Пети?
  Вопрос 2. При K=6, найдите минимальное и максимальное значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
  Вопрос 3. Сколько существует пар (K; S), при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
from functools import lru_cache

def moves(h):

a,b = h

return (a+1,b),(a*2,b),(a,b+1),(a,b*2)

@lru_cache(None)

def game(h):

a,b = h

if a+b>=30: return 'W'

if any(game(m)=='W' for m in moves(h)): return 'P1'

if all(game(m)=='P1' for m in moves(h)): return 'B1'

if any(game(m)=='B1' for m in moves(h)): return 'P2'

if all(game(m)=='P1' or game(m)=='P2' for m in moves(h)): return 'B2'
print('задание 19')

cnt = 0

for k in range(1,30):

for s in range(1,30):

h = k, s

if game(h) == 'B1':

cnt += 1

print(cnt)
print('задание 20')

for s in range(1,30):

h = 6, s

if game(h) == 'P2':

print(s, game(h))

print('задание 21')

cnt = 0

for k in range(1,30):

for s in range(1,30):

h = k, s

if game(h) == 'B2':

cnt += 1

print(cnt)


4) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит лист бумаги, на котором написано двоичное число. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может приписать справа или слева к имеющемуся числу двоичную запись любого из чисел вида 4^n + 3, где n – произвольное натуральное число, либо приписать справа или слева от имеющегося числа его копию. Игра завершается в тот момент, когда количество единиц в двоичной записи числа на листе станет больше или равно 60. В начальный момент единиц в числе было S: 1<=S<=57.

19. Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение S, когда такая ситуация возможна?
20. Найдите минимальное и максимальное значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
21. Найдите максимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
from functools import lru_cache

def moves(h):

return (h+3),(h*2)

@lru_cache(None)

def game(h):

if h >= 60: return 'W'

if any(game(m)=='W' for m in moves(h)): return 'P1'

if all(game(m)=='P1' for m in moves(h)): return 'B1'

if any(game(m)=='B1' for m in moves(h)): return 'P2'

if all(game(m)=='P1' or game(m)=='P2' for m in moves(h)): return 'B2'
for s in range(1,58):

if game(s) == 'B2':

print(s, game(s))

5) (А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из кучи один камень или уменьшить количество камней в любой куче в два раза (если количество камней нечётно, то остаётся на один камень меньше, чем убирается). Игра завершается в тот момент, когда общее количество камней в двух кучах становится не более 18, побеждает игрок, сделавший последний ход. В начальный момент в первой куче было K≥1 камней, а во второй – S≥1 камней, S+K ≥ 19.
Ответьте на следующие вопросы:
  Вопрос 1. Известно, что из начальной позиции (M; M) Ваня выигрывает первым ходом при любой игре Пети. При каком значении M это возможно?
  Вопрос 2. При K=13, найдите минимальное и максимальное значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
  Вопрос 3. При каком минимальном значении N для начальной пары (N;N) одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

from functools import lru_cache

def moves(h):

a,b = h

x = []

if a>0: x.append((a-1,b))

if b>0: x.append((a,b-1))

if a>0: x.append((a//2,b))

if b>0: x.append((a,b//2))

return x
@lru_cache(None)

def game(h):

a,b = h

if a+b <= 18: return 'W'

if any(game(m)=='W' for m in moves(h)): return 'P1'

if all(game(m)=='P1' for m in moves(h)): return 'B1'

if any(game(m)=='B1' for m in moves(h)): return 'P2'

if all(game(m)=='P1' or game(m)=='P2' for m in moves(h)): return 'B2'
for s in range(1,101):

h = s,s

if game(h) == 'B2':

print(s, game(h))

6) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в три раза. При этом нельзя повторять ход, который только что сделал второй игрок. Например, если в начале игры в куче 4 камня, Петя может первым ходом получить кучу из 5, 6 или 12 камней. Если Петя добавил 1 камень и получил кучу из 5 камней, то следующим ходом Ваня может либо добавить 2 камня (и получить 7 камней), либо утроить количество камней в куче (их станет 15). Получить 6 камней Ваня не может, так как для этого нужно добавить 1 камень, а такой ход только что сделал Петя.
Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается, когда количество камней в куче становится не менее 140. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 140 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 139.
Ответьте на следующие вопросы:
  Вопрос 1. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
  Вопрос 2. Определите, минимальное и максимальное значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
  Вопрос 3. Найдите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
from functools import lru_cache

def moves(h):

x, last = h

a = []

if last != '+1': a.append((x+1,'+1'))

if last != '+2': a.append((x+2,'+2'))

if last != '*3': a.append((x*3,'*3'))

return a

@lru_cache(None)

def game(h):

x, last = h

if x >= 140: return 'W'

if any(game(m)=='W' for m in moves(h)): return 'P1'

if all(game(m)=='P1' for m in moves(h)): return 'B1'

if any(game(m)=='B1' for m in moves(h)): return 'P2'

if all(game(m)=='P1' or game(m)=='P2' for m in moves(h)): return 'B2'
for s in range(1,140):

h = s, '0'

if game(h) == 'B2':

print(s, game(h))

7)

from functools import lru_cache

def moves(h):

x, limit = h

a = []

if limit >= 1: a.append((x+1,limit-1))

if limit >= 2: a.append((x+2,limit-2))

if limit >= x: a.append((x*2,limit - x))

return a
@lru_cache(None)

def game(h):

x, limit = h

if x >= 41: return 'W'

if any(game(m)=='W' for m in moves(h)): return 'P1'

if all(game(m)=='P1' for m in moves(h)): return 'B1'

if any(game(m)=='B1' for m in moves(h)): return 'P2'

if all(game(m)=='P1' or game(m)=='P2' for m in moves(h)): return 'B2'

if any(game(m)=='B2' for m in moves(h)): return 'P3'

if all(game(m)=='P1' or game(m)=='P2' or game(m)=='P3' for m in moves(h)): return 'B3'
for s in range(1,41):

h = s, 50-s

if game(h) is not None:

print(s, game(h))