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 2007 - 3ª Fase - Nível 3)

Arrumam-se $2007^{2}$ quadradinhos iguais, formando um tabuleiro $2007 \times 2007$. Arnaldo e Bernaldo disputam o seguinte jogo: cada jogada de Arnaldo consiste em retirar $4$ quadradinhos que formem um quadradinho $2 \times 2$. Cada jogada de Bernaldo consiste em reitrar apenas $1$ quadradinho. Os jogadores jogam alternadamente, sendo Arnaldo o primeiro a jogar. Quando Arnaldo não puder fazer sua jogada, Bernaldo fica com todas as peças restantes do tabuleiro. Ganha o jogo aquele que possuir mais quadradinhos no final.

É possível que Bernaldo ganhe o jogo, não importanto como Arnaldo jogue?

Solução: Sim, é possível. Vamos preencher o tabuleiro com as letras $A, B, C$ e $D$ conforme o seguinte padrão:

Cada vez que Arnaldo pega um quadrado $2 \times 2$, ele pega exatamente uma das letras. Se Bernaldo esgotar alguma das letras, então Arnaldo não poderá mais jogar. Qual das letras ele consegue esgotar mais rapidamente? Vejamos quantas vezes cada alguma aparece no tabuleiro.

Observe que $A$ e $B$ estão nas linhas ímpares e $C$ e $D$ nas linhas pares. Na lista $1,2,3,\cdots ,2007$ aparece $1004$ ímpares e $1003$ pares. Desta forma, $A$ e $B$ aparecem em $1004$ linhas. Além disso, observe que $A$ aparece nas colunas ímpares e $B$ nas pares. Ou seja, $A$ aparece em $1004^{2}$ quadradinhos e $B$ em $1004\cdot 1003$.

Além disso, observe que $C$ aparece nas colunas ímpares e $D$ nas pares. Ou seja, a quantidade de quadradinhos em que $C$ aparece é $1003\cdot 1004$ enquanto a de $D$ é $1003^{2}$. Observe que a letra que menos aparece é a $D$.

Vejamos o que acontece se Bernaldo jogar em casas do tipo $D$. Observe que, em cada jogada, o jogador retira uma casa com a letra $D$. Assim depois de $1003^{2}$ jogadas, será impossível alguém jogar.

Quantas peças pegaram cada um dos jogadores? Observe que Arnaldo fez ${\frac {1003^{2}+1}{2}}$ jogadas e em cada uma delas retirou quatro casas. Com isso, o total de casas retiradas foi $4\left({\frac {1003^{2}+1}{2}}\right)$. Para mostrarmos que Bernaldo vence, basta provarmos que esta quantidade é menor que a metade do total de quadradinhos do tabuleiro. De fato, suponha, por absurdo, que $4\left({\frac {1003^{2}+1}{2}}\right)>{\frac {2007^{2}}{2}}$. Esta desigualdade pode ser reescrita como

$4\cdot 1003^{2}+4>2007^{2}\Leftrightarrow 2^{2}\cdot 1003^{2}+4>2007^{2}\Leftrightarrow 2006^{2}+4>2007^{2}\Leftrightarrow 4>2007^{2}-2006^{2}.$

Absurdo. Logo, Bernaldo possui uma estratégia vencedora.

Exemplo (Cone Sul 2004)

Arnaldo escolhe um inteiro $a$, $a \ge 0$, e Bernaldo escolhe um inteiro $b$, $b \ge 0$. Ambos dizem, em segredo, o número que escolheram a Cernaldo, e este escreve em um quadro os números $5$, $8$ e $15$, sendo um desses a soma $a+b$.

Cernaldo toca uma campainha e Arnaldo e Bernaldo, individualmente, escrevem em papéis distintos se sabem ou não qual dos números no quadro é a soma de $a$ e $b$, e entregam seus papéis para Cernaldo. Se em ambos os papéis está escrito NÃO, Cernaldo toca novamente a campainha, e o procedimento se repete.

Sabe-se que Arnaldo e Bernaldo são sinceros e inteligentes.

Qual é o número máximo de vezes que a campainha pode ser tocada até que um deles escreva que sabe o valor da soma?

Solução: Comecemos analisando quais são os valores de $a$ e $b$ em que Arnaldo ou Bernaldo sabem o valor da soma logo na primeira rodada.

