O PASSEIO DE LULU

Desafios pendentes:

Edu leva o cão para passear todas as noites. A casa dele fica em uma esquina de um bairro em que todas as ruas são retas e têm cruzamentos em ângulo de 90 graus. Cansado de fazer sempre o mesmo caminho, Edu resolve testar novos trajetos a cada dia, de acordo com as seguintes limitações:

  1. Ao sair de casa, andaria para a esquerda e caminharia o quarteirão inteiro;
  2. Só poderia dobrar esquinas à esquerda;
  3. Poderia andar, no máximo, oito quarteirões sem dobrar uma esquina;

Se os passeios de Edu começaram no dia primeiro de janeiro de 2000, quando se esgotaram os novos trajetos?


Solução:

Os passeios retangulares podem ter quatro trechos (o trecho 1 será equivalente ao trecho 3, e o 2, ao 4) ou cinco trechos (em que o trecho 5 mais o trecho 1 serão equivalentes ao trecho 3). Assim, se o primeiro trecho tiver oito quadras, há oito possibilidades de percurso. Se tiver sete quadras há 8 x 2 possibilidades, uma vez que Eduardo sempre poderá voltar ao ponto inicial a partir da rua que faz esquina com sua casa ou dobrar á esquerda um quarteirão adiante. Seguindo esse raciocínio, o trecho 1, com seis quadras, implicará 8 x 3 possibilidades de percurso e assim por diante. Portanto, os caminhos possíveis são:

8x1 + 8x2 + 8x3 + 8x4 + 8x5 + 8x6 + 8x7 + 8x8 = 288

Uma vez que 2000 foi um ano bissexto, os novos trajetos se esgotaram em 14 de outubro daquele ano.
Por PET-Computação