São dois os jogadores — cada um escolhe, secretamente, um número natural não nulo. Suponhamos que um jogador escolheu o número a e o outro jogador, o número b, com a b>0. Um dos jogadores é sorteado para iniciar o jogo. Ele receberá o par (não ordenado) {a, b} e deverá subtrair do maior número, a, um múltiplo não nulo do menor, kb, de modo que a-kb ainda seja um número natural. O 2.° jogador receberá o novo par (não ordenado)  {a-kb,b} e repetirá o processo, subtraindo do maior número um múltiplo do menor, e assim por diante. Ganhará o jogo quem obtiver o par   {n, 0}.

Suponhamos que os números escolhidos tenham sido 31 e 7. O 1.° jogador terá várias opções de jogo: {24,7}, {17, 7}, {10, 7}, {3, 7}. Suponhamos que escolha  {10, 7}.

Neste caso, o 2.° jogador só terá uma alternativa:  {3, 7}.

Será a vez, novamente, do 1.° jogador que poderá escolher{4, 3} ou{1, 3}.

Se jogar   {1, 3},   o 2.° jogador jogará   {1, 0}  e será o vencedor.

Se jogar {4, 3}, o 2.° jogador será obrigado a jogar {1,3} e, na jogada seguinte, o 1.° jogador ganhará o jogo.

Não é difícil ver que o jogo termina com o par {n, 0}, onde n é o maior divisor comum de  a e  b.

(De fato, se um número dividir a e b,  este número também dividirá a-kb e b.  Reciprocamente, se um número dividir  a-kb e  b,  este número também dividirá a e b.  Portanto, os divisores comuns de a e b e os de a-kb e b são os mesmos e, conseqüentemente, mdc(a,b) = = mdc(a-kb, b) =  ...  = mdc(n, 0) = n.)

Também não é difícil ver por que o jogo se chama "jogo de Euclides" — basta observar o algoritmo de Euclides para o cálculo do maior divisor comum de dois números:

onde, em cada passagem, do maior número subtrai-se um múltiplo do menor (no jogo, este múltiplo não é necessariamente o maior possível).

Como foi feito para o jogo do NIM (RPM 6, p. 47), apresentaremos uma análise matemática do jogo de Euclides que permitirá dizer quem vencerá o jogo, caso ambos os jogadores joguem corretamente.

será decisivo para definir o vencedor do jogo —um jogo que só envolve números inteiros! (Esse número r aparece ao dividirmos um segmento na razão áurea, ao estudarmos os números de Fibonacci e em outras partes da Matemática — veja RPM 6, p. 9.)

Dado um par {a, b}, com  a > b, os pares {a-b, b}, {a-2b, b}, ..., {a-qb, b}, com  a-qb 0,   chamam-se pares derivados de {a, b}.   Assim, {24,7},   {17,7},   {10,7},   {3,7}   são os pares derivados de   {31,7}.

Se a-qb 0 e a-(q + 1)b < 0, {a-qb, b} chama-se par derivado mínimo de {a, b}. No exemplo, {3,7} é o par derivado mínimo de {31,7}. Observe que, dentre todos os pares derivados de um par {a, b}, com a > b, os números do par derivado mínimo são b e o resto da divisão de a por b.

Se {a-qb, b} for o par derivado mínimo, diremos que o par {a-(q-1)b, b} é o par anterior ao par derivado mínimo.

Observe, mais uma vez, o exemplo. Dado o par {31,7}, o 1.° jogador tem apenas duas opções significativas: • ele escolhe o par derivado mínimo   {3, 7};

ou

•  ele escolhe o par anterior ao par derivado mínimo, isto é,  {10, 7},  obrigando o adversário a jogar   {3, 7}.

Qualquer outra escolha daria estas mesmas duas opções ao adversário.

Qual das duas é a melhor?

Vamos fazer a análise no caso geral. Suponhamos que o 1.° jogador receba o par  {n, m}   com   m < n.

 
{n-km, m} = (0, m).

•    Suponhamos, então,   n = qm + r,   0 < r < m.

O jogador deverá optar pelo par derivado mínimo ou pelo par anterior a este, isto é, deverá optar entre: {n-qm, m} - {r, m}   com  0 < r < m  ou

{n-(q-l)m, m} = {qm + r-qm + m, m} = {m + r, m} com  m < m + r Como o adversário

Refazemos, então, a pergunta: o 1.° jogador pode optar entre um par cuja

razão é maior do que  ,  ou um par cuja razão é menor do que  .  Qual é

a melhor opção?

A resposta se encontra no seguinte fato:

Portanto é sempre vantajoso para um jogador escolher aquele par cuja razão é menor do que 2 e passá-lo ao adversário. Este, na sua vez, não ganhará o jogo e será obrigado a devolver um par com razão maior do que  2.

E, agora, o fato decisivo:

Se um jogador receber um par [a, b] com-r-> r ele terá uma estratégia que lhe garantirá a vitória.

Demonstração:

duas opções: escolher o par derivado mínimo ou o anterior ao mínimo. Já vimos que ele deve escolher o par com razão menor do que  ,  o que impedirá a vitória do adversário no lance seguinte.

adversário um par com razão menor do que   .

sempre impedir que seu adversário ganhe o jogo no lance seguinte. Como o jogo é finito (já que os sucessivos pares contêm números naturais cada vez menores), necessariamente haverá uma vez em que o jogador receberá um par {a, b},  com  a  múltiplo de  b, o que lhe dará a vitória.

Em resumo:

Se o jogo começar com o par {a, b}, com a > b > 0, o 1.° jogador terá uma estratégia que terá uma estratégia que lhe garantirá a vitória.

Bibliografia

[1] Roberts, Joe. Elementary Number Theory, a Problem Oriented Approach, MIT Press, 1977 [2] Gardiner, A. Discovering Mathematics, Oxford, 1982.
 

NR: O "problema de Euclides", que se encontra no livro [2] da bibliografia, fez parte da prova da 9.ª Olimpíada Brasileira de Matemática e foi resolvido corretamente por Ralph Costa Teixeira