Uma forma de proceder seria contar o número de caminhos que passam por um número específico de quadrados.
Assim, o menor caminho passa por três quadrados (excluindo o superior esquerdo mas incluindo o inferior direito) - é o da diagonal e é o único caminho desse comprimento. Chamemos de N(k), o número de caminhos de comprimento k. Assim, N(1) = N(2) = 0 e N(3) = 1. Já o caminho mais comprido não usa nenhuma diagonal e mede 6. Além disso, N(6) = C(6,3) = 20. Justificativa: cada caminho de comprimento 6 pode ser representado por uma sequência do tipo L L B L B B (L = para o lado, B = para baixo, D = pela diagonal), onde existem 3 L's e 3 B's ( e nenhum D). O número de tais sequências é C(6,3). O número total de caminhos é, portanto, N = N(3) + N(4) + N(5) + N(6). Já conhecemos N(3) e N(6). N(5) é o número de caminhos que usa apenas uma diagonal. Exemplos: B B L D L, ou então L D B L B. Todos estes caminhos seriam compostos de 1 D, 2 L's e 2 B's ==> N(5) = 5 * C(4,2) = 5 * 6 = 30 N(4) é o número de caminhos que usa duas diagonais. Exemplos: L D D B; D L D B. Todos os caminhos têm 2 D's, 1 L e 1 B ==> N(4) = C(4,2) * 2 = 6 * 2 = 12. Assim, N = 1 + 12 + 30 + 20 = 63 caminhos distintos. Um abraço, Claudio. ----- Original Message ----- From: "Juliana Freire" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Thursday, January 09, 2003 6:00 PM Subject: Re: Re:[obm-l] IME 96 > É dado um tabuleiro quadrado 4x4. Deseja- > se atingir o quadrado inferior direito a partir do quadrad > o superior esquerdo. Os movimentos permitidos são represen > tados pelas setas: > De quantas maneiras isto é possível ? > O enunciado está vago, pois diz que deve-se partir do > quadrado superior esquerdo e chegar ao quadrado inferior > direito. Mas isso, na minha opinião, pode ser feito > partindo-se de qualquer vértice do quadrado superior > esquerdo e chegar a qualquer vértice do quadrado inferior > direito. Eu não acho que seja para andar pelos vértices, e sim pelo centro do quadrado... andando para um quadrado adjacente ou na diagonal. Assim não tem ambiguidade. ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> ========================================================================= ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =========================================================================