Analisemos somente os valores de $a$, pois para os valores de $b$, o raciocínio era análogo.

1ª Rodada:

Se $a\geq 9$, então Arnaldo saberá de primeira a soma é $15$, pois $b \ge 0$. Logo, neste caso, a campainha irá tocar apenas uma vez. O mesmo acontece com Bernardo se $b\geq 9$. Melhor ainda, sabemos que se for pra segunda rodada, então $a,b\leq 8$.

2ª Rodada:

Se $a=6$, então, neste caso, a soma não pode ser $5$ (pois $b \ge 0$) e também não pode ser $15$ (pois $b\leq 8$). Logo, a soma será $8$

Para outros valores de $a$ ainda não é possível analisar. Por isso, é necessário ir para a próxima rodada.

3ª Rodada:

Se estivermos nesta rodada, ambos sabem que $a,b\leq 8$ e $a$ e $b$ são diferentes de $6$.

Aqui, se $a=2$, como $b$ é diferente de $6$ e menor ou igual a $8$, então a única soma possível é $5$.

Agora se $a$ e $b$ são diferentes de $2$, dá para algum deles pode saber a soma nessa rodada? Não.

4ª Rodada:

No começo da rodada, ambos sabem que $a,b\leq 8$ e $a$ e $b$ são diferentes de $2$ e $8$.

Se $a=3$, a soma não pode ser $5$ (pois $b$ é diferente de $2$) e nem $15$ (pois $b\leq 8$). Logo, a soma será $8$.

Para valores de $a$ diferentes de $3$, é impossível saber qual é a soma.

5ª Rodada:

No começo da rodada, ambos sabem que $a,b\leq 8$ e $a$ e $b$ são diferentes de $2$, $3$ e $8$.

Se $a = 5$, a soma não pode ser $8$ (pois $b$ é diferente de $3$) e nem $15$ (pois $b\leq 8$). Logo, a soma será $5$.

Para valores de $a$ diferentes de $5$, é impossível saber qual é a soma.

6ª Rodada:

No começo dessa, ambos sabem que a e b só podem ser $0,1,4,7$ ou $8$.

Se $a = 0$, então a soma não pode ser $5$ (pois $b$ é diferente de $5$) e nem $15$ (pois $b\leq 8$). Logo, a soma é $8$.

Se $a$ é diferente de $0$, ainda não podemos afirmar nada.

7ª Rodada:

No começo dessa, ambos sabem que a e b só podem ser $1,4,7$ ou $8$.

Se $a=8$, então a soma não pode ser $5$ (pois $b \ge 0$) e nem $8$ (pois $b$ é diferente de $0$). Logo, a soma é $8$.

Se $a$ é diferente de $8$, não se pode determinar a soma.

8ª Rodada:

No começo dessa, ambos sabem que a e b só podem ser $1,4$ ou $7$.

