19-21 - Теория игр
Источники:
сайт Полякова (https://kpolyakov.spb.ru/)
Embedded Files
1)(№32 А.Носкин) За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 40. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 40 или больше камней. В начальный момент в первой куче было 9 камней, во второй куче – S камней; 1 ≤ S ≤ 30.
Задание 19
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Задание 20
Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Сколько существует значений S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Решение
def f(s1,s2,c,m):
if s1+s2>=40: return c%2==m%2
if c==m: return 0
h=[f(s1+1,s2,c+1,m),f(s1,s2+1,c+1,m),f(s1*2,s2,c+1,m),f(s1,s2*2,c+1,m)]
if (c+1)%2==m%2: return any(h)
else: return all(h)# для задания 19 - заменить all на any
for s in range(1,31):
for m in range(1,5):
if f(9,s,0,m):
if m==4: # (19 - m == 2, 20 - m == 3, 21 - m ==4)
print(s,m)
break
Ответ:
19 - 4 (m == 2 и заменяем all на any)
20 - 3 14 (m == 3)
21 - 0 (m == 4)
2)(№ 1) За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 75. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 75 или больше камней. В начальный момент в первой куче было 8 камней, во второй куче – S камней; 1 ≤ S ≤ 66.
Задание 19
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Задание 20
Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Решение
Решение
def f(s1,s2,c,m):
if s1+s2>=40: return c%2==m%2
if c==m: return 0
h=[f(s1+1,s2,c+1,m),f(s1,s2+1,c+1,m),f(s1*2,s2,c+1,m),f(s1,s2*2,c+1,m)]
if (c+1)%2==m%2: return any(h)
else: return all(h)# для задания 19 - заменить all на any
for s in range(1,67):
for m in range(1,5):
if f(8,s,0,m):
if m==4: # (19 - m == 2, 20 - m == 3, 21 - m ==4)
print(s,m)
break
Ответ:
19 - 17 (m == 2 и заменяем all на any)
20 - 29 32 (m == 3)
21 - 28 (m == 4)
3)(№ 4831) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в три раза. При этом нельзя повторять ход, который только что сделал второй игрок. Например, если в начале игры в куче 4 камня, Петя может первым ходом получить кучу из 5, 6 или 12 камней. Если Петя добавил 1 камень и получил кучу из 5 камней, то следующим ходом Ваня может либо добавить 2 камня (и получить 7 камней), либо утроить количество камней в куче (их станет 15). Получить 6 камней Ваня не может, так как для этого нужно добавить 1 камень, а такой ход только что сделал Петя. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается, когда количество камней в куче становится не менее 140. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 140 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 139.
Ответьте на следующие вопросы:
Задание 19
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 20
Определите минимальное и максимальное значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Найдите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
Решение
def f(s,c,m,v):
if s>=140: return c%2==m%2
if c==m: return 0
h=[f(s+1,c+1,m,1),f(s+2,c+1,m,2),f(s*3,c+1,m,3)]
if v>0: h.pop(v-1)
if (c+1)%2==m%2: return any(h)
else: return all(h)
for s in range(1,140):
for m in range(1,7):
if f(s,0,m,0):
if m==2: # (19 - m == 2, 20 - m == 3, 21 - m ==4)
print(s,m)
break
Ответ:
19 - 46 (m == 2)
20 - 16 45 (m == 3)
21 - 15 (m == 4)
4)(№ 3084 А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
а) добавить в кучу один камень;
б) увеличить количество камней в куче в два раза;
в) увеличить количество камней в куче в три раза.
Игра завершается в тот момент, когда количество камней в куче становится не менее 43. Если при этом в куче оказалось не более 72 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. В начальный момент в куче было S камней, 1 ≤ S ≤ 42.
Ответьте на следующие вопросы:
Задание 19
Найдите минимальное значение S, при котором Ваня выигрывает своим первым ходом при любой игре Пети.
Задание 20
Сколько существует значений S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Задание 21
Найдите минимальное и максимальное значения S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Найденные значения запишите в ответе в порядке возрастания.
Решение
def f(s,c,m):
if 43<=s<=72: return c%2==m%2
if s>72: return (c+1)%2==m%2
if c==m: return 0
h=[f(s+1,c+1,m),f(s*2,c+1,m),f(s*3,c+1,m)]
if (c+1)%2==m%2: return any(h)
else: return all(h)
for s in range(1,43):
for m in range(1,7):
if f(s,0,m):
if m==2: # (19 - m == 2, 20 - m == 3, 21 - m ==4)
print(s,m)
break
Ответ:
19 - 14 (m == 2)
20 - 3 (m == 3)
21 - 12 39 (m == 4)
5)(№ 3186) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в любую кучу один камень или увеличить количество камней в любой куче в четыре раза. Игра завершается в тот момент, когда общее количество камней в двух кучах становится не менее 105. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 4 камня, а во второй – S камней, 1 ≤ S ≤ 100.
Ответьте на следующие вопросы:
Задание 19
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Назовите минимальное значение S, при котором это возможно.
Задание 20
Найдите минимальное и максимальное значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Найдите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Решение
def f(s1,s2,c,m):
if s1+s2>=105: return c%2==m%2
if c==m: return 0
h=[f(s1+1,s2,c+1,m),f(s1,s2+1,c+1,m),f(s1*4,s2,c+1,m),f(s1,s2*4,c+1,m)]
if (c+1)%2==m%2: return any(h)
else: return all(h) # для задания 19 - заменить all на any
for s in range(1,101):
for m in range(1,7):
if f(4,s,0,m):
if m==4: # (19 - m == 2, 20 - m == 3, 21 - m ==4)
print(s,m)
break
Ответ:
19 - 7 (m == 2 и заменяем all на any)
20 - 22 24 (m == 3)
21 - 21 (m == 4)
6)(№ 5872 Д. Статный) Снегурочка и Дед Мороз играют в следующую игру: перед ними лежит куча подарков. Игроки ходят по очереди, первый ход делает Снегурочка. За один ход игрок может добавить 2 подарка, 5 подарков, 12 подарков или увеличить их количество в два раза. При этом нельзя повторять ход, который этот же игрок делал на предыдущем ходу. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество подарков. Игра завершается в тот момент, когда суммарное количество подарков станет не менее 121. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в куче будет не меньше, чем 121 подарок. В начальный момент в куче было S подарков; 1 ≤ S ≤ 120. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
Задание 19
Известно, что Дед Мороз выиграл своим первым ходом после неудачного первого хода Снегурочки. Укажите минимальное значение S, когда такая ситуация возможна.
Задание 20
Укажите минимальное S, при котором одновременно выполняются два условия:
– у Снегурочки есть выигрышная стратегия, позволяющая ей выиграть своим вторым ходом при любой игре Деда Мороза;
– у Снегурочки нет стратегии, которая позволит её гарантированно выиграть первым ходом.
Задание 21
Найдите максимальное и минимальное значения S, при которых
– у Деда Мороза есть выигрышная стратегия, позволяющая ему выиграть, по крайней мере, своим третьим ходом при любой игре Снегурочки;
– у Деда Мороза нет стратегии, которая позволит ему гарантированно выиграть первым или вторым ходом.
Найденные значения запишите в ответе в порядке возрастания.
Решение
def f(s,h,m,x):
if s>=121:return h%2==m%2
if m==h: return 0
d=[f(s+2,h+1,m,x+'0'),f(s+5,h+1,m,x+'1'),f(s+12,h+1,m,x+'2'),f(s*2,h+1,m,x+'3')]
if len(x)>=2: d.pop(int(x[-2]))
if (h+1)%2==m%2: return any(d)
else: return all(d) # для задания 19 - заменить all на any
for s in range(1,121):
for m in range(1,7):
if f(s,0,m,''):
if m==6: # (19 - m == 2, 20 - m == 3, 21 - m ==6)
print(s,m)
break
Ответ:
19 - 31 (m == 2 и заменяем all на any)
20 - 47 (m == 3)
21 - 35 46 (m == 6)
7) (№ 5305 Е. Джобс) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может увеличить количество камней в куче в целое число раз (но не более, чем на 80 камней) или добавить в кучу десять камней или добавить в кучу два камня. Например, из кучи из 10 камней можно получить кучу из 12, 20, 30, 40, 50, 60, 70, 80 и 90 камней. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Выигрывает тот игрок, после хода которого количество камней в куче становится не менее 166.
В начальный момент в куче было S камней; 1 ≤ S ≤ 165. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
Задание 19
Известно, что Петя выиграл своим вторым ходом после неудачного хода Вани. При каком минимальном значении S такое возможно?
Задание 20
Известно, что Петя имеет выигрышную стратегию. Укажите минимальное и максимальное значения при которых Петя не может победить первым ходом, но при любом ходе Вани Петя побеждает своим вторым ходом.
Задание 21
Известно, что Ваня имеет выигрышную стратегию за один или два хода, при этом не имеет выигрышной стратегии в один ход. Найдите минимальное значение S, при котором это возможно.
Решение
def f(s,h,m):
if s >= 166:return h%2==m%2
if m==h: return 0
d = [f(s+2,h+1,m),f(s+10,h+1,m)]
k=1
while s*k<=80:
d.append(f(s+s*k,h+1,m))
k+=1
if (h+1)%2==m%2: return any(d)
else: return all(d) # для задания 19 - заменить all на any
for s in range (1,166):
for m in range(1,6):
if f(s,0,m):
if m==3:print(s,m)# (19 - m == 3, 20 - m == 3, 21 - m ==4)
break
Ответ:
19 - 1 (m == 3 и заменяем all на any)
20 - 77 153 (m == 3)
21 - 142 (m == 4)
8) (№ 4374) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который этот же игрок делал на предыдущем ходу. Повторять чужие ходы и свои более старые ходы разрешается.
Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или 6 камней. Если Петя получил кучу из 5 камней (добавил два камня), то следующим ходом Ваня может получить 6, 7 или 10 камней. Если Ваня добавил один камень и получил 6 камней, то вторым ходом Петя может получить 7 или 12 камней. Получить 8 камней Петя не может, так как для этого нужно добавить 2 камня, а Петя делал это на предыдущем ходу.
Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 21 Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 21 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 20
Задание 19
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите наименьшее значение S, при котором Петя не может выиграть за один ход, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом.
Задание 20
Для игры, описанной в задании 19, укажите два значения S, при которых у Вани есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.
В ответе запишите найденные значения в порядке возрастания: сначала меньшее, затем большее.
Задание 21
Для игры, описанной в задании 19, найдите наибольшее значение S, при котором у Пети есть выигрышная стратегия, позволяющая ему выиграть третьим ходом при любой игре Вани, но у Пети нет стратегии, которая позволяла бы ему гарантированно выиграть первым или вторым ходом.
Решение
def f(s,c,m,h1,h2):
if s>=21: return c%2==m%2
if c==m: return 0
h=[]
if c%2==0:
if h1!=1:h+=[f(s+1,c+1,m,1,h2)]
if h1!=2:h+=[f(s+2,c+1,m,2,h2)]
if h1!=3:h+=[f(s*2,c+1,m,3,h2)]
else:
if h2!=1:h+=[f(s+1,c+1,m,h1,1)]
if h2!=2:h+=[f(s+2,c+1,m,h1,2)]
if h2!=3:h+=[f(s*2,c+1,m,h1,3)]
if (c+1)%2==m%2: return any(h)
else: return all(h)
for s in range(1,20):
for m in range(1,6):
if f(s,0,m,0,0):
if m==3: #(19 - m == 3, 20 - m == 4, 21 - m ==5)
print(s,m)
break
Ответ:
19 - 8 (m == 3)
20 - 6 7 (m == 4)
21 - 5 (m == 5)
9) (№ 5064)Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом не разрешается делать ход, после которого количество камней в куче будет делиться на 3. Например, если в начале игры в куче 4 камня, Петя может первым ходом получить кучу из 5 или из 8 камней. Добавить два камня Петя не может, так как в этом случае в куче станет 6 камней, а 6 делится на 3.
Игра завершается, когда количество камней в куче становится не менее 151. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 151 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 149, S не делится на 3.
Задание 19
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня сможет выиграть своим первым ходом.
Задание 20
Для игры, описанной в задании 19, укажите два значения S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани. В ответе запишите найденные значения в порядке возрастания: сначала меньшее, затем большее.
Задание 21
Для игры, описанной в задании 19, найдите такое значение S, при котором у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.
Решение
def f(s,c,m):
if s%3==0:return 0
if s>=151: return m%2==c%2
if m==c: return 0
h=[]
if (s+1)%3!=0: h+=[f(s+1,c+1,m)]
if (s+2)%3!=0: h+=[f(s+2,c+1,m)]
if (s*2)%3!=0: h+=[f(s*2,c+1,m)]
if (c+1)%2==m%2: return any(h)
return all(h)
for s in range(1,150):
for m in range(1,7):
if f(s,0,m):
if m==2:print(s)
break
Ответ:
19 - 74 (m == 2)
20 - 37 73 (m == 3)
21 - 71 (m == 4)
Page updated
Google Sites
Report abuse