Re: Re:[obm-l] IME 96

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

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" <jufreire@superig.com.br>
To: <obm-l@mat.puc-rio.br>
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 é <nicolau@mat.puc-rio.br>
=========================================================================

=========================================================================
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 é <nicolau@mat.puc-rio.br>
=========================================================================