Se $a=7$, a soma não pode ser $5$ (pois $b \ge 0$) e nem $15$ (pois $b$ é diferente de $8$. Logo, a soma é $8$.

Se $a$ é diferente de $7$, não é possível determinarmos a soma.

9ª Rodada:

No começo dessa, ambos sabem que a e b só podem ser $1$ ou $4$.

Se $a = 1$, então a soma não pode ser $8$ (pois $b$ é diferente de $7$) e nem $15$ (pois $b\leq 8$). Logo, a soma é $5$.

10ª Rodada:

Neste caso, ambos sabem que $a$ e $b$ são ambos iguais a $4$.

Desta forma, a campainha pode ser tocada, no máximo, $10$ (lembre-se que ela foi tocada uma vez antes de começarem as rodadas).

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$.

Exemplo (Cone Sul 2008)

Dois amigos $A$ e $B$ devem resolver a seguinte adivinha: cada um deles recebe um número do conjunto $\{1,2,\cdot ,250\}$ mas não vê o número que o outro recebeu. O objetivo é que cada amigo descubra o número do outro. O procedimento que devem seguir é anunciar, por turnos, números inteiros positivos não necessariamente distintos: primeiro $A$ diz um número, em seguida $B$ diz um número, depois novamente $A$, etc., de modo que a soma de todos os números anunciados seja $20$. Demonstrar que existe uma estratégia de modo que, através de um acordo prévio $A$ e $B$ possam atingir o objetivo, sem importar quais números cada um receba no começo da adivinha.

Solução: O acordo prévio que $A$ e $B$ devem fazer é o seguinte: para cada número do conjunto $\{1,2,\cdots ,250\}$, eles devem associar a uma sequência de $10$ elementos formadas por cinco $0$'s e cinco $1$'s, de modo que dois números diferentes não podem ser associados a mesma sequência.

Dá para montar essa associação, pois o número de sequências é maior do que o número de elementos do conjunto $\{1,2,\cdots ,250\}$. De fato, a quantidade de sequências é ${10 \choose 5}=252$. Assim, só de saber a sequência, os jogadores conseguem saber o número escolhido.

Como o número $A$ consegue dizer a sequência para $B$? Suponha que o número escolhido por $A$ vá para uma sequência onde os números $1$'s apareçam na sequência $a_{1},a_{2},a_{3},a_{4},a_{5}$, com $1\leq a_{i}\leq 10$. Então $A$ dirá $a_{1},a_{2}-a_{1},a_{3}-a_{2},a_{4}-a_{3},a_{5}-a_{4}$.

Como $B$ pode conseguir $a_{1},a_{2},a_{3},a_{4},a_{5}$ com os números ditos por $A$? Ele já sabe que o primeiro número dito foi $a_1$. Já $a_2$ ele obtém somando os dois primeiros números, $a_3$ ele obtém somando os três primeiros números e assim por diante.

Observe que a soma dos números ditos por $A$ é $a_5$, que é um número menor ou igual a $10$.

Além disso, $B$ deve fazer a mesma coisa. Mas e se a soma dos números ditos não for $20$? Basta que $A$ diga o número que faça com que a soma seja $20$ para poder "completar" (ambos saberão que esse sexto número dito por $A$ não vai influenciar nas informações que eles precisam descobrir).

Desta forma, cada jogador pode descobrir o número do outro.

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.

Em certos casos, existem as posições perdedoras, ou seja, aquelas em que a pessoa perde, independente do que faz. E uma posição vencedora seria aquela que leva o adversário para a posição perdedora.

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 $2004$).

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 primeira rodada deve ser escolhido o número $2$. Logo, $n-19=1$, ou seja, $n=20$. E quem tem a estratégia vencedora é quem joga pela segunda vez, ou seja, Bernaldo.

Exemplo (Cone Sul 2006)

Duas pessoas, $A$ e $B$, jogam o seguinte jogo: eles retiram moedas de uma pilha que contém, inicialmente, $2006$ moedas. Os jogadores jogam alternadamente retirando, em cada pilha, $1$ a $7$ moedas; cada jogador guarda as moedas que retira. Se quiser, um jogador pode passar (não retirar moedas em sua vez), mas para isso deve pagar $7$ moedas das que retirou da pilha em jogadas anteriores. Estas $7$ moedas são colocadas em uma caixa separada e não interferem mais no jogo. Ganha quem retira a última moeda, e $A$ começa o jogo.

Determinar qual jogador pode assegurar a vitória, não importando como jogue o outro. Mostrar uma estratégia vencedora e explicar por que é vencedora.

Solução: O jogador $A$ é quem tem a estratégia vencedora. Vejamos porque isso funciona em cada um dos casos.

1º Caso: $B$ remove sempre $7$ moedas (sem passar)

Aqui, quem tem a estratégia vencedora é o jogador $A$: basta ele retirar sempre $7$ moedas em todas as jogadas. Assim, a cada rodada, haverão $14$ moedas a menos. Com isso, após $143$ rodadas, haverão $2006-143.14=4$ moedas e assim $A$ vence.

2º Caso: $B$ remove sempre $7$ moedas, mas no seu último movimento, ele passa

Neste caso, $A$ deverá continuando removendo $7$ moedas por jogada. Restarão $11$ moedas para $A$. Este, para vencer, deve retirar $3$ moedas ou menos, deixando para $B$ $8,9,10$ ou $11$ moedas. Depois disso, se alguém tira qualquer quantidade de moedas da pilha, perde. Por isso, eles devem ficar passando. Mas aqui, $A$ possui mais moedas do que $B$. Logo, ele pode repassar mais vezes do que $B$. Assim, $B$ deve ser o próximo a mexer na pilha, ou seja, a pessoa que irá perder.

