John x Mary: Qual tem a melhor estratégia no jogo? (Exercício 9.1 IRP 2018)

Question

Problema:

Exercise 9.1 — Mary and John are going to play a game involving n
pebbles placed on a board. Each player can remove one, three, or four
pebbles at a time. The one who takes the last pebbles wins. Both players
will win if there are one, three, or four pebbles left and it is their turn
to play. If there are two pebbles left then they will lose since they can
only pick up one pebble. When there are more than four pebbles Mary
has decided that she will take four pebbles whenever she can, while
John’s strategy consists of removing only one pebble. Implement a pair
of mutually recursive functions that simulate the game, and return a 1
in case John wins, and a 0 if Mary wins. Which player has adopted a
better strategy in general, if 1 ≤ n ≤ 100? Consider that any player can
start the game. ~IRP 2018, p. 288

Answer 1

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.