Vou supor que cumes nao existem nos pontos (1,a) e (10,b). Se cumes nas
"pontas" forem validos, o raciocinio tem que mudar um pouquinho.
Entao a pergunta eh: quantos caminhos tem um cume no ponto (x,y)? Por
exemplo, quantos caminhos tem cume em (2,10)?
Ora, para um caminho ter cume em (2,10), basta escolher pontos (1,a) e
(3,b) onde a,b<=9 (sao 9*8 opcoes) e quaisquer outros pontos (4,c),
(5,d),... dentre os 7 valores de y que sobram. Ou seja, sao 9*8*7!=9!
caminhos com este cume.
Analogamente, para ter cume em (2,9), temos 8*7 opcoes para os pontos (1,a)
e (3,b), e o resto faz-se como quiser: total = 8*7*7! opcoes.
Para ter cume em (2,8), sao 7*6*7! opcoes. Para ter cume em (2,7), sao
6*5*7! opcoes. E assim por diante.
Em suma, temos um total de (9*8+8*7+7*6+...+2*1)*7! caminhos com cumes em
(2,y) para algum y.
Repita esse argumento para cumes na forma (3,y), (4,y), etc. Dah um total
de 8*(9*8+8*7+7*6+...+2*1)*7! caminhos com cumes em algum lugar.... Nao,
mentira, eu nao contei caminhos (porque varios deles aparecerao varias
vezes), mas eu contei sim cumes (porque quando um caminho aparece varias
vezes na minha contagem, ele aparece uma vez para cada cume)!
Entao essa eh a resposta que voce quer: (9*8+8*7+7*6+...+2*1)*8!. Espero
nao ter errado bobagens.
Abraco, Ralph.
2015-05-06 11:36 GMT-03:00 Douglas Oliveira de Lima <
profdouglaso.del...@gmail.com>:
> Considere um quadriculado 10x10, no qual existem 100 pontos, {(1,1),
> (1,2),...,(10,10)}, é permitido fazer os seguintes movimentos sair do ponto
> (x,y) para o ponto (x+1,n), onde n,x e y variam no conjunto
> {1,2,3,4,5,6,7,8,9,10}, assim formando um caminho que não saia do
> quadriculado. Um exemplo de um caminho seria {(1,6); (2,7); (3,4); (4,9);
> (5,5); (6,8); (7,1);(8,2);(9,10); (10,3)}.
> No exemplo citado percebemos que os valores de x são consecutivos e os
> valores de y são sempre distintos. Agora considerando todos os caminhos
> desse tipo do exemplo( com x começando em 1 e terminando em 10 e y não se
> repetindo), quantos cumes surgirão?
>
> OBS: Considera-se um cume quando um valor de y é maior do que os valores
> de y vizinhos, no exemplo citado temos 4 cumes, a saber 6<7<4; 4<9<5;
> 5<8<1; 2<10<3.
>
> Agradeço a ajuda e desculpe qualquer erro, caso haja dúvida na pergunta eu
> explico melhor.
> Abraços.
> Douglas OLiveira
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
