Jogos

Existem estratégias que podem ser úteis nas resoluções destes problemas:

• Faça casos pequenos para entender melhor o jogo.
• Faça algumas partidas contra si mesmo.
• Procure por invariantes no jogo, ou seja, características que não variam conforme o jogo acontece.
• Entenda quais são as características do começo e do final.
• Pense em qual a maneira que alguém deve deixar para o seu adversário para fazê-lo perder.

Exemplo (Cone Sul 1992)

Considere um tabuleiro $m \times n$. Em cada casa existe um inteiro não negativo assinalado. Uma operação consiste em escolher qualquer uma das duas casas com $1$ lado em comum, e adicionar a estes $2$ números o mesmo inteiro (ele pode ser negativo) de tal forma que os dois resultados sejam não negativos. Quais são as condições que devem ser satisfeitas inicialmente nos números assinalados das casos, de tal que forma que, depois de algumas operações, haverão $0$ em todas as casas?

Solução: Cada vez que somamos um inteiro em cada dos dois quadradinhos com lados em comum, alteramos o valor de uma casa na posição par e outra na posição ímpar. Podemos usar isto a nosso favor. Faremos o seguinte: pintaremos as casas do tabuleiro de preto e branco (conforme um tabuleiro de xadrez).

Desta forma, podemos entender cada operação como sendo somar um inteiro $k$ em uma casa de cada cor. Queremos saber se podemos fazer a soma dos números das casas brancas e das casas pretas seja igual a $0$.

Se fizermos as operações de trás para frente, de uma rodada para a anterior devemos subtrair o mesmo inteiro $k$, tanto da soma dos números das casas brancas quanto a das somas pretas. Com isso, no início, a soma dos números das casas brancas é o mesmo das pretas.

Resumo: já vimos que se pudermos zerar todas as casas, então a soma dos números das casas brancas é igual ao das casas pretas. Agora, se a soma das casas brancas for igual a soma das casas pretas, podemos zerar o tabuleiro? Sim! Como?

Vamos imaginar que temos o tabuleiro com a soma dos números brancos igual à dos números pretos. Para zerar o tabuleiro, comecemos com o seguinte: vamos zerar subtrair números na coluna da direita até que todos eles zerem (observe que também mexeremos na coluna que fica à esquerda dela). Repita este processo até que sobre duas colunas.

Faça o mesmo para as linhas até que sobre apenas uma só (sem ser zerada). Observe que sobrou um pedaço $2 \times 1$ do tabuleiro. Um dos números estará em uma casa branca e o outro em uma casa preta. Como a soma da dos números casas brancas é igual à soma dos casas pretas, estes números são iguais. Logo, basta subtrairmos o mesmo número das duas casas para a zerarmos.

Portanto, podemos zerar todas as casas se, e somente se, a soma dos números das casas brancas é igual ao das casas pretas.

Exemplo (Cone Sul 1991)

Duas pessoas, $A$ e $B$, jogam o seguinte jogo: $A$ começa escolhendo um número inteiro positivo e então, cada jogador em seu turno diz um número conforme as seguintes regras:

Se o último número dito for ímpar, o jogador soma $7$ a este número;

Se o último número dito for par, o jogador divide ele por $2$.

O ganhador é o jogador que repete o primeiro número dito. Encontre todos os números que $A$ pode escolher para ganhar. Justifique sua resposta.

Solução: O jogador $A$ ganha se o número que ele escolheu na primeira vez aparecer em alguma posição ímpar (ou seja, ou na terceira, ou na quinta etc). Assim, os números que fazem $A$ ganham aparecem de dois em dois. Se começarmos com um número "razoavelmente grande", ele diminui logo nas primeiras rodadas.

Consideraremos aqui $x$ o número inicial. Vamos encontrar algum valor para $x$ suficientemente grande, tal que se $x$ for maior que este número, ele irá diminuir a cada duas rodadas. Por que encontrar isto é bom? Porque saberemos que se o primeiro termo for maior que este número, então ele nunca poderá subir (se estivermos olhando a cada duas rodadas), isto é, ele nunca vai voltar ao número original.

Como podemos olhar para as primeiras rodadas? Depende do valor de $x$. Existem três possibilidades:

1º Caso: $x$ é ímpar.

Aqui, os primeiros números serão $x,x+7,{\frac {x+7}{2}}$. Ele diminui a cada duas rodadas se, e somente se,

$x>{\frac {x+7}{2}}\Leftrightarrow x>7.$

2º Caso: $x$ é múltiplo de $4$.

