Helder de Carvalho Matos
Aluno do curso de Matemática
da Universidade de Brasília (UnB)

O jogo de quadrinhos é muito conhecido e tão simples que pode ser explicado em poucas palavras. Ele é jogado num quadriculado de pontos como ilustra a Fig. 1.

Cada jogador marca uma aresta unindo dois vértices na mesma horizontal ou na mesma vertical (Fig. 2)

e toda vez que um dos jogadores, ao colocar uma aresta, completar um circuito fechado, ele tem direito (e obrigação) de marcar nova aresta (é importante não confundir “circuito fechado”com “quadrinho unitário” ou, simplesmente, “quadrinho”. Embora todo quadinho seja um circuito fechado, este pode ser mais geral que um simples quadrinho, como ilustra a Fig. 3).

Ganha o jogador que fechar o maior número de quadrinhos e o jogo termina quando o quadriculado original ficar reduzido apenas a quadrinhos. Para facilitar a contagem, os jogadores marcam os quadrinhos que vão fechando com sua inicial. Por exemplo, se Herculano joga com André, o jogo pode terminar com a vitória de André (Fig. 4)

O jogo de quadrinhos é largamente jogado em fundos de salas de aulas, sobretudo quando a  aula fica muito chata ... E foi depois de muito jogar em tais circunstâncias que acabei descobrindo como prever, em qualquer jogo, qual dos dois jogadores ganhará (ou, pelos menos empatará) o jogo.

Daremos algumas definições preliminares. Diremos  que o jogo se encontra numa situação quase final quando no quadriculado não existirem quadrinhos com três arestas, mas um tal quadrinho forçosamente se formará.

com o acréscimo de qualquer nova aresta (Figs 5 e 6). Chamaremos corredor a uma seqüência de quadrinhos que serão fechados por jogadas sucessivas de um mesmo jogador. (Fig. 6)      

Quando um jogo se encontra em situação quase final, como ilustra a Fig. 6, ele consiste exclusivamente de corredores e qualquer aresta adicional precipita o fechamento de quadrinhos ao longo de um corredor. Vamos enumerar os corredores em ordem crescente (mais precisamente, não-decrescente) de seu tamanho. Por tamanho de um corredor entendemos o número de quadrinhos que ele produz com os fechamentos sucessivos. No caso da Fig. 7,
C₁ = C₂ = 1, C₃ = 2 e C₄ = 5.

Vamos supor, como é natural, que cada jogador proceda da maneira a não entregar quadrinhos; e se for obrigado a entregar alguns, que entregue o menor número possível, sito é, que entregue o corredor que tenha menos quadrinhos a fechar. Chamaremos esse procedimento de perda mínima. Veremos, logo adiante, que tal procedimento não assegura vitória, ou mesmo empate; mas permite prever quem vai ganhar (ou empatar) o jogo.

Observemos agora que o jogador que fechar o último corredor (o de número r), fecha também os de números r –2 , r –4, ..., e o outro jogador fechará os corredores r –1, r –3, r –5, ... Há dois casos a  considerar, conforme r seja par ou ímpar.

1º caso: r par. O jogador que fechar o último corredor ganhará um número de quadrinhos igual a

S₁ = Cr + C_r-2 + ... + C₂

E o outro jogador ficará com

S₂ = C_r-1 + C_r-3 +...+ C₁

quadrinhos.

2º Caso: r ímpar: O jogador que fechar o último corredor ganhará.

S₁ = Cr + C_r-2 + ... + C₁

quadrinhos, ao passo que o outro ficará com

S₂ = C_r-1 + C_r-3 +...+ C₂

quadrinhos.

Vamos colocar esses dois casos a lado, em colunas, o que nos permite comparar as somas S1 e S2.

Isto permite constatar, facilmente, que o jogador que terminar o jogo sempre levará vantagem e certamente ganhará se r for impar, pois neste caso, S₁ é estritamente maior que S₂. Portanto, a estratégia para ganhar (ou, pelos menos, empatar) o jogo é, assegurar-se de fechar o último corredor.

Quando, ainda no 2º grau, eu me divertia com o jogo de quadrinhos, acabei percebendo a necessidade de ganhar o último corredor para não perder o jogo. E acabei descobrindo também que se o número de vértices for ímpar, então ganha ou empata o primeiro jogador (o que começa o jogo); ao passo que se o numero de vértices for par, então ganha ou empata o segundo jogador.

Para estabelecermos esse resultado, vamos considerar o jogo já em situação quase final, quando então vale a seguinte formula de Euler generalizada*[ :

A + r = V + R –2,

onde A é o número de arestas, r o numero de corredores, V o número de vértices e R o número de regiões. As figs. 6 e 7 ilustram jogos com uma única região cada um, que é o plano todo. Já as Figs. 8 e 9 mostram jogos com três regiões cada um: R₁, R₂ e R₃.

Para determinar quem ganha o último corredor e, portanto, ganha ou empata o jogo, vamos primeiro supor que R = 1 quando o jogo chega a uma situação quase final. Isto significa que no quadriculado não há circuitos fechados. Então, a fórmula de Euler nos dá.

A + r = V – 1.

Temos de examinar duas hipóteses, conforme V seja ímpar ou par e cada uma delas comporta dois casos.

1ª hipótese: V é impar. Então A + r é par, daí os dois casos seguintes:

Caso 1a: A e r ambos pares. Disto decorre que foi o segundo jogador quem colocou a última aresta (pois A é par), levando o jogo a situação quase final. Portanto, é o primeiro jogador que entregará o primeiro corredor ao segundo; e como r é par será primeiro quem fechará o último corredor, ganhando ou, pelo menos, empatando o jogo.

  Caso 1b: A e r ambos ímpares. Então, foi o primeiro jogador quem colocou a última aresta (pois A é impar), levando o jogo a situação quase final. Em conseqüência, o segundo jogador entregará o primeiro corredor ao primeiro jogador; e como r é impar, o primeiro jogador fechará o último corredor, ganhando o jogo, pois neste caso não há empate.

2ª hipótese: V é par. O raciocínio aqui é inteiramente análogo ao da 1ª hipótese, com dois casos a considerar. A única diferença é que agora quem ganha ou empata o jogo é o segundo jogador.

Falta examinar o caso em que R > 1. Ora, quando o jogo começa, R = 1, pois só temos uma região, que é o plano todo. E, se R permanecer igual a 1 até a situação quase final, um dos jogadores é o favorecido; como acabamos de ver, trata-se do primeiro se V for ímpar e do segundo se V for par. Se um dos jogadores decide fechar um circuito, ele altera a paridade de V + R –2, na situação quase final, portanto altera a paridade da soma A + r na fórmula de Euler e, repetindo os argumentos já usados, o anteriormente favorecido passa a ser desfavorecido. Mas lembremos que pelas regras do jogo, o próprio jogador que fechou um circuito é obrigado a colocar uma nova aresta, o que novamente altera a posição dos jogadores, restabelecendo, as previsões originais. Isto completa a demonstração do teorema em todos os casos.

_________________
* Essa fórmula é uma conseqüência simples da fórmula de Euler para grafos planos (veja-a na pág 143 do livro “Teoria e Modelos de Grafos”de Paulo O. Boaventura Netto. Editora Edgard Blücher, 1979)