Primeiramente, acho que seria interessante fazer um código inicial para analisar o problema, que retorne mensagens conforme as jogadas vão acontecendo, para entender melhor como o jogo funciona. Vamos definir 2 recursões múltiplas (uma função chama a outra). No jogo, o jogador inicial é definido aleatoriamente.
def MaryJoga(n):
if(n>4):
print("Mary jogou e sobram " + str(n-4) + " peças! Vez de John.")
return JohnJoga(n-4)
else:
if(n==1,3,4):
print("Mary vence!")
return 0
elif(n==2):
print("John vence!")
return 1
else:
print("Erro de input")
def JohnJoga(n):
if(n>4):
print("John jogou e restam "+ str(n-1) + " peças! Vez de Mary.")
return MaryJoga(n-1)
else:
if(n==1,3,4):
print("John vence!")
return 1
elif(n==2):
print("Mary vence!")
return 0
else:
print("Erro de input")
def Jogo(n):
import random
JogadorInicial = random.randint(0,1)
if(JogadorInicial==0):
print("John começa jogando!")
return JohnJoga(n)
else:
print("Mary começa jogando!")
return MaryJoga(n)
A melhor estratégia é a de John. Por quê? Mary ganha em t quando em t-1 é a vez de John e há 5 peças na mesa (John tira uma, sobram quatro e Mary ganha), ou chega na sua vez com 7 peças na mesa (John tira um, sobram 6, Mary tira 4, sobram 2, Mary Ganha). Já John ganha em t quando em t-1 é a vez de Mary e há 5,7 ou 8 peças na mesa. Portanto, há mais possibilidades de vitórias de John e, em muitas repetições, espera-se que John vença a maioria das vezes. De fato, definindo uma função mais "frutífera", podemos verificar isso numericamente:
def MaryJogaNum(n):
if(n>4):
return JohnJogaNum(n-4)
else:
if(n==1,2,3,4):
return 0
else:
print("Erro de input")
def JohnJogaNum(n):
if(n>4):
return MaryJogaNum(n-1)
else:
if(n==1,2,3,4):
return 1
else:
print("Erro de input")
def JogoNum(n):
import random
JogadorInicial = random.randint(0,1)
if(JogadorInicial==0):
return JohnJogaNum(n)
else:
return MaryJogaNum(n)
Agora, simulando as repetições:
soma = 0
for i in range(1000000):
x = random.randint(1,100)
soma = soma + JogoNum(x)
print(soma)
Que retornou 594803 no meu caso, comprovando a conclusão analítica anterior.