Siga-nos

Perfil

Expresso

Solução para o problema "A força de uma ideia simples"

  • 333

Blogue "O problema da semana"

Na passada sexta-feira deixámos um desafio que envolvia um jogo muito simples para dois jogadores. O objectivo era definir uma estratégia ganhadora para o primeiro jogador, que lhe permitisse obter um lucro total não inferior ao segundo jogador. Esta terça-feira apresentamos-lhe a solução. Este jogo foi criado pelo matemático israelita Noga Alon, e usado em entrevistas de emprego para empresas de tecnologia, como forma de testar a capacidade de raciocínio dos candidatos.

Problema

20 moedas de diversos valores estão dispostas em fila numa mesa. Cada um de dois jogadores retira alternadamente uma moeda de uma das pontas. O jogo termina quando não existirem mais moedas em cima da mesa. Ganha quem retirar a maior soma.

Solução

O primeiro jogador começa por atribuir alternadamente as cores branca e preta a cada uma das moedas. A moeda mais à esquerda é branca, a segunda é preta, e assim sucessivamente. As moedas que ocupam uma posição par são brancas e as restantes pretas. Podemos agora somar os valores das moedas que estão nas casas brancas e comparar com a soma das moedas que estão nas casas pretas, verificando desta forma qual dos dois grupos de moedas garante um lucro superior.

O primeiro jogador consegue sempre retirar todas as 10 moedas de um dos dois grupos à sua escolha. Suponhamos por exemplo que o grupo mais favorável é o das casas brancas. Nesse caso, o primeiro jogador começa por retirar a moeda mais à esquerda, que é branca, deixando ao seu adversário duas moedas pretas nos extremos. Desta forma, o primeiro jogador pode em cada jogada retirar uma moeda numa casa branca e obriga o segundo jogador a retirar sempre moedas pretas!

O mais interessante neste tipo de jogo é a possibilidade de descrever uma estratégia ganhadora, neste caso para o primeiro jogador, usando apenas o conceito muito simples de paridade. Claro que esta estratégia pode não ser a melhor em algumas situações particulares, contudo tem a vantagem de servir para qualquer disposição inicial das moedas, garantindo ao primeiro jogador obter pelo menos metade do total em cima da mesa, ou seja, da soma dos valores de todas as moedas.

A receita apresentada funciona com qualquer número de moedas, desde que seja par. No caso de começarmos com um número ímpar de moedas, a situação é bem mais complexa, ou pelo menos confusa. Por exemplo, com apenas 3 moedas de valores 1, 5 e 2, o segundo jogador ganha facilmente, basta ficar com a moeda do meio, o que é sempre possível. De facto, os problemas matemáticos também são como as cerejas, resolvemos um mas acabamos com mais uns quantos na mão.