Para ir até o doce andando sobre as linhas da figura, a formiguinha deve andar 4 vezes para frente e 5 vezes para baixo. Um caminho de menor comprimento possível ocorre quando ela anda simultaneamente para frente e para baixo, na diagonal, o máximo de vezes possível. De acordo com as linhas da figura, esse caminho de menor tamanho possível ocorre quando ela anda 4 vezes na diagonal, escolhendo uma vez só para andar para baixo. Logo, se a letra D representar andar na diagonal e a letra B andar para baixo, os caminhos de menor comprimento possível são:
- D+D+D+D+B;
- D+D+D+B+D;
- D+D+B+D+D;
- D+B+D+D+D;
- B+D+D+D+D.
Portanto, são 5 os caminhos de menor comprimento possível.
DETALHAMENTO DA SOLUÇÃO:
A principal ideia para a resolução desse problema é a percepção de que o caminho mais curto para ir de um ponto a outro é através do segmento de reta que une os dois pontos, como exemplificamos na figura abaixo:
Utilizando este conceito, vamos a duas considerações:
I) Nenhum caminho mínimo pode passar por qualquer ponto acima da diagonal azul indicada na figura abaixo. Isso é fato, pois a formiga começa em um ponto da diagonal azul e, se em algum momento passar, por exemplo, no ponto verde, obrigatoriamente terá que tornar a passar na diagonal azul e, portanto, o caminho que fosse direto do ponto inicial até este ponto de retorno à diagonal seria menor que o caminho em questão.
II) O mesmo raciocínio se aplica para concluirmos que o caminho mínimo não pode passar por qualquer ponto abaixo da diagonal vermelha, pois, se passar por um ponto, o laranja por exemplo, obrigatoriamente passaria por dois pontos da diagonal vermelha e, portanto, esse caminho ficaria maior do que o que une os dois pontos diretamente.
Portanto, todos os caminhos mínimos precisam ficar restritos à região compreendida entre as paralelas azul e vermelha, a formiga começa na diagonal azul e, em algum momento, desce para vermelha. Como há 5 segmentos verticais unindo as duas diagonais, há 5 maneiras de ela fazer um caminho mínimo.