3º Caso: $B$ passa ou remove menos do que $7$ moedas em algum turno

Então nós podemos chegar novamente a $8$ moedas (basta $A$ forçar que a quantidade de moedas tenha resto $1$ na divisão por $7$). O resto ocorre da mesma forma que no caso anterior.

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 (Cone Sul 2012)

$A$ e $B$ jogam alternadamente sobre um tabuleiro $2012\times 2013$ com peças suficientes dos tipos:

Em seu turno, $A$ deve colocar uma peça do tipo $1$ sobre casas vazias de tabuleiro. $B$, em seu turno, deve colocar exatamente uma peça de cada tipo sobre casas vazias do tabuleiro. Perde o jogador que não puder realizar sua jogada. Se $A$ é o primeiro a jogar, determine quem possui uma estratégia vencedora.

Observação: As peças podem ser ratacionadas, mas não podem se sobrepor, nem sair do tabuleiro. As peças do tipo $1$, $2$ e $3$ cobrem exatamente $3$, $2$ e $1$ casas do tabuleiro, respectivamente.

Solução: Vamos dividir o tabuleiro em três de $2012\times 671$.

Observe que se $A$ jogar uma ficha do tipo $1$, então $B$ pode jogar as suas de modo que nos três subtabuleiros permaneçam ocupadas as mesmas casinhas.

Figura retirada de https://www.omaforos.com.ar/viewtopic.php?f=16&t=1285

Vamos entender isso melhor. Para isso, repare que $B$ pode usar as peças dos tipos $2$ e $3$ para formar uma peça igual a do tipo $1$.

Na figura, as peças vermelhas representam as jogadas de $A$, enquanto as azuis representam as de $B$.

Podemos garantir que $B$ sempre pode jogar? Sim, afinal se $A$ jogou, então estas três casas estavam desocupadas nos três subtabuleiros.

Portanto, o primeiro que não pode jogar é $A$, ou seja, $B$ possui a estratégia vencedora.

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.

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:

Aqui $B$ possui a estratégia vencedora. Como ele pode ganhar? Por simetria. Quando $A$ começar em algum desses números, basta que $B$ vá para o mesmo número do mesmo tabuleiro $2\times4$. Se $A$ ainda puder jogar, ele vai para o mesmo número em outro tabuleiro $2\times4$ (que pode ser à esquerda ou à direita). Depois de algumas jogadas, $A$ não terá para onde ir, o que faz com que $B$ sempre vença.

• $m=3$

Vamos também dividir em vários tabuleiros menores. Mas para sabermos como lidar com esses tabuleiros depois de divididos, olhemos primeiro para casos menores.

(i) $3 \times 3$

Se $A$ colocar na posição representada na figura abaixo com a letra $A$, então $B$ não pode ir para nenhum lugar deste tabuleiro. Logo, neste caso, $A$ possui a estratégia vencedora.

(ii) $3 \times 4$

Aqui, $B$ possui a estratégia vencedora: basta que ele vá para o mesmo número que $A$.

(iii) $3\times5$

$A$ pode colocar sua peça na casa representada pela letra $A$. Depois disso, basta que ele se mova para o mesmo número que $B$. Depois de algumas jogadas, $B$ não terá mais para onde ir e isso dá a estratégia vencedora para $A$.

(iv) $3\times6$

O raciocínio é o mesmo que o do tabuleiro $3 \times 4$.

Parece que em um tabuleiro $3\times n$, $A$ possui e a estratégia vencedora se $n$ for ímpar e $B$ possui caso contrário. Provemos que isto é, de fato, verdade. Temos que juntar tabuleiros (de alguma forma).

(I) $n=4t+1$

Podemos juntar um tabuleiro $3\times5$ com $t-1$ tabuleiros $3 \times 4$. Neste caso, $A$ pode começar na casa marcada com a letra $A$ (no primeiro tabuleiro $3\times5$) e fazer a mesma estratégia do caso $3\times5$.

(II) $n=4t+3$

Basta juntarmos um tabuleiro $3 \times 3$ com $t$ tabuleiros $3 \times 4$. Neste caso, $A$ pode começar na casa marcada com a letra $A$ (no primeiro tabuleiro $3 \times 3$) e fazer a mesma estratégia do caso $3 \times 3$.

