Pré-Vestibular ⇒ (UFPE - 1992) Lógica

[ALDRINMOD]

De quantas maneiras distintas o Labirinto da figura abaixo pode ser atravessado de um lado a outro sem que se cruze mais de uma vez a mesma passagem?

lab.GIF (2.33 KiB) Exibido 646 vezes

[fabit]

Sem ser chato, a resposta é [tex3]2^5=32[/tex3]. Sendo chato, a resposta é 64, pois aí eu consideraria ir do lado direito para o esquerdo como uma "maneira" diferente de se ir do esquerdo para o direito.

Por que a "ida" é [tex3]2^5[/tex3]? Ora, cada parede que separa dois cômodos consecutivos tem só 2 portas. Escolho de 2 formas e quando chego ao cômodo seguinte não posso voltar pela que não escolhi sem ter que, depois repetir alguma porta. Em outras palavras, só dá pra "ir pra frente" nesse labirinto.