Soluções Matemática - Semana 15

Problema Iniciante

Vamos falar de uma das mais importantes técnicas de jogos: jogar simetricamente. No nosso problema temos muito pouca informação, então jogar simetricamente é algo que nos livra das especificidades dos tamanhos da mesa e das moedas. O primeiro jogador vai começar botando uma moeda bem no centro da mesa. Agora, para cada jogada do segundo jogador, o primeiro responderá jogando no lugar simétrico ao jogado pelo segundo em relação à moeda central. Isso garante que o primeiro jogador NUNCA PERDE, pois sempre que houver um lugar disponível, o simétrico desse local também estará e sendo assim, sempre que o segundo jogador conseguir jogador o primeiro também conseguirá. Como sabemos que o jogo é finito e o primeiro jogador não perde, o segundo jogador irá eventualmente perder o jogo e provamos o que o enunciado pedia.

 

Problema Intermediário

Vamos falar sobre a segunda das mais conhecidas técnicas de jogos: Achar posições vencedoras.

Definiremos posições vencedoras como posições onde o jogador que vai jogar pode garantir a vitória e definiremos posições perdedoras como aquelas onde o jogador que vai jogar só pode levar seu oponente para uma posição vencedora.

Olhando para essas definições observe que uma posição é vencedora quando dela o jogador pode de duas uma: acabar o jogo ou mandar seu oponente para uma posição perdedora.

Só que para uma pessoa vendo essas estratégias pela primeira vez fica difícil de entender sem um exemplo, então vamos exemplificar com o nosso problema!

Claramente $1,2,3,4$ e $5$ são posições vencedoras, pois delas o jogador pode simplesmente acabar com o jogo tirando a quantidade exata de chocolates da pilha. $6$ do contrário, é uma posição perdedora, pois o jogador que recebe $6$ chocolates é obrigado a deixar seu adversário com  $1,2,3,4$ ou $5$ chocolates e o outro jogador vencerá. Agora, $7,8,9,10,11$ são posições vencedoras, pois o jogador que está em uma dessas posições pode deixar seu oponente com $6$ chocolatess, que é uma posição perdedora. De novo, note que $12$ será uma posição perdedora, pois um jogador nessa posição só pode deixar seu oponente numa posição vencedora. Seguindo esse procedimento (e aqui pode ser um momento para os mais novos treinarem o método de indução matemática) veremos que as posições perdedoras são os $n$ múltiplos de $6$. Hora de matar o problema

Inicialmente Arnaldo comerá $4$ chocolates e deixará Bernaldo com $96$ chocolates. Agora, sempre que Bernaldo tirar $x$ chocolates Arnaldo tirará $6-x$ chocolates e deixará Bernaldo sempre num múltiplo de $6$. Sendo assim, quando Arnaldo deixar Bernaldo com $6$ chocolates, o último tirará entre $1$ e $5$ chocolates e em seguida Arnaldo poderá finalizar o jogo. Logo, nossa resposta é que Arnaldo tem uma estratégia vencedora e acabamos de explicá-la.

 

Problema Avançado

Esse jogo tem várias estratégias, inclusive estratégias que garantem o resultado em $5$ movimentos, e é essa que iremos apresentar aqui. A primeira ideia é que, em dois movimentos podemos descobrir o resto de $x$ por $4$ em até duas perguntas:

$1)$ $mdc(x,4)\longrightarrow$ se o resultado for $2$ ou $4$, saberemos de imediato o resto de $x$ por $4$. Caso contrário, $x$ é impar, daí $x+1$ é par e vamos à pergunta:

$2)$ $mdc(x+1,4)\longrightarrow$ como a resposta será $2$ ou $4$, vamos descobrir o resto de $x+1$ por $4$ e por consequência obteremos também o resto de $x$ por $4$.

 

Na mesma ideia, perguntando por $mdc(x,3)$ e $mdc(x+1,3)$, se algum deles der $3$, teremos descoberto o resto de $x$ por $3$. Caso ambas respostas sejam $1$ saberemos que $x$ só pode deixar resto $1$ por $3$ e do mesmo modo descobrimos o resto de $x$ por $3$.

Aplicando a mesma ideia para $mdc(x,5),mdc(x+1,5),mdc(x+2,5)$ e $mdc(x+3,5)$ podemos descobrir, em $4$ perguntas os resto de $x$ por $5$ analisando quando (ou não) o fator $5$ aparecerá em um desses $mdc's$ (ou se ele nunca aparecerá).

Feitas essas três observações, podemos reunir todas elas em quatro perguntas apenas: $mdc(x,60),mdc(x+1,60),mdc(x+2,60)$ e $mdc(x+3,60)$.

Como nossas observações não dependem da exata resposta e sim de quando os fatores $2,3$ e $5$ aparecem neles, podemos olhar para essas $4$ perguntas e fazer algo análogo ao que fizemos acima e obteremos o resto de $x$ por $3,4$ e $5$.

Pelo teorema chinês dos restos, saberemos o valor de $x$ módulo $3\cdot 4\cdot 5=60$: seja ele $r$. Como $x$ está entre $0$ e $101$, nossa resposta pode ser somente $r$ ou $60+r$. Assim, nossa última pergunta sera $mdc(x,60+r)$. Se a resposta for $60+r\Longrightarrow x=60+r$, já se o $mdc$ for menor que isso $\Longrightarrow x=r$ e de qualquer modo acabamos o problema. Logo, conseguimos descobrir $x$ em $5$ perguntas!