Aqui, os números que aparecerão depois de duas rodadas são $x,{\frac {x}{2}},{\frac {x}{4}}$. Neste caso, $x$ diminui a cada duas rodadas se, e somente se,

$x>{\frac {x}{4}}\Leftrightarrow x>0.$

3º Caso: $x$ é par, mas não é múltiplo de $4$.

Os primeiros termos serão $x,{\frac {x}{2}},{\frac {x}{2}}+7$. Aqui $x$ diminuirá a cada duas rodadas se, e somente se,

$x>{\frac {x}{2}}+7\Leftrightarrow x>14$

Desta forma, em qualquer um dos casos, se $x>14$, então ele nunca irá voltar ao número original nas posições ímpares. Por isso, devemos testar as soluções menores ou iguais a $14$. As únicas em que $A$ ganha são $1,2,4,7,8,14$.

Exemplo (OBM 2004 - 3ª Fase - Nível 2)

Esmeralda tem uma pilha com $100$ pedras. Ela divide essa pilha em duas novas pilhas e em seguida multiplica as quantidades de pedras nessas duas novas pilhas e escreve o produto em um quadro. Ela então escolhe uma pilha com mais de uma pedra e repete esse procedimento: a pilha é dividida em duas , as quantidades de pedras nessas duas pilhas são multiplicadas e o produto escrito no quadro. Esta operação é realizada até se obter apenas pilhas com 1 pedra cada. Quais são os possíveis valores da soma de todos os produtos escritos no quadro?

Solução: Faremos o seguinte: começaremos entendendo bem a conta depois de uma divisão qualquer em duas pilhas. Depois de entendida a álgebra desse processo, conseguiremos entender o processo de várias divisões com mais precisão nas contas.

Considere uma pilha com $a$ pedras que é distribuída em duas pilhas com Exemplo $b$ e $e$ pedras. O produto escrito no quadro será $be$. Podemos escrever este número de outra maneira? Vamos relacionar $a$, $b$ e $e$ de modo a aparecer esse produto. O que sabemos sobre eles? Primeiramente que $a=b+e$. E como fazer $be$ aparecer? Uma maneira é elevarmos ambos os lados ao quadrado:

$a^{2}=b^{2}+2be+e^{2}\Leftrightarrow be={\frac {a^{2}-b^{2}-e^{2}}{2}}$.

Façamos o caso com várias divisões. Chamaremos de $b_1$ e $b_2$ as quantidades de pedras das pilhas depois da primeira divisão. As outras quantidades das próximas divisões serão $b_{3},b_{4},\dots ,b_{i},b_{i+1}$. Com isso, o número escrito no quadro será

$S=b_{1}b_{2}+b_{3}b_{4}+\dots +b_{i}b_{i+1}.$

Se aplicarmos o raciocínio que fizemos para a primeira pilha para todas essas divisões, teremos

$S={\frac {100^{2}-b_{1}^{2}-b_{2}^{2}}{2}}+{\frac {b_{1}^{2}-b_{3}^{2}-b_{4}^{2}}{2}}+\dots +{\frac {b_{i-1}^{2}-b_{i}^{2}-b_{i+1}^{2}}{2}}.$

Observe que alguns $b_{t}'s$ se cancelam. Quais deles? Se $b_{t}>1$, então ${\frac {b_{x}^{2}-b_{t}^{2}-b_{y}^{2}}{2}}$ e ${\frac {b_{t}^{2}-b_{x}^{2}-b_{w}^{2}}{2}}$. Com isso, se $b_{t}>1$, ele irá se cancelar. Mas se $b_{t}=1$, ele não se cancelará.

Observe que existirão $100$ valores de $t$ tais que $b_{t}=1$. Desta forma,

$S={\frac {100^{2}-1-1-\dots -1}{2}}={\frac {9900}{2}}=4500$.

Portanto, a única soma possível é $4500$.

Posições Vencedoras

Algumas posições de um jogo serão chamadas de posições vencedoras se apenas um jogador (o vencedor) conseguir passar por ela e por causa delas conseguir vencer.

E como descobrir que apenas um jogador consegue passar pelas soluções vencedoras? Em primeiro lugar, necessariamente, a posição final deve ser vencedora.

Além disso, precisamos garantir duas coisas: que o jogador vencedor sempre consegue ir para uma posição vencedora e que seu adversário não consegue ir para lá. Para isso, um jogador nunca pode ir, em uma só rodada, de uma posição vencedora para uma não vencedora, enquanto um jogador que não está em posição vencedora pode ir para uma, em apenas uma rodada.

