[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] Problema - Combinatória



Ola Claudio e demais colegas...

Uma duvida quanto a esta questao:

O menor caminho de A ateh B nao seria (1,1)-(2,2)-(3,3)-(4,4)-(5,5)-(6,5)-(7,5) ? Ou seja, distancia = 7 unid. ?


Em uma mensagem de 6/12/2003 23:43:22 Hor. de verão leste da Am. Sul, claudio.buffara@terra.com.br escreveu:


on 06.12.03 22:27, David M. Cardoso at david@suati.com.br wrote:

>
> Gostaria da ajuda de vcs:
> http://www.suati.com.br/david/questao15.gif
>
Usando coordenadas cartesianas, podemos colocar A = (0,0) e B = (7,5).
Para ir de A a B percorrendo a menor distancia possivel (igual a 12 -> 7
quadras pra direita e 5 pra cima) soh podemos ir pra cima ou pra direita.

Consideremos os segmentos:
s(1): de (3,3) a (3,4);
s(2): de (4,3) a (4,4);
s(3): de (5,3) a (5,4);
s(4): de (5,3) a (6,3).

Para ir de A a B percorrendo a distancia minima, temos que passar por
exatamente um desses 4 segmentos.

Passando por s(1): Binom(6,3)*Binom(5,1) = 100
Passando por s(2): Binom(7,3)*Binom(4,1) = 140
Passando por s(3): Binom(8,3)*Binom(3,1) = 168
Passando por s(4): Binom(8,3)*Binom(3,2) = 168

Logo, N = 100 + 140 + 168 + 168 = 576 e a soma dos algarismos de N eh 18.

Um abraco,
Claudio.