(III) $n=4t$

Basta juntarmos $t$ tabuleiros $3 \times 4$. $B$ pode ganhar aqui, repetindo a estratégia do caso $3 \times 4$.

(IV) $n=4t+2$

Neste caso, unimos um tabuleiro $3\times6$ e $t-1$ tabuleiros $3 \times 4$. $B$ tem a estratégia vencedora, pelo mesmo raciocínio que fizemos no item anterior.

• $m=4$

Também dividiremos um tabuleiro $4\times n$ em um outros tabuleiros menores. Se $n$ é par, dividimos o tabuleiro em $\frac{n}{2}$ tabuleiros $4 \times 2$ e $B$ possui a estratégia vencedora. Caso $n$ for ímpar, dividimos em um tabuleiro $4 \times 3$ e ${\frac {n-3}{2}}$ tabuleiros $4 \times 2$ para também mostrarmos que $B$ tem a estratégia vencedora.

Ou seja, em um tabuleiro $4\times n$, $B$ sempre possui a estratégia vencedora.

• Já podemos generalizar?

Não totalmente, mas já podemos dar um passo bem grande nessa direção. Observe que $B$ sempre ganha em um tabuleiro $4\times n$ é o mesmo que dizer que conseguimos fazer uma numeração neste tipo de tabuleiro em que o cavalo sempre pode ir de uma casa para a outra e essas duas tenham o mesmo número.

Desta forma, se alguém tiver a estratégia vencedora em um tabuleiro $m \times n$ também terá se adicionarmos a ele $k$ tabuleiros $4\times n$. Ou seja, se um jogador possui a estratégia em um tabuleiro $m \times n$, ele também possui em alguma do tipo $(m+4k)\times n$. Assim, basta resolvermos os casos $m=3,4,5,6$ para terminarmos o problema.

Os casos $m=5$ e $m=6$ podem ser feitos de maneira parecida.

Portanto, para $m = 2$, $A$ tem a estratégia vencedora se, e somente se, $n$ não é múltiplo de $4$. Já se $m \geq 3$, $A$ tem a estratégia vencedora se, e somente se, $m$ e $n$ são ambos ímpares.

Lugares Para Estudar

• A aula 01 de Combinatória do POTI nível 1: Arquivo:Aula 01 - Jogos.pdf
• A aula 02 também: Arquivo:Aula 02 - Jogos2.pdf
• Jogos (POTI - Nível 2)
• Problemas Resolvidos: Jogos (POTI - Nível 2)
• A aula da Semana Olímpica de 2005: Jogos (Márcio Assad Cohen)
• A aula da Semana Olímpica de 2010: Jogos (Tertuliano Franco Santos)
• A aula da Semana Olímpica de 2014: Jogando e Ganhando (Régis Prado Barbosa).
• A aula da Semana Olímpica de 2015: Desmata-Mata e Sinais (Ralph Costa Teixeira).
• A aula da Semana Olímpica de 2015: Problemas de Jogos e Tabuleiros (Emiliano Chagas)
• A aula da Semana Olímpica de 2016: Paridade, Jogos e Invariantes (Samuel Feitosa)
• A aula da Semana Olímpica de 2017: Jogos: Cê Manja ou Nim? (Davi Lopes)
• A aula da Semana Olímpica de 2018: Jogos (Luíze D'Urso)
• O artigo da Revista Eureka 27: Jogos e Feijoada no São Paulo's (Emanuel Carneiro).
• O artigo da Revista Eureka 37: Jogos (Bruno Holanda).

Vídeos

• Jogos (POTI - Nível 2): Apesar da aula se chamar "Primeiro Simulado" e ele começá-la com um exercício, a aula em si é sobre jogos.
• A aula do PAPMEM de 2022: Jogos Matemáticos Para Aprendizado e Diversão (Luciano Monteiro Castro).
• Estratégias de Simetria (POTI 2017)
• Análise de Posições Vencedoras (POTI 2017)
• Problemas de Jogos I (POTI 2017)
• Problemas de Jogos II (POTI 2017)
• Exercícios Olímpicos sobre Jogos (POTI 2017)
• Jogos Finitos (POTI 2017)