Assim, se você sabe quais são as posições vencedoras, você resolveu o jogo.

E como saber quem tem a estratégia vencedora? Se a posição inicial for vencedora, então o segundo jogador irá vencer. Caso contrário, o primeiro jogador vence.

Exemplo (OBM 2004 - 3ª Fase - Nível 2)

Em um jogo para dois participantes, Arnaldo e Bernaldo alternadamente escolhem um número inteiro positivo. A cada jogada, deve-se escolher um número maior que o último número escolhido e menor que o dobro do último número escolhido. Nesse jogo, vence o jogador que conseguir escolher o número $2004$. Arnaldo joga primeiro e inicia com o número $2$. Qual dos dois tem a estratégia vencedora, ou seja, consegue escolher o número $2004$ independente das jogadas do adversário?

Solução: Para nós, rodada será cada vez que uma pessoa joga. Chamemos de $X$ a pessoa que escolheu o número $2004$ e $n$ a rodada em que essa pessoa faz isso. O outro jogador será chamado de $Y$. Vamos entender o que aconteceu nas rodadas $n-1,n-2,\dots$ e assim por diante até conseguirmos descobrir qual foi a rodada inicial.

Para que na rodada $n$, o jogador $X$ tenha escolhido o número $2004$, o outro jogador deveria ter escolhido na rodada $n-1$ algum número entre $1003$ e $2003$, (não dá para $X$ ser menor que $1002$, pois aí $X$ não poderia escolher o $1004$).

E quanto a rodada $n-2$? Nela, o jogador $X$ deverá ter escolhido o número $1002$, para que rodada $n-1$ o jogador $Y$ seja obrigado a escolher um número entre $1003$ e $2003$.

Pelo mesmo raciocínio que fizemos na rodada $n-1$, na rodada $n-3$, $Y$ deve escolher um número entre $502$ e $1001$.

Pelo mesmo raciocínio que fizemos na rodada $n-2$, na rodada $n-4$, $X$ deve escolher o número $501$.

Vamos repetir esses raciocínios para as rodadas anteriores e colocar em uma tabela:

Outras Rodadas Anteriores

Rodada	Quem Escolhe	Número Escolhido
$n-5$	$Y$	Entre $251$ e $500$
$n-6$	$X$	$250$
$n-7$	$Y$	Entre $126$ e $249$
$n-8$	$X$	$125$
$n-9$	$Y$	Entre $63$ e $124$
$n-10$	$X$	$62$
$n-11$	$Y$	Entre $32$ e $61$
$n-12$	$X$	$31$
$n-13$	$Y$	Entre $16$ e $30$
$n-14$	$X$	$15$
$n-15$	$Y$	Entre $8$ e $14$
$n-16$	$X$	$7$
$n-17$	$Y$	Entre $4$ e $6$
$n-18$	$X$	$3$
$n-19$	$Y$	$2$

Mas na segunda rodada, deve ser escolhido o número $2$, pois na primeira rodada deve ser escolhido o número $1$. Logo, $n-19=2$, ou seja, $n=21$. E quem tem a estratégia vencedora é quem começa, ou seja, Arnaldo.

Exemplo (OBM 2010 - 3ª Fase - Nível 2)

Arnaldo e Bernaldo participam do seguinte jogo em um tabuleiro $m \times n$, $m,n \geq 2$. Arnaldo começa escolhendo uma casinha e colocando um cavalo na casinha escolhida; em seguida, Bernaldo e Arnaldo movem alternadamente o cavalo, começando por Bernaldo, com a restrição de que o cavalo não pode cair em casinhas que já foram visitadas. Perde quem não poder mover o cavalo. Determinar, em função de $m$ e $n$, qual jogador tem uma estratégia vencedora para ganhar o jogo, não importando os movimentos do outro jogador e mostrar como ele deve jogar para ganhar.

Observação: Cada movimento de um cavalo consiste em ir duas casas na vertical ou na horizontal e, em seguida, uma casa na direção perpendicular.

Solução: Para facilitar a escrita, usaremos $A$ e $B$ para representar Arnaldo e Bernaldo, respectivamente.

Antes de começar a analise em si, imagine que fizemos o raciocínio para um tabuleiro $2\times 3$. Depois, não precisaremos fazê-lo para o tabuleiro $3 \times 2$ (afinal, o tabuleiro é o mesmo, porém rotacionado). Por isso, podemos supor sem perda de generalidade que $m \le n$.

Comecemos explorando alguns casos particulares.

• $m = 2$

(i) $n$ é da forma $4k+1$

