Siga-nos

Perfil

Expresso

Solução para o Problema da Semana “O cavaleiro e o dragão”

  • 333

Na passada sexta-feira deixámos AQUI um problema. Hoje apresentamos-lhe a solução.

Um cavaleiro queria matar um dragão. Para isso, teria de cortar, com a sua espada mágica, todas as cabeças e caudas do dragão. Infelizmente, sempre que cortava uma cabeça ao dragão, logo crescia outra no seu lugar. Se cortava uma cauda, apareciam duas novas caudas. Se cortava duas caudas, surgia uma nova cabeça. Finalmente, se cortava duas cabeças ao dragão, nada acontecia. Como matar o dragão com um número mínimo de golpes de espada?

Vamos supor que x representa o número de cabeças do dragão e y o número de caudas. Podemos representar pelo par ordenado (x,y), a situação em que se encontra o dragão em cada momento. Inicialmente, (x,y) = (3,3). O nosso objectivo é chegar a (x,y) = (0,0). Para organizar as suas ideias, pode representar estes pontos num papel quadriculado e ver o movimento que corresponde a cada golpe de espada.



Vamos ver primeiro um modo de não matar o dragão! Consideremos, por exemplo, a seguinte sequência de golpes:

 (3,3) → (4,1) → (4,2) → (5,0).



Primeiro cortámos duas caudas, depois outra cauda e finalmente outras duas caudas. Durante o processo, cresceram duas novas cabeças. Chegados a este ponto, e porque o número de cabeças é ímpar, por muito que tente, o pobre cavaleiro já não consegue matar este dragão! 



Vamos começar de novo. Sabemos que o golpe final tem de ser cortar duas cabeças, porque este é o único golpe que reduz o número total de membros do dragão. Vamos por isso deixar as cabeças para o fim, mas evitando um número ímpar de cabeças.

A seguinte sequência de 9 golpes, não sendo a única, é um dos modos mais rápidos de matar este irritante dragão:



(3,3) → (3,4) → (3,5) → (3,6) → (4,4) → (5,2) → (6,0) → (4,0) → (2,0) → (0,0).


No papel quadriculado é relativamente fácil testar todas as possibilidades de forma exaustiva e ver que não há soluções com menos golpes.

Esta é uma solução com uma natureza geométrica. Pode ver uma mais algébrica nos comentários do artigo anterior (http://expresso.sapo.pt/blogues/problema-da-semana/2015-07-10-O-cavaleiro-e-o-dragao), assim como uma solução mais computacional. Segundo um dos nossos leitores, existem exatamente 166 soluções diferentes para matar o dragão com 9 golpes.


Dragão morto, problema resolvido. Resta esperar por sexta-feira por um novo desafio.