Neste caso, $A$ tem a estratégia vencedora: basta ele colocar o cavalo na primeira coluna (da esquerda para a direita). De fato, observe que o cavalo só pode ir para a direita e deve passar pelas colunas ímpares.

Quem vence neste caso? Aquele que chegar na última coluna, pois o próximo não conseguirá andar mais para a direita. Observe que $A$ passa pelas colunas $1,5,9,13,\dots$, ou seja, pelas fileiras da forma $4t+1$. Enquanto isso, $B$ anda pelas colunas $3,7,11,15,\dots$, isto é, aquelas da forma $4t+3$. Com isso, como a última coluna será $4k+1$, $A$ é quem chegará nela.

(ii) $n$ é da forma $4k+2$ ou $4k+3$

O raciocínio é análogo ao anterior: basta que $A$ coloque o cavalo na segunda coluna (em ambos os casos).

(iii) $n$ é da forma $4k$

Divida o tabuleiro em $k$ tabuleiros $2\times4$ conforme a figura a seguir:

Simetria

Em certas ocasiões, se o jogador copiar a jogada do outro simetricamente, ele vence. Neste caso, devemos garantir que o oponente não "estrague" a nossa estratégia.

Em certos casos, podemos começar tomando um ponto de simetria, ou ainda, o eixo de simetria.

Exemplo (OBM 2002 - 3ª Fase - Nível 2)

São dados um tabuleiro quadriculado $m \times n$ e palitinhos do tamanho dos lados das casas. Dois jogadores jogam alternadamente e, em cada jogada, um dos jogadores coloca um palitinho sobre um lado de uma casa do tabuleiro, sendo proibido sobrepor palitinhos.

Vence o jogador que conseguir completar primeiro um quadrado $1 \times 1$ de palitinhos. Supondo que nenhum jogador cometa erros, qual dos dois jogadores tem a estratégia vencedora, ou seja, consegue vencer independentemente de como jogue seu adversário.

Solução: Aqui a estratégia do espelhamento funciona. Mas temos que tomar cuidado com a paridade da quantidade de palitos que devem ser colocados. Se a quantidade palitos a serem colocadas for ímpar, existe um palito central. Caso contrário, a gente deve se basear no quadrado central.

Vamos entender isso com mais calma. Em que casos a quantidade de palitos colocados será par? E em que casos será ímpar? Para sabermos isto, devemos nos perguntar: qual a quantidade de palitos que podemos colocar num tabuleiro $m \times n$?

Sem perda de generalidade, podemos supor que existem $m$ quadradinhos na horizontal e $n$ na vertical. Então será necessário colocar $m(n+1)$ palitos na horizontal e $n(m+1)$ na vertical. Com isso, precisaremos de $m(n+1)+n(m+1)=2mn+m+n$ palitos.

Vamos analisar a paridade desta última expressão. Como $2mn$ é par, segue que $2mn+m+n$ e $m+n$ possuem mesma paridade (ao somarmos um número par a um número, não alteramos sua paridade). Desta forma, precisamos de uma quantidade ímpar de palitos se $m$ e $n$ tiverem mesma paridade, enquanto teremos uma quantidade par, caso contrário.

Vejamos cada um dos casos.

1º Caso: A quantidade de palitos necessárias para cobrir o tabuleiro é ímpar.

Neste caso, $m$ e $n$ possuem paridades diferentes. O primeiro jogador pode usar a técnica da simetria. Como? Basta ele começar colocando uma peça na posição central e "imitar" as jogadas do segundo, simetricamente com relação a esta peça do centro. Os jogadores sabem que quem colocar o terceiro palito em um quadrado $1 \times 1$ perde. Em alguma hora, todos os quadrados serão ocupados com dois palitos e será a vez do $2$º jogador. Ele vai ter que colocar o terceiro palito em algum dos quadradinhos e irá perder (pois o primeiro jogador irá completar o quadrado).

Logo, nesta ocasião o primeiro jogador vence.

2º Caso: A quantidade de palitos necessárias para cobrir o tabuleiro é par.

Neste caso, $m$ e $n$ possuem paridades iguais. Quem pode ter a estratégia vencedora é o segundo jogador: basta ele jogar espelhadamente em relação ao quadrado central. Quando tivermos todos os quadrados com $2$ palitos, será a vez do primeiro jogador (que irá perder pelo mesmo raciocínio do caso anterior).

Portanto, se $m$ e $n$ tem paridades diferentes, o primeiro jogador tem a estratégia vencedora. Caso contrário, quem consegue vencer